Решение задачи о коммивояжере

Заключение

Был разработан алгоритм, позволяющий быстро найти кратчайший путь между городами. По алгоритму разработано приложение, решающее задачу о коммивояжере.

Литература

1. Круглински Д., Программирование на Microsoft Visual C++ 6.0 для профессионалов/Пер.с англ. –СПб:Питер; 2004г. – 861 с.: ил.

2. Беляев С.П. Курс лекций по «Исследованию операций

».

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

// Kurs_LipinDlg.h : headerfile

//

#if !defined(AFX_KURS_LIPINDLG_H FFEC63D9_17E7_4E43_805B_75F68CE9E55F INCLUDED_)

#define AFX_KURS_LIPINDLG_H FFEC63D9_17E7_4E43_805B_75F68CE9E55F INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

// CKurs_LipinDlg dialog

class CSetting;

class CKurs_LipinDlg : public CDialog

{

// Construction

public:

CKurs_LipinDlg(CWnd* pParent = NULL);// standard constructor

int koord[29][2],x0,y0;

bool flag_select[29];

bool flag_draw;

int count_selected, n;

int begin_point;

bool flag_Bpoint;

int **table;

int tableAllCity[29][29];

unsigned int *min_path;

int *sel_city;

CString name_city[29];

CFont myFont;

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

// Dialog Data

//{{AFX_DATA(CKurs_LipinDlg)

enum { IDD = IDD_KURS_LIPIN_DIALOG };

CListBoxm_list1;

CStaticm_label;

CStringm_len;

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CKurs_LipinDlg)

protected:

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

//}}AFX_VIRTUAL

// Implementation

protected:

HICON m_hIcon;

// Generated message map functions

//{{AFX_MSG(CKurs_LipinDlg)

virtual BOOL OnInitDialog();

afx_msg void OnSysCommand(UINT nID, LPARAM lParam);

afx_msg void OnPaint();

afx_msg HCURSOR OnQueryDragIcon();

afx_msg void OnLButtonDown(UINT nFlags, CPoint point);

afx_msg void OnButton2();

afx_msg void OnButton1();

virtual void OnOK();

afx_msg void OnButton3();

afx_msg void OnButton4();

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

};

//{{AFX_INSERT_LOCATION}}

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

#endif // !defined(AFX_KURS_LIPINDLG_H FFEC63D9_17E7_4E43_805B_75F68CE9E55F INCLUDED_)

// Kurs_LipinDlg.cpp : implementation file

//

#include "stdafx.h"

#include "Kurs_Lipin.h"

#include "Kurs_LipinDlg.h"

#include "math.h"

#include "Setting.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = FILE ;

#endif

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

// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog

{

public:

CAboutDlg();

// Dialog Data

//{{AFX_DATA(CAboutDlg)

enum { IDD = IDD_ABOUTBOX };

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CAboutDlg)

protected:

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

//}}AFX_VIRTUAL

// Implementation

protected:

//{{AFX_MSG(CAboutDlg)

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)

{

//{{AFX_DATA_INIT(CAboutDlg)

//}}AFX_DATA_INIT

}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CAboutDlg)

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)

//{{AFX_MSG_MAP(CAboutDlg)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

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

// CKurs_LipinDlg dialog

CKurs_LipinDlg::CKurs_LipinDlg(CWnd* pParent /*=NULL*/)

: CDialog(CKurs_LipinDlg::IDD, pParent)

{

//{{AFX_DATA_INIT(CKurs_LipinDlg)

m_len = _T("");

//}}AFX_DATA_INIT

// Note that LoadIcon does not require a subsequent DestroyIcon in Win32

m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

void CKurs_LipinDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CKurs_LipinDlg)

DDX_Control(pDX, IDC_LIST1, m_list1);

DDX_Control(pDX, IDC_STATIC1, m_label);

DDX_Text(pDX, IDC_STATIC1, m_len);

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CKurs_LipinDlg, CDialog)

//{{AFX_MSG_MAP(CKurs_LipinDlg)

ON_WM_SYSCOMMAND()

ON_WM_PAINT()

ON_WM_QUERYDRAGICON()

ON_WM_LBUTTONDOWN()

ON_BN_CLICKED(IDC_BUTTON2, OnButton2)

ON_BN_CLICKED(IDC_BUTTON1, OnButton1)

ON_BN_CLICKED(IDC_BUTTON3, OnButton3)

ON_BN_CLICKED(IDC_BUTTON4, OnButton4)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

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

// CKurs_LipinDlg message handlers

BOOL CKurs_LipinDlg::OnInitDialog()

{

CDialog::OnInitDialog();

// Add "About ." menu item to system menu.

// IDM_ABOUTBOX must be in the system command range.

ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);

ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);

if (pSysMenu != NULL)

{

CString strAboutMenu;

strAboutMenu.LoadString(IDS_ABOUTBOX);

if (!strAboutMenu.IsEmpty())

{

pSysMenu->AppendMenu(MF_SEPARATOR);

pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

// Set the icon for this dialog. The framework does this automatically

// when the application's main window is not a dialog

SetIcon(m_hIcon, TRUE);// Set big icon

SetIcon(m_hIcon, FALSE);// Set small icon

name_city[0] = "С.-Петербург";

name_city[1] = "Псков";

name_city[2] = "Новгород";

name_city[3] = "Смоленск";

name_city[4] = "Тверь";

name_city[5] = "Вологда";

name_city[6] = "Ярославль";

name_city[7] = "Кострома";

name_city[8] = "Москва";

name_city[9] = "Брянск";

name_city[10] = "Калуга";

name_city[11] = "Иваново";

name_city[12] = "Орел";

name_city[13] = "Тула";

name_city[14] = "Владимир";

name_city[15] = "Курск";

name_city[16] = "Рязань";

name_city[17] = "Белгород";

name_city[18] = "Липецк";

name_city[19] = "Н.Новгород";

name_city[20] = "Воронеж";

name_city[21] = "Тамбов";

name_city[22] = "Чебоксары";

name_city[23] = "Саранск";

name_city[24] = "Пенза";

name_city[25] = "Ульяновск";

name_city[26] = "Саратов";

name_city[27] = "Самара";

 Скачать реферат