旅行商问题，简称TSP问题。数学描述为：在一个有权无向图中寻找一条最短的哈密顿回路。意思就是需要在每一条边上都有权值的图（一般情况下边上的权值就是边的几何长度，当然在拓扑图的意义上未必如此）中找一条经过所有节点且每个节点仅经过一次的回路，而且这个回路是所有满足该条件的回路中最短的。
旅行商问题目前没有解析解法，即没有固定的算法，可以稳定地在所有有权无向图中找到最短哈密顿回路（找最短欧拉回路的解析方法是有的）。因为这个原因，旅行商问题成为了组合优化的经典问题，也是很多启发式算法可用的经典示例。
在最后介绍的两种非经典算法，蚁群算法及模拟退火算法中，我们将以旅行商问题为例。在此之前，在这里先给出旅行商问题的贪心算法解。
贪心算法是解决旅行商问题最直接的考虑，即完全地局部寻优。意思就是，在每一个位置，旅行商都找最近能到的点，不重复走，直到完成一个哈密顿回路。贪心算法当然是不能确保找到真正最小的哈密顿回路的（其实智能算法也做不到，但能找到比贪心算法好的）。理论上贪心算法一定会陷入局部最优，即使找到全局最优也是偶然。
在以后将给出的蚁群算法及模拟退火算法中，我们使用的都是同一个图。下面给出的程序列举了从所有点起始的贪心算法找到的最小哈密顿回路，并找到了这些回路中最短的一条。下面智能算法的目标即是超越贪心算法，只要一个智能算法在这个图中能稳定地找到比贪心算法能找到的最短回路还小的回路，这个算法就是成功的。
问题中涉及的图是：坐标数据可以在下面的程序中找到，这里图边的权值即是边的几何长度
下面给出实现贪心算法的程序，C++语言编写，包括两个文件，head.h和main.cpp。在C++空项目中填入这两个文件算法即能运行。
head.h中包括需要的系统头文件和问题描述及算法中的常量：
#include
#include
#include
#include
#include
#include
#definen52//城市规模
//城市横坐标数组
doubleML_x[n]=
{565,25,345,945,845,880,25,525,580,650,1605,1220,1465,1530,845,725,145,415,510,560,
300,520,480,835,975,1215,1320,1250,660,410,420,575,1150,700,685,685,770,795,720,760,
475,95,875,700,555,830,1170,830,605,595,1340,1740};
//城市纵坐标数组
doubleML_y[n]=
{575,185,750,685,655,660,230,1000,1175,1130,620,580,200,5,680,370,665,635,875,365,
465,585,415,625,580,245,315,400,180,250,555,665,1160,580,595,610,610,645,635,650,
960,260,920,500,815,485,65,610,625,360,725,245};
doublemound[n][n];//城市间距离矩阵
voidinit_mound_matrix(double*X,double*Y,double(*M)[n])//城市间距离计算方法
{
for(inti=0;i for(intj=0;j if(i==j)M[i][j]=0; elseM[i][j]=sqrt(pow((X[i]-X[j]),2)+pow((Y[i]-Y[j]),2)); } mian.cpp中是算法主体和程序入口： /**********************/ /******贪心算法******/ #include"head.h" introute[n][n+1];//全部贪心路径记录 introute_best[n+1];//最佳贪心路径记录 doublelength[n];//各贪心路径长度 doublelength_best;//最佳贪心路径长度 intmain() init_mound_matrix(ML_x,ML_y,mound); for(inti=0;i for(intk=0;k intLOC=k;//当前位置变量 intrecord[n+1];//反重走记录 for(inti=0;i record[LOC]=1;//记录初始位置已走过 intindex;//最佳位置的序号 doubled;//到最近位置的长度 route[k][0]=LOC;//记录初始位置 //依据贪心法则寻找路径 if(i==n-1)record[LOC]=0;//走到最后一步时，允许走回初始位置 d=100000; if(mound[route[k][i]][j] index=j; d=mound[route[k][i]][j]; route[k][i+1]=index; record[index]=1; //显示从k点出发找到的贪心路径 for(inti=0;i std::cout<<"\n"; for(inti=0;i std::cout<<"length:"< //从长度记录中找到最短长度，并找到它的序号 length_best=length[0]; inttemp=0; if(length[i] length_best=length[i]; temp=i; //显示最短贪心路径及其长度 std::cout<<"———————————————————————————"; std::cout<<"\n\n"; for(inti=0;i for(inti=0;i std::cout<<"length_best:"< return0; 程序报告的结果：（结果可以秒出，后面两个算法需要10到20秒） 上面看不到的部分是贪心算法从0到51各点起始找到的最短路径，最后报告的是这些回路中最短的一条，从点“39”出发，由贪心算法找到的序列，它的长度是8182.19，在后续的算法中我们将在这张图中找到比这条回路更短的哈密顿回路，以显示智能算法的能力。