双调欧几里得旅行商问题（动态规划） 《java实现》

问题描述:

欧几里得旅行商问题 是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。图a给出了7个点问题的解，这个问题的一般形式是NP完全的,故其解需要多于多项式的时间。

　　J.K.Bentley建议通过只考虑双调旅程来简化问题，这种旅程即为从最左点开始，严格从左到最右点，再严格地从最右点回到最左点。图b显示了同样的7个点的问题的最短双调路线，在这种情况下，多项式的时间的算法是有可能的。

　　描述一个确定最优双调路线的O（n^2）时间的算法。可以假设任何两点的x坐标都不相同。

解法思路：

a:数据的提前定义

首先要理解双调，也就是说有两条路线，一个一直向左，一个一直向右，我们不妨设这两种路线分别为A路线（一直向左），与B路线（一直向右走），那么我们再来看看A，B都必须满足什么条件（A[i]表示从0点到i点路径，B[j]表示从j点到0点的路径）

1：A,B路线必定没有重复点，如果有的话也只能是起点和终点

2：A,B路线的路径总和必定是所有情况中最小的

如果满足这两个条件那么此时A+B的路径和就是我们需要的最优双调路线。

小技巧：这里B[j]是从j到0，并且从j到0和从0到j的路径没有变，我们不妨也把B看做另外一条从0一直向右走的路径（当然这里的B也同样需要满足上面两个条件）

为了方便阐述，我们引用d[i][j]表示i点到j点的直线距离（两点间的距离公式我就不赘述了）

s[i][j]表示在A[i],B[j]路径和最小的情况下的值（当然正如你想的那样，当i=j，也就是终点，起点都一样，中间不一样，就构成了一个环，也就是只有i个点情况下的最短闭合巡游路线）

B：动态规划，公式推导

首先s[0][0]=0;我就不赘述了

这里容许我那个不那么标准的图，来分析一下（由于对称的关系，s[i][j]=s[j][i],因此这里我就只拿一般来就做个图论，也就是当j>=i时） ·综上：

当然i=j可以和j>i+i放在一起，没有必要把它专门分出来。

C：代码

public static void Print(double map[][]) {
		for(int i=0;i<map.length;i++)
		{
			for(int j=0;j<map[0].length;j++)
			{
				System.out.printf("%.2f ", map[i][j]);
			}
			System.out.println("");
		}
	}
	public static double FindDist(Point p1,Point p2)
	{
		return Math.sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
	}
	public static void main(String[] args) {
		Point[] point = {
			new Point(0, 0),
			new Point(1,6),
			new Point(2,3),
			new Point(5,2),
			new Point(6,5),
			new Point(7,1),
			new Point(8,4)
			};
		double[][] s =  new double[point.length][point.length];
		s[0][0] = 0;
		for(int i=0;i<s.length;i++)
		{
			for(int j=i;j<s[0].length;j++)
			{
				if(i<=j  && i!=j-1 && j!=0)
				{
					s[i][j] = s[i][j-1]+FindDist(point[j-1],point[j]);
					s[j][i] = s[i][j]; 
				}
				else if(i<=j && i==j-1)
				{
					double min = Double.MAX_EXPONENT;
					for(int k=0;k<j;k++)
					{
						if(min>s[i][k]+FindDist(point[k], point[j]))
						{
							min  = s[i][k]+FindDist(point[k], point[j]);
						}
					}
					s[i][j] = min;
					s[j][i] = min;
				}
			}
		}
		Print(s);
	}

}
class Point{
	public int x;
	public int y;
	public Point(int x,int y) {
		this.x = x;
		this.y = y;
		// TODO Auto-generated constructor stub
	}
	public Point() {
		// TODO Auto-generated constructor stub
	}
}