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的运算。
运行结果如下,我们输入了上面所提到的矩阵。
经过运算求得了所行走的路径和长度。