?? tspdlg.cpp
字號:
// tspDlg.cpp : implementation file
//
#include "stdafx.h"
#include "tsp.h"
#include "tspDlg.h"
#include "math.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)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CTspDlg dialog
CTspDlg::CTspDlg(CWnd* pParent /*=NULL*/)
: CDialog(CTspDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CTspDlg)
m_nc = 50;
m_antnum = 10;
m_rou = 0.1;
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CTspDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CTspDlg)
DDX_Text(pDX, IDC_EDIT1, m_nc);
DDX_Text(pDX, IDC_EDIT2, m_antnum);
DDV_MinMaxInt(pDX, m_antnum, 0, 30);
DDX_Text(pDX, IDC_EDIT4, m_rou);
DDV_MinMaxDouble(pDX, m_rou, 0., 1.);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CTspDlg, CDialog)
//{{AFX_MSG_MAP(CTspDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDOK2, OnOk2)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CTspDlg message handlers
BOOL CTspDlg::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
// TODO: Add extra initialization here
MoveWindow(0,0,800,600);
CenterWindow();
chushihua();
if(citynum==0)
{
openflag=0;
MessageBox("數據不正確，請檢查。");
}
// if(openflag==1) CDialog::OnOK();
return TRUE; // return TRUE unless you set the focus to a control
}
void CTspDlg::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 CTspDlg::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 dc(this);
dc.Rectangle(250,50,650,450);
if(openflag!=0)
{
dc.FillSolidRect(250,450,650,600,RGB(236,233,216));
CString aa;
aa.Format("城市數目：%d",citynum);
dc.TextOut(250,450,aa,strlen(aa));
draw();
}
CDialog::OnPaint();
}
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CTspDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CTspDlg::chushihua()
{
CStdioFile file;
CString data;
if(file.Open("chengshi.txt",CStdioFile::modeReadWrite)==TRUE)
{
file.ReadString(data);
citynum=0;
int num=0,a=0;
file.ReadString(data);
for(;data.IsEmpty()==0;)
{
char temp[50],temp1[10];
for(int i=0;i<data.GetLength();i++)
{
temp[i]=data.GetAt(i);
if(i>=50) break;
}
for(int j=0;j<=i;j++)
{
if(temp[j]<='9' && temp[j]>='0')
temp1[j]=temp[j];
else break;
}
if(j!=0)
{
temp1[j]='\0';
bianhao[citynum]=atoi(temp1);
for(;j<=i;j++)
{
if(temp[j]<='9' && temp[j]>='0')
{
temp1[a++]=temp[j++];
break;
}
}
for(;j<=i;j++)
{
if(temp[j]<='9' && temp[j]>='0')
temp1[a++]=temp[j];
else break;
}
temp1[a]='\0';
point[citynum].x=atoi(temp1);
a=0;
for(;j<=i;j++)
{
if(temp[j]<='9' && temp[j]>='0')
{
temp1[a++]=temp[j++];
break;
}
}
for(;j<=i;j++)
{
if(temp[j]<='9' && temp[j]>='0')
temp1[a++]=temp[j];
else break;
}
temp1[a]='\0';
point[citynum].y=atoi(temp1);
a=0;
/* CString dd;
dd.Format("%d %d %d",bianhao[citynum],point[citynum].x,point[citynum].y);
MessageBox(dd);*/
if(point[citynum].x<100 && point[citynum].x>0 && point[citynum].y<100 && point[citynum].y>0)
citynum++;
}
for(int b=0;b<30;b++) temp[b]='\0';
file.ReadString(data);
}
file.Close();
openflag=1;
}
else
{
MessageBox("無法打開數據文件，無法初始化。");
openflag=0;
}
}
void CTspDlg::OnOK()
{
// TODO: Add extra validation here
if(citynum>3)
CTspDlg::astsp();
else MessageBox("城市數目太少.");
// CDialog::OnOK();
}
void CTspDlg::draw()
{
int x1,y1,x2,y2;
CString dd;
CClientDC dc(this);
dc.Rectangle(250,50,650,450);
CPen pen(0,10,RGB(0,0,255));
dc.SelectObject(&pen);
//dc.Rectangle(50,50,450,450);
for(int i=0;i<citynum;i++)
{
x1=249+point[i].x*4;
y1=49+point[i].y*4;
x2=251+point[i].x*4;
y2=51+point[i].y*4;
dc.Ellipse(x1,y1,x2,y2);
dd.Format("%d",bianhao[i]);
dc.TextOut(x1-5,y1+10,dd,strlen(dd));
}
for(i=0;i<citynum;i++)
for(int j=0;j<citynum;j++)
{
d[i][j]=(point[i].x-point[j].x)*(point[i].x-point[j].x)+
(point[i].y-point[j].y)*(point[i].y-point[j].y);
d[i][j]=pow((d[i][j]),0.5);
if(i==j) d[i][j]=0.05;
}
CPen pen1(0,10,RGB(255,0,0));
dc.SelectObject(&pen1);
dc.Ellipse((249+point[0].x*4),(49+point[0].y*4),
(251+point[0].x*4),(51+point[0].y*4));
dc.Ellipse((249+point[citynum-1].x*4),(49+point[citynum-1].y*4),
(251+point[citynum-1].x*4),(51+point[citynum-1].y*4));
}
/*用蟻群求解tsp問題*/
void CTspDlg::astsp()
{
UpdateData(TRUE);
draw();
int nc=0,m=m_antnum,i,j,numflag=0;
double c=0.05,alf=1,bt=1,rou=m_rou;
double tt[50][50],tt1[50][50],dtt[50][50];
double best=0,p[50];
int bestroad[50];
CString dd1;
//把輸入的路徑順序作為初始值
for( i=0;i<citynum;i++)
{
bestroad[i]=i;
if(i<citynum-2) best=d[i][i+1]+best;
}
//初始化信息素數組
for( i=0;i<citynum;i++)
for( j=0;j<citynum;j++)
{
tt[i][j]=c;
tt1[i][j]=1/d[i][j];
dtt[i][j]=0;
}
int tub[30][50];//禁忌表數組
for( ;nc<m_nc;nc++)
{
for( i=0;i<30;i++)
for( j=0;j<50;j++)
tub[i][j]=j;
for(i=1;i<citynum-1;i++)
{
for(j=0;j<m;j++)
{
//*******計算概率選出下個城市**********
double pnum=0;
for(int aa=i+1;aa<citynum-1;aa++)
{
p[aa]=pow(tt[tub[j][i]][tub[j][aa]],alf)
*pow(tt1[tub[j][i]][tub[j][aa]],bt);
pnum=pnum+p[aa];
}
for( aa=i+1;aa<citynum-1;aa++)
p[aa]=p[aa]/pnum;
double pp=random01();
for( aa=i+1;aa<citynum-1;aa++)
{
if(pp>p[aa])
p[aa+1]+=p[aa];
else
{
int cc=tub[j][i+1];
tub[j][i+1]=tub[j][aa];
tub[j][aa]=cc;
aa=citynum;
}
}
//*********已經選出下個城市****
double mmm=0;
for( aa=0;aa<=i;aa++)
mmm=d[tub[j][aa]][tub[j][aa+1]]+mmm;//計算螞蟻所走國的長度
dtt[tub[j][aa]][tub[j][aa+1]]+=citynum/mmm;
}//螞蟻循環完畢
//****更新信息素*******
for(int a=0;a<=citynum;a++)
for(int b=0;b<=citynum;b++)
{
tt[a][b]=(1-rou)*tt[a][b]+dtt[a][b];
dtt[a][b]=0;
}
}//城市循環結束
//*****計算個螞蟻的路徑長度******
for(i=0;i<m;i++)
{
double mmm=0;
for(j=0;j<citynum-1;j++)
mmm=d[tub[i][j]][tub[i][j+1]]+mmm;
if(mmm<best)
{
best=mmm;
for(j=0;j<citynum;j++) bestroad[j]=tub[i][j];
}
}
}//nc循環結束
//******畫線***************************
CClientDC dc(this);
CPen pen1(0,1,RGB(0,255,0));
dc.SelectObject(&pen1);
dc.MoveTo(point[bestroad[0]].x*4+250,point[bestroad[0]].y*4+50);
for(i=1;i<citynum;i++)
{
dc.LineTo(point[bestroad[i]].x*4+250,point[bestroad[i]].y*4+50);
}
//**************畫線結束******
//***************文字輸出*******
dc.FillSolidRect(250,450,650,600,RGB(236,233,216));
CString dd,aaa;
dd.Format("最優路徑長度 %f",best);
dc.TextOut(400,450,dd,strlen(dd));
dd.Format("路徑：%d",bianhao[bestroad[0]]);
for(i=1;i<citynum;i++)
{
aaa.Format("-%d",bianhao[bestroad[i]]);
dd+=aaa;
}
for(i=0;strlen(dd)>50;i++)
{
dc.TextOut(250,470,dd,50);
dd.Delete(0,50);
}
dc.TextOut(250,470+i*20,dd,strlen(dd));
dd.Format("城市數目：%d",citynum);
dc.TextOut(250,450,dd,strlen(dd));
//***********
}
double CTspDlg::random01()
{
int b=rand();
return double(b)/32767;
}
void CTspDlg::OnOk2() //更新城市數據
{
// TODO: Add your control notification handler code here
CClientDC dc(this);
chushihua();
if(citynum==0)
{
openflag=0;
MessageBox("數據不正確，請檢查。");
}
if(openflag!=0)
{
CString aa;
dc.FillSolidRect(250,450,650,600,RGB(236,233,216));
aa.Format("城市數目：%d",citynum);
dc.TextOut(250,450,aa,strlen(aa));
draw();
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -