1. Question
强行科普一下TSP问题问题。
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
也就是说，假设在一个无向图中，找到一条路径，从某个点出发，遍历所有的点一次且仅一次，最后回到起始点，要求所求路径最短。
2. Answer
对于TSP问题一般是由动态规划法实现，而使用贪心法将会得到非最优解，这也就不能算是解决了TSP问题，所以说贪心法回答这个问题仅能满足前半部分。
举个简单的栗子。
这里说明一下，由于我用的作图软件的问题，线条不太好弄，所以我用箭头代替了，但是无向图里又没有方向，看的时候可以忽略箭头，想象成一条线。
图中红色的线代表了贪心算法的运行结果。
假设从点1出发,按照贪心（最短）的思想来找，总是寻找与上一个点相连的最短的未被访问的点（每个点只能访问一次，所以访问过了的，我们就不考虑了）。
- 1 -> 4 （1到4是1-2，1-3，1-4，1-5 中最短的，为2）
- 4 ->3 （4到3是4-2，4-3，4-5中最短的，为2）
- 3 -> 5 （3到5 是 3-2，3-5中最短的，为5）
- 5 -> 2 （2是唯一剩下没被访问结点，直接选择5-2）
- 2 -> 1 （最后要回到原点）
所以我们得到的贪心路径是
1->4->3->5->2->1 长度为2+2+2+5+3 = 14
But！
最优解不是它。
我们可以看看1->2->5->4->3->1 长度是3+2+3+2+3 = 13，所以说贪心算法能否得到最优解或者是否接近最优解是不能保证的。
3.Code
那么要怎么实现？
其实看起来复杂，实际上并不难实现。
假设从某点开始访问，访问过的就标志为1，没有访问的就标志为0，设置一个计数器，判断直到选择的点够数了为止。
如何选？
就是一个比较的过程，假设现在在a点，我要去下一个地点，那么遍历所有与a点相连接的点，比较a与某点的路径长度，选出一个最小的，且没被访问的作为终点即可。
代码如下:
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class TspGreedy {
final static int MAX = 1000;
private static int[][] arc;
public static void main(String[] args) throws Exception{
createGraph(); //创建图
showGraph();
tsp_greedy(1); //传入起始操作点（按点的标号开始算）
}
//贪心-TSP
private static void tsp_greedy(int w) {
/********************************/
// 初始化数据
/********************************/
w--; //按下标为0开始算
int num = arc[0].length; //边长
int[] readLog = new int[num]; //访问记录
int count = 0; //计数器
for (int i = 0; i < num; i++) {
readLog[i] = 0; //初始化，没访问为0
}
int u = w;
readLog[w] = 1; //从w出发
int min;
int v = 0;
int TSPLength = 0; //哈密顿回路长度
while(count < num - 1){
//初始化最小值
min = MAX + 1;
for (int i = 0; i < num; i++) {
if(readLog[i] == 0 && arc[u][i] != 0 && arc[u][i] < min){
v = i; //记录最小路径的重点位置
min = arc[u][i]; //记录最小值
}
}
//1.加入距离，2.标记访问，3.继续前进
TSPLength += arc[u][v];
readLog[v] = 1;
count++;
//输出路径
System.out.println((u + 1) + "-->" + ( v + 1));
u = v; //重新赋值起始点
}
//闭合所经过的城市圈
System.out.println((v + 1) + "-->" + ( w + 1));
//打印所求长度
System.out.println("路径长度"+(TSPLength+arc[u][w]));
}
//打印二维矩阵
private static void showGraph() {
for (int i = 0; i < arc[0].length; i++) {
for (int j = 0; j < arc[0].length; j++) {
System.out.print(arc[i][j]+" ");
}
System.out.println();
}
}
private static void createGraph() throws Exception {
int weight;
int vnum;
System.out.println("输入顶点的个数");
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
vnum = Integer.parseInt(bufferedReader.readLine());
//创建矩阵
arc = new int[vnum][vnum];
//初始化矩阵
for (int l = 0; l < vnum; l++) {
for (int m = 0; m < vnum; m++) {
if(l != m){
System.out.println("输入"+l+"-"+m+"的连接边权值，不输入为MAX");
String input = bufferedReader.readLine();
if(input.isEmpty()){
weight = MAX;
}else{
weight = Integer.parseInt(input);
}
}else{
weight = MAX;
}
arc[l][m] = weight;
}
}
}
}
代码中，我准备了创建矩阵和打印矩阵的方法，然后对矩阵进行了贪心求tsp的运算。
运行结果如下，我们输入了上面所提到的矩阵。
经过运算求得了所行走的路径和长度。
