Программная реализация метода ветвей и границ

Автор: Пользователь скрыл имя, 30 Марта 2011 в 19:18, курсовая работа

Описание работы

Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.

Содержание

Введение_________________________________________________________2

Глава 1. Задача о коммивояжере_____________________________________3

Общая постановка задачи______________________________________3
Математическая модель задачи_______________________________3
Глава 2. Метод ветвей и границ____________________________________5

2.1. Основные понятия и определения_____________________________5

2.2. Постановка задачи_________________________________________5

2.3. Решение задачи методом ветвей и границ_______________________5

Глава 3. Программная реализация метода ветвей и границ_____________12

3.1. Язык программирования___________________________________12

3.2. Описание алгоритма_______________________________________12

3.3. Описание основных структур данных_________________________15

3.4. Описание интерфейса с пользователем________________________16

Заключение___________________________________________________17

Литература___________________________________________________18

Текст программы______________________________________________

Работа содержит 1 файл

курсовая по мат методам.doc

— 385.50 Кб (Скачать)
>     flag_draw = true;

     Invalidate(false); 

     } 

     void CKurs_LipinDlg::recursiv (bool flag[],unsigned int cur_path[],int j)  

     { 

     for (int i = 0; i < n; i++)      // для каждой точки

     {

     if (flag[i] == false)        // где  мы еще не были

     {

     flag[i] = true;          // переходим  в нее,

     cur_path[j] = i+1;       // вычисляя длину пройденного пути

     cur_path[n+1] += table [cur_path[j-1]-1] [cur_path[j]-1]; 

       //  ***   если длина текущего пути меньше минимальной   ***

       if (cur_path[n+1] < min_path[n+1])

     // рассматриваем новую точку, если  она не конечная

     if (j < n-1) recursiv (flag, cur_path, j+1);

     else

     {   // или вычисляем длинув сего  пути и ...

     cur_path[n+1] += table [cur_path[n-1]-1] [cur_path[n]-1]; 

     // ...  сравниваем с минимальным

     if (cur_path[n+1] < min_path[n+1])

     {

     for (int k=0; k <= n+1; k++)

        min_path[k] = cur_path[k]; 

     }

     cur_path[n+1] -= table [cur_path[n-1]-1] [cur_path[n]-1];

     }

     flag[i]=false;

     cur_path[n+1] -= table [cur_path[j-1]-1] [cur_path[j]-1];

     }

     }

     return;

     } 

     void CKurs_LipinDlg::OnButton3()

     {

     m_list1.ResetContent();

     flag_Bpoint=true;

     Invalidate(false);

     } 

     void CKurs_LipinDlg::OnButton4()

     {

     CSetting dlg1(this);

     dlg1.DoModal(); 

     } 

     // Setting.h : header file

     // 

     /////////////////////////////////////////////////////////////////////////////

     // CSetting dialog

     class CKurs_LipinDlg;

     class CSetting : public CDialog

     {

     // Construction

     public:

     CSetting(CKurs_LipinDlg* pParent);   // standard constructor 

     CKurs_LipinDlg *parent;

     CEdit t_edit[29][29];

     CFont myFont;

     BOOL f_start;

     void CSetting::Proverka(); 

     // Dialog Data

     //{{AFX_DATA(CSetting)

     enum { IDD = IDD_DIALOG1 };

     // NOTE: the ClassWizard will add data members here

     //}}AFX_DATA 
 

     // Overrides

     // ClassWizard generated virtual function overrides

     //{{AFX_VIRTUAL(CSetting)

     protected:

     virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support

     //}}AFX_VIRTUAL 

     // Implementation

     protected:

     // Generated message map functions

     //{{AFX_MSG(CSetting)

     virtual void OnOK();

     void CSetting::OnMyEdit();

     void CSetting::OnMyEdit1() ; 

     virtual BOOL OnInitDialog();

     //}}AFX_MSG

     DECLARE_MESSAGE_MAP()

     }; 

     //{{AFX_INSERT_LOCATION}}

     // Microsoft Visual C++ will insert additional declarations immediately before the previous line. 

     #endif // !defined(AFX_SETTING_H__23ABDE52_3A69_456A_A9DC_23A586A6699A__INCLUDED_) 

     // Setting.cpp : implementation file

     #include "stdafx.h"

     #include "Kurs_Lipin.h"

     #include "Setting.h"

     #include "Kurs_Lipin.h"

     #include "Kurs_LipinDlg.h" 

     #ifdef _DEBUG

     #define new DEBUG_NEW

     #undef THIS_FILE

     static char THIS_FILE[] = __FILE__;

     #endif 

     /////////////////////////////////////////////////////////////////////////////

     // CSetting dialog 

     CSetting::CSetting(CKurs_LipinDlg* pParent)

     : CDialog(CSetting::IDD, pParent)

     {

     f_start=false;

     parent = pParent;

     //{{AFX_DATA_INIT(CSetting)

     // NOTE: the ClassWizard will add member initialization here

     //}}AFX_DATA_INIT

     } 

     void CSetting::DoDataExchange(CDataExchange* pDX)

     {

     CDialog::DoDataExchange(pDX);

     //{{AFX_DATA_MAP(CSetting)

     // NOTE: the ClassWizard will add DDX and DDV calls here

     //}}AFX_DATA_MAP

     } 

     BEGIN_MESSAGE_MAP(CSetting, CDialog)

     //{{AFX_MSG_MAP(CSetting)

     //}}AFX_MSG_MAP

     END_MESSAGE_MAP() 

     /////////////////////////////////////////////////////////////////////////////

     // CSetting message handlers 

     BOOL CSetting::OnInitDialog()

     {

     CDialog::OnInitDialog();

     myFont.CreateFont(11,0,0,0,0,false,false,false,0,0,0,0,0,"Courier Cyr"); 

     int count=1, w=30,h=20,x0=45,y0=10;

     for (int i=0; i < 29; i++)

     {

     for (int j=i; j < 29; j++)

     {

     if (i == j)

     {

     t_edit[i][j].Create (WS_CHILD|WS_VISIBLE | WS_TABSTOP | WS_DLGFRAME|TA_LEFT,

     CRect(j*w+x0-35,i*h+y0,(j+1)*w-1+x0,(i+1)*h-1+y0),this,100); 

     t_edit[i][j].SetFont (&myFont);

     t_edit[i][j].SetWindowText(parent->name_city[i]);

     t_edit[i][j].SetReadOnly ();

     }

     else

     {

     t_edit[i][j].Create (WS_CHILD|WS_VISIBLE | WS_TABSTOP | WS_DLGFRAME,

     CRect(j*w+x0,i*h+y0,(j+1)*w-1+x0,(i+1)*h-1+y0),this,100);//count++); 

     t_edit[i][j].SetFont (&myFont);

     t_edit[i][j].SetLimitText(4);

     }

     }

     } 

     CStdioFile f1;

     f1.Open("table.ini",CFile::modeRead);

       for ( i=0; i < 29; i++)

     {

     CString s1;

     f1.ReadString(s1);

     int j=i+1;

     int k=0;

     while (j<29 && k < s1.GetLength())

     {CString s2;

     while (s1[k] == ' ') k++;

     while (s1[k] != ' ')

     {   s2 += s1[k];    k++;}

     t_edit[i][j].SetWindowText(s2);

     j++;

     }

     } 

     Proverka();

     return TRUE;  // return TRUE unless you set the focus to a control

     // EXCEPTION: OCX Property Pages should return FALSE

     } 

     void CSetting::OnOK()

     {

     Proverka();

     CStdioFile f1;

     f1.Open("table.ini",CFile::modeCreate | CFile::modeWrite);

     for (int i=0; i < 29; i++)

     {

     parent->tableAllCity[i][i]=0;

     CString s1;

     for (int j=i+1; j < 29; j++)

     {

     CString s2;

     t_edit[i][j].GetWindowText(s2);

     parent->tableAllCity[j][i]=parent->tableAllCity[i][j]=atoi(s2); 

     s1 += s2+" ";

     } s1 += "\n";

     f1.WriteString(s1);

     }

     MessageBox("Введённые  параметры проверены на ошибки  и сохранены.");

     CDialog::OnCancel ();

     } 

     void CSetting::Proverka()

     {

       for (int i=0; i < 29; i++)

     {

     for (int j=i+1; j < 29; j++)

     {

     CString s1;

     t_edit[i][j].GetWindowText(s1);

     if (!s1.IsEmpty())

     {

     for (int k=0; k < s1.GetLength(); k++)

     if (s1[k]<'0' || s1[k]>'9') {s1.Delete(k,1);k--;}

     if (s1.IsEmpty()) s1='0'; 

     }

     else s1='0';

     t_edit[i][j].SetWindowText(s1);

     }

     }

     }

Информация о работе Программная реализация метода ветвей и границ