TSP问题,模拟退火,有图形界面,windowsAPI

 TSP测试数据:2391

编译器:TinyC 或者GCC均可

测试平台:windows

图形界面:winapi

编译命令:

        gcc的:gcc -Wall -lm test.c -o test.exe -mwindows

        tinyC的:tcc test.c -o test.exe

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <windows.h> #define N 3 #define L 2391 const char file_name[50]="tsp2391.tsp"; double data[N-1][L]; double t=100.0; double t0=1; double lenth=0; int loop=L; double tdown=0.8; void initData(); double dis(int,int); void ifaccept(int,int); void swap(int,int); void anneal(); double sumlen(); void makedata() { initData(); anneal(); sumlen(); } void initData() { FILE *fp; double temp; int count = 0; if((fp=fopen(file_name, "rb")) == NULL) { printf("File dose not exist\n"); exit(1); } while(1==fscanf(fp, "%lf", &temp)) { if(count%N) { data[count%N-1][count/N] = temp; } count++; } fclose(fp); } double dis(int i,int j) { double square=(data[0][i]-data[0][j])*(data[0][i]-data[0][j])+(data[1][i]-data[1][j])*(data[1][i]-data[1][j]); return sqrt(square); } double sumlen() { int i; lenth=0; for(i=0;i<L;i++) lenth+=dis(i,(i+1)%L); return lenth; } void ifaccept(int i,int j) { double d=sumlen(); swap(i,j); double dnew=sumlen(); if(dnew>d) { if((double)(rand()%1000)/1000.0>exp((d-dnew)/t)) swap(i,j); } } void swap(int i,int j) { double temp[N-1]={data[0][i],data[1][i]}; data[0][i]=data[0][j]; data[1][i]=data[1][j]; data[0][j]=temp[0]; data[1][j]=temp[1]; } void anneal() { int i,j,k; while(t>t0) { for(k=0;k<loop;k++) { i=rand()%L; j=rand()%L; ifaccept(i,j); } t=t*tdown; } } LRESULT CALLBACK WndProc(HWND hWnd, UINT iMsg, UINT wParam, LONG lParam) { HDC hDC; HBRUSH hBrh; HPEN hPen; PAINTSTRUCT ptStr; // 定义绘图信息结构体 POINT oldPt; TCHAR szBuffer[40] ; int i; switch (iMsg) { case WM_PAINT: // 处理绘图信息 hDC = BeginPaint(hWnd, & ptStr); // 获取设备上下文 SetMapMode(hDC, MM_TEXT); // 设置映射模式 hPen = (HPEN)GetStockObject(BLACK_PEN); // 获取默认黑色画笔 SelectObject(hDC, hPen); // 将画笔选入 设备上下文 hBrh = (HBRUSH)(GetStockObject(DKGRAY_BRUSH)); // 深灰色画刷 SelectObject(hDC, hBrh); TextOut(hDC,5, 5,szBuffer,wsprintf(szBuffer,TEXT(" 最短路径是：%d"),(int)lenth)); for(i=0;i<L;i++) { MoveToEx(hDC,data[0][i]/15,data[1][i]/30, & oldPt); LineTo(hDC,data[0][(i+1)%L]/15,data[1][(i+1)%L]/30); } EndPaint(hWnd, & ptStr); // 结束绘图 return 0 ; case WM_DESTROY: PostQuitMessage( 0 ); return 0 ; default : // 其它消息的默认处理函数 return (DefWindowProc(hWnd, iMsg, wParam, lParam)); } } // 对窗口进行初始化 BOOL InitWindow(HINSTANCE hInst, int nCmdShow) { makedata(); HWND hWnd; hWnd = CreateWindow( " WinFill " , " TSP by HIt9" ,WS_SYSMENU, 0 , 0 ,CW_USEDEFAULT, CW_USEDEFAULT,NULL, NULL,hInst,NULL); if ( ! hWnd) { return FALSE; } ShowWindow(hWnd, nCmdShow); UpdateWindow(hWnd); return TRUE; } BOOL InitWindowClass(HINSTANCE hInst) { WNDCLASS wndClass; wndClass.cbClsExtra = 0 ; wndClass.cbWndExtra = 0 ; wndClass.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH); wndClass.hCursor = LoadCursor(NULL, IDC_ARROW); wndClass.hIcon = LoadIcon(NULL, " END " ); wndClass.hInstance = hInst; wndClass.lpfnWndProc = WndProc; wndClass.lpszClassName = " WinFill " ; wndClass.lpszMenuName = " NULL " ; wndClass.style = CS_HREDRAW | CS_VREDRAW; return RegisterClass( & wndClass); } int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,LPSTR lpCmdLine,int nCmdShow) { MSG msg; if ( ! InitWindowClass(hInstance)) { return FALSE; } if ( ! InitWindow(hInstance, nCmdShow)) { return FALSE; } while (GetMessage( & msg, 0 , 0 , 0 )) { TranslateMessage( & msg); DispatchMessage( & msg); } return msg.wParam; }