📄 tsp.cpp
字号:
// TSP.cpp : Defines the entry point for the application.
//
#include "stdafx.h"
#include "resource.h"
#include <stdio.h>
#include <math.h>
#define MAX_LOADSTRING 100
#define A 0.500 //500
#define B 0.500 //500
#define C 0.200 //200
#define D 0.0005
#define x0 0.02
#define N 10 // the number of cities
#define Ri 1.0
#define Dt 0.01
#define delta_x 0.01
#define e 2.87
#define delta_v 0.001
#define MaxTimes 10000
#define OPTI_LENGTH 32.0
#define side 0.7
// Global Variables:
HINSTANCE hInst; // current instance
TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING]; // The title bar text
double pre_v_array[N+1][N+1];
double v_array[N+1][N+1];
double x_array[N+1][N+1];
double d_array[N+1][N+1];
double points_array[5][2];
/*{
(0.4000, 0.4439),
(0.2439, 0.1463),
(0.1707, 0.2293),
(0.2293, 0.7610),
(0.5171, 0.9414),
(0.8732, 0.6536),
(0.6878, 0.5219),
(0.8488, 0.3609),
(0.6683, 0.2536),
(0.6195, 0.2634)};
*/
int draw_times;
double total_length;
// Foward declarations of functions included in this code module:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
LRESULT CALLBACK About(HWND, UINT, WPARAM, LPARAM);
void caculate_d(void);
void f_func(void);
double derivative(int x,int i);
void get_pre_v(void);
double get_bias_v(void);
void draw_cities (HWND hWnd, HDC hdc, int times);
void one_city(HDC hdc, int x, int y);
void inti_cites(void);
double get_length (void);
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
// TODO: Place code here.
MSG msg;
HACCEL hAccelTable;
// Initialize global strings
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_TSP, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
// Perform application initialization:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_TSP);
// Main message loop:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return msg.wParam;
}
//
// FUNCTION: MyRegisterClass()
//
// PURPOSE: Registers the window class.
//
// COMMENTS:
//
// This function and its usage is only necessary if you want this code
// to be compatible with Win32 systems prior to the 'RegisterClassEx'
// function that was added to Windows 95. It is important to call this function
// so that the application will get 'well formed' small icons associated
// with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, (LPCTSTR)IDI_TSP);
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = (LPCSTR)IDC_TSP;
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);
return RegisterClassEx(&wcex);
}
//
// FUNCTION: InitInstance(HANDLE, int)
//
// PURPOSE: Saves instance handle and creates main window
//
// COMMENTS:
//
// In this function, we save the instance handle in a global variable and
// create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance; // Store instance handle in our global variable
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//
// FUNCTION: WndProc(HWND, unsigned, WORD, LONG)
//
// PURPOSE: Processes messages for the main window.
//
// WM_COMMAND - process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
TCHAR szHello[MAX_LOADSTRING];
LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);
char cc[10000],ccTemp[1000];
int xx,ii,t;
long int Times;
double temp;
switch (message)
{
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:
switch (wmId)
{
case IDM_CACUL:
///////////// Initialize ///////////////////
inti_cites();
Times = 0;
total_length = 0.0;
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
x_array[xx][ii] = -0.5*x0*log(N+5-1) + delta_x*(rand())/0x7fff;
//////////// 步骤③-④-⑤ /////////////////
f_func();
do
{
get_pre_v();
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
x_array[xx][ii] += derivative(xx,ii)*Dt;
f_func();
Times++;
// temp = get_bias_v();
// sprintf(cc,"Bias_v=%1.9f",temp);
// MessageBox(hWnd,cc,"TSP",MB_OK);
} while( (get_bias_v()>delta_v) || (Times < 2000));
sprintf(cc, " TSP Caculation is completed! The Times=%ld ", Times);
MessageBox(hWnd,cc,"TSP",MB_OK);
break;
case IDM_V_MATRIX:
sprintf(cc,"V-MATRIX[x][i]:\n");
for (xx=1; xx<=N; xx++)
{
for (ii=1; ii<=N; ii++)
{
sprintf(ccTemp," %1.3f , ",v_array[xx][ii]);
strcat(cc,ccTemp);
}
strcat(cc,"\n");
}
MessageBox(hWnd,cc,"TSP",MB_OK);
break;
case IDM_DRAW:
hdc = GetDC(hWnd);
draw_times++;
draw_cities(hWnd,hdc,draw_times);
total_length = get_length();
sprintf(cc,"路程总长度=%1.5f.",total_length);
MessageBox(hWnd,cc,"TSP",MB_OK);
ReleaseDC(hWnd,hdc);
break;
case IDM_OPTI_TRACK:
///////////// Initialize ///////////////////
Times = 0;
total_length = 0.0;
inti_cites();
do{
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
x_array[xx][ii] = -0.5*x0*log(N+5-1) + delta_x*(rand()-0x3fff)/0x7fff;
//////////// 步骤③-④-⑤ /////////////////
f_func();
t=0;
do
{
get_pre_v();
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
x_array[xx][ii] += derivative(xx,ii)*Dt;
f_func();
t++;
// temp = get_bias_v();
// sprintf(cc,"Bias_v=%1.9f",temp);
// MessageBox(hWnd,cc,"TSP",MB_OK);
} while( (get_bias_v()>delta_v) || (t < 500));
Times++;
total_length = get_length();
} while(total_length>OPTI_LENGTH);
sprintf(cc, " TSP OPTI_Caculation is completed! The Times=%ld ", Times);
MessageBox(hWnd,cc,"TSP",MB_OK);
break;
case IDM_ABOUT:
DialogBox(hInst, (LPCTSTR)IDD_ABOUTBOX, hWnd, (DLGPROC)About);
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
// TODO: Add any drawing code here...
RECT rt;
GetClientRect(hWnd, &rt);
DrawText(hdc, szHello, strlen(szHello), &rt, DT_CENTER);
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
// Mesage handler for about box.
LRESULT CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_INITDIALOG:
return TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return TRUE;
}
break;
}
return FALSE;
}
///////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////
void inti_cites(void)
{
// points_array[0][0] =2.0; points_array[0][1] =6.0;
// points_array[1][0] =6.7; points_array[1][1] =10.0;
// points_array[2][0] =6.7; points_array[2][1] =2.5;
// points_array[3][0] =11.0; points_array[3][1] =1.8;
// points_array[4][0] =15.0; points_array[4][1] =6.0;
points_array[0][0] =0.4; points_array[0][1] =0.4439;
points_array[1][0] =0.2439; points_array[1][1] =0.1463;
points_array[2][0] =0.1707; points_array[2][1] =0.2293;
points_array[3][0] =0.2293; points_array[3][1] =0.7610;
points_array[4][0] =0.5171; points_array[4][1] =0.9414;
points_array[5][0] =0.8732; points_array[5][1] =0.6536;
points_array[6][0] =0.6878; points_array[6][1] =0.5219;
points_array[7][0] =0.8488; points_array[7][1] =0.3609;
points_array[8][0] =0.6683; points_array[8][1] =0.2536;
points_array[9][0] =0.6195; points_array[9][1] =0.2634;
/*
points_array[0][0] =0.2; points_array[0][1] =0.5;
points_array[1][0] =0.3; points_array[1][1] =0.4;
points_array[2][0] =0.4; points_array[2][1] =0.3;
points_array[3][0] =0.5; points_array[3][1] =0.4;
points_array[4][0] =0.6; points_array[4][1] =0.5;
points_array[5][0] =0.7; points_array[5][1] =0.6;
points_array[6][0] =0.6; points_array[6][1] =0.7;
points_array[7][0] =0.5; points_array[7][1] =0.7;
points_array[8][0] =0.4; points_array[8][1] =0.7;
points_array[9][0] =0.3; points_array[9][1] =0.6;
*/
caculate_d();
}
void caculate_d(void)
{
int xx,yy;
for (xx=1; xx<=N; xx++)
for (yy=1; yy<=N; yy++)
d_array[xx][yy] = sqrt( (points_array[xx-1][0]-points_array[yy-1][0]) * (points_array[xx-1][0]-points_array[yy-1][0]) + (points_array[xx-1][1]-points_array[yy-1][1]) * (points_array[xx-1][1]-points_array[yy-1][1]) );
}
void f_func(void)
{
int xx,ii;
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
{
v_array[xx][ii]=0.5*(1+tanh(x_array[xx][ii]/x0));
}
}
double derivative(int x, int i)
{
double v,va,vb,vc,vd,result;
int xx,yy,ii,jj;
v = x_array[x][i]/Ri;
va = 0.0;
vb = 0.0;
vc = 0.0;
vd = 0.0;
for (jj=1; jj<=N; jj++)
{
if (jj != i)
va += v_array[x][jj];
}
va *=A;
for (yy=1; yy<=N; yy++)
{
if (yy != x)
vb += v_array[yy][i];
}
vb *=B;
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
vc +=v_array[xx][ii];
vc = vc-N;
vc *=C;
for (yy=1; yy<=N; yy++)
vd +=d_array[x][yy]*(v_array[yy][i+1]+v_array[yy][i-1]);
vd *=D;
result = -(v+va+vb+vc+vd);
return result;
}
void get_pre_v (void)
{
int xx,ii;
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
{
pre_v_array[xx][ii] = v_array[xx][ii];
}
}
double get_bias_v (void)
{
int xx,ii;
double bias;
bias = 0.0;
for (xx=1; xx<=N; xx++)
for (ii=1; ii<=N; ii++)
{
bias += ( v_array[xx][ii] - pre_v_array[xx][ii] )*( v_array[xx][ii] - pre_v_array[xx][ii] );
}
bias = sqrt( bias );
return bias;
}
void draw_cities (HWND hWnd, HDC hdc, int times)
{
int xx,ii;
char cc[100];
int city_x,city_y, pre_city_x,pre_city_y, first_city_x,first_city_y;
for (ii=1; ii<=N; ii++)
{
for (xx=1; xx<=N; xx++)
{
if (v_array[xx][ii]>side)
{
city_x = (int)(500*points_array[xx-1][0]);
city_y = (int)(500*points_array[xx-1][1]);
sprintf(cc,"The %d step is the No %d city(%d,%d).",ii,xx,city_x,city_y);
// MessageBox(hWnd,cc,"TSP",MB_OK);
if (ii>1)
{
MoveToEx(hdc,pre_city_x,pre_city_y,NULL);
LineTo(hdc,city_x,city_y);
}
one_city(hdc,city_x,city_y);
pre_city_x = city_x;
pre_city_y = city_y;
if (ii==1)
{
first_city_x = city_x;
first_city_y = city_y;
}
}
}
}
MoveToEx(hdc,pre_city_x,pre_city_y,NULL);
LineTo(hdc,first_city_x,first_city_y);
}
void one_city(HDC hdc, int x, int y)
{
int r=5;
Ellipse(hdc,x-r,y+r,x+r,y-r);
}
double get_length (void)
{
int xx,ii;
double city_x,city_y, pre_city_x,pre_city_y, first_city_x,first_city_y;
double length;
length = 0.0;
for (ii=1; ii<=N; ii++)
{
for (xx=1; xx<=N; xx++)
{
if (v_array[xx][ii]>side)
{
city_x = points_array[xx-1][0];
city_y = points_array[xx-1][1];
if (ii>1)
{
length +=sqrt((city_x - pre_city_x)*(city_x - pre_city_x) + (city_y - pre_city_y)*(city_y - pre_city_y));
}
pre_city_x = city_x;
pre_city_y = city_y;
if (ii==1)
{
first_city_x = city_x;
first_city_y = city_y;
}
}
}
}
length +=sqrt((city_x - first_city_x)*(city_x - first_city_x) + (city_y - first_city_y)*(city_y - first_city_y));
return length;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -