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

 

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

 

// Kurs_LipinDlg.h : header file

//

 

#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] = "Самара";

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

 

x0=10;y0=10;// смещение  карты относительно левого верхнего  угла окна

koord[0][0]=x0+225;// Санкт-Петербург

koord[0][1]=y0+54;

koord[1][0]=x0+148; //Псков

koord[1][1]=y0+60;

koord[2][0]=x0+195;  // Новгород

koord[2][1]=y0+92;

koord[3][0]=x0+93;  // Смоленск

koord[3][1]=y0+171;

koord[4][0]=x0+191; //Тверь

koord[4][1]=y0+193;

koord[5][0]=x0+301;  //Вологда

koord[5][1]=y0+200;

koord[6][0]=x0+261;  //Ярославль

koord[6][1]=y0+231;

koord[7][0]=x0+279;//Кострома

koord[7][1]=y0+248;

koord[8][0]=x0+181;//Москва

koord[8][1]=y0+241;

koord[9][0]=x0+76;//Брянск

koord[9][1]=y0+240;

koord[10][0]=x0+133;//Калуга

koord[10][1]=y0+245;

koord[11][0]=x0+256;//Иваново

koord[11][1]=y0+264;

koord[12][0]=x0+88;//Орел

koord[12][1]=y0+275;

koord[13][0]=x0+139;//Тула

koord[13][1]=y0+272;

koord[14][0]=x0+227;//Владимир

koord[14][1]=y0+274;

koord[15][0]=x0+55;//Курск

koord[15][1]=y0+297;

koord[16][0]=x0+176;//Рязань

koord[16][1]=y0+297;

koord[17][0]=x0+29;//Белгород

koord[17][1]=y0+328;

koord[18][0]=x0+121;//Липецк

koord[18][1]=y0+338;

koord[19][0]=x0+276;//Нижний  Новгород

koord[19][1]=y0+322;

koord[20][0]=x0+92;//Воронеж

koord[20][1]=y0+353;

koord[21][0]=x0+149;//Тамбов

koord[21][1]=y0+364;

koord[22][0]=x0+307;//Чебоксары

koord[22][1]=y0+373;

koord[23][0]=x0+237;//Саранск

koord[23][1]=y0+388;

koord[24][0]=x0+212;//Пенза

koord[24][1]=y0+408;

koord[25][0]=x0+280;//Ульяновск

koord[25][1]=y0+429;

koord[26][0]=x0+184;//Саратов

koord[26][1]=y0+456;

koord[27][0]=x0+292;//Самара

koord[27][1]=y0+491;

koord[28][0]=x0+91;//Волгоград

koord[28][1]=y0+506;

 

count_selected=0;

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

m_len="Выберите  несколько городов.";

m_label.SetFont (&myFont);

UpdateData(false);

 

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

flag_select[i]=false;

flag_draw=false;

begin_point = -1;

flag_Bpoint=false;

 

 

CStdioFile f1;

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

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

{

tableAllCity[i][i]=0;

 

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++;}

tableAllCity[j][i]=tableAllCity[i][j]=atoi(s2);

j++;

}

}

 

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

}

 

void CKurs_LipinDlg::OnSysCommand(UINT nID, LPARAM lParam)

{

if ((nID & 0xFFF0) == IDM_ABOUTBOX)

{

CAboutDlg dlgAbout;

dlgAbout.DoModal();

}

else

{

CDialog::OnSysCommand(nID, lParam);

}

}

 

// If you add a minimize button to your dialog, you will need the code below

//  to draw the icon.  For MFC applications using the document/view model,

//  this is automatically done for you by the framework.

 

void CKurs_LipinDlg::OnPaint()

{

if (IsIconic())

{

CPaintDC dc(this); // device context for painting

 

SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

 

// Center icon in client rectangle

int cxIcon = GetSystemMetrics(SM_CXICON);

int cyIcon = GetSystemMetrics(SM_CYICON);

CRect rect;

GetClientRect(&rect);

int x = (rect.Width() - cxIcon + 1) / 2;

int y = (rect.Height() - cyIcon + 1) / 2;

 

// Draw the icon

dc.DrawIcon(x, y, m_hIcon);

}

else

{

CClientDC pDC(this);

CDC temp;

CBitmap bmp;

bmp.LoadBitmap(IDB_BITMAP1);

temp.CreateCompatibleDC (&pDC);

temp.SelectObject(bmp);

 

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

{

if (flag_select[j])

{

int x=koord[j][0]-x0;

int y=koord[j][1]-y0;

 

temp.SelectStockObject (BLACK_BRUSH);

temp.Ellipse(x-3,y-3,x+3,y+3);

}

}

if (begin_point>=0)

{

int x=koord[begin_point][0]-x0;

int y=koord[begin_point][1]-y0;

CBrush br (RGB(255,0,0));

temp.SelectObject (&br);

temp.Ellipse(x-4,y-4,x+4,y+4);

 

}

 

if (flag_draw)

{

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

{

int x1 = koord[sel_city[min_path[i]-1]][0];

int x2 = koord[sel_city[min_path[i+1]-1]][0];

int y1 = koord[sel_city[min_path[i]-1]][1];

int y2 = koord[sel_city[min_path[i+1]-1]][1];

 

temp.MoveTo(x1-x0,y1-y0);

temp.LineTo(x2-x0,y2-y0);

}

 

CString s1;

 

m_list1.ResetContent();

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

{

s1=name_city[sel_city[min_path[i]-1]];

s1+=" - "+name_city[sel_city[min_path[i+1]-1]];

CString s2;

s2.Format("%d",table[min_path[i]-1][min_path[i+1]-1]);

s1+=" ->"+s2;

m_list1.AddString(s1);

 

}

m_len.Format("Длина пути:\n%d км",min_path[n+1]);

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

{

if (i % 2 != 0) m_list1.SetSel(i);

}

}

else

{

m_len="Выберите  несколько городов.";

 

}

UpdateData(false);

 

pDC.BitBlt(x0,y0,638,638,&temp,0,0,SRCCOPY);

 

CDialog::OnPaint();

}

}

 

