183655 (Решение задачи о коммивояжере), страница 3

{

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

table[i] = new int [n];

for (i=0; 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]);

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]'9') {s1.Delete(k,1);k--;}

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

}

else s1='0';

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

}

}

}