// The system calls this to obtain the cursor to display while the user drags

//  the minimized window.

HCURSOR CKurs_LipinDlg::OnQueryDragIcon()

{

return (HCURSOR) m_hIcon;

}

 

void CKurs_LipinDlg::OnLButtonDown(UINT nFlags, CPoint point)

{

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

{

int x=point.x-koord[i][0],y=point.y-koord[i][1];

if((x*x+y*y)<=7*7)

{

if (flag_Bpoint)

{

if (count_selected >= 13 && flag_select[i]==false)

{

MessageBox ("Нельзя  выбрать более 13 городов !!!\nВыберите  выделенный город или снимите  выделение \nс одного города  и поставьте на другом.");

flag_Bpoint=false;

Invalidate(false);

}

else

{

begin_point=i;

flag_Bpoint=false;

if (flag_select[i]==false) count_selected++;

 

flag_select[i]=true;

flag_draw=false;

Invalidate(false);

}

}

else

{

if (count_selected >= 13 && flag_select[i]==false)

{

MessageBox ("Нельзя  выбрать более 13 городов !!!");

}

else

{

if (flag_select[i]==false) count_selected++;

else

{

count_selected--;

if (i == begin_point)

{

begin_point=-1;

}

}

flag_select[i]=!flag_select[i];

flag_draw=false;

Invalidate(false);

}

}

}

}

CDialog::OnLButtonDown(nFlags, point);

}

 

void CKurs_LipinDlg::OnButton1()

{

m_list1.ResetContent();

 

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

flag_select[i]=false;

flag_select[6]=true;

flag_select[8]=true;

flag_select[12]=true;

flag_select[13]=true;

flag_select[15]=true;

flag_select[18]=true;

flag_select[19]=true;

flag_select[20]=true;

flag_select[21]=true;

flag_select[26]=true;

flag_select[27]=true;

flag_select[28]=true;

flag_select[24]=true;

count_selected=13;

flag_draw=false;

flag_Bpoint = false;

begin_point = -1;

 

 

Invalidate(false);

 

}

 

void CKurs_LipinDlg::OnButton2()

{

m_list1.ResetContent();

 

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

flag_select[i]=false;

flag_Bpoint = false;

begin_point = -1;

count_selected = 0;

flag_draw = false;

Invalidate (false);

 

}

 

void CKurs_LipinDlg::OnOK()

{

m_list1.ResetContent();

 

n = count_selected;

 

if (n <=1)

{

MessageBox ("Пожалуйста, выберите не менее 2 городов.");

return;

}

sel_city= new int[n];

int count = 0;

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

if (flag_select[i]) sel_city[count++] = i;

 

for (i=0; i < n; i++)// ставим исходный город на первое  место в массиве

if (sel_city[i] == begin_point)

{

int tmp = sel_city[0];

sel_city[0] = sel_city[i];

sel_city[i] = tmp;

}

 

table = new int *[n];

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

table[i] = new int [n];

 

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

  for (int j = 0; j < n; j++)

  {

if (i>=j)

{

table[i][j]=table[j][i]=tableAllCity[sel_city[i]][sel_city[j]];

}

  }

 

bool *flag = new bool[n];      //  заполнение признаков посещения  городов

flag[0] = true;

for (i=1; i < n; i++) flag[i]=false;

 

unsigned int *cur_path = new unsigned int[n+2];

min_path = new unsigned int[n+2];

 

//  заполнение  матриц минимального пути и текущего пути

min_path[0] = min_path[n]=1;    min_path[n+1]=0;

for (i=1; i < n; i++)

{

min_path[i]=i+1;  min_path[n+1]+=table[i-1][i];

cur_path[i]=0;

}  min_path[n+1] += table [min_path[n-1]-1] [min_path[n]-1 ];

 

cur_path[n+1] =0;

cur_path[0] = cur_path[n] = 1;

 

m_len="Пожалуйста, подождите:\nидут вычисления...";

UpdateData(false);

 

recursiv (flag,cur_path, 1);    // вызов рекурсивной функции*/

 

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]);