TPS（旅行家）问题，自己随便谢谢，高手进来看一下对不对。

这个问题可以能也不是严格意义上的TPS（旅行家问题），有错的话希望大家指出。/**
 * author:DNY
 * date:2011-05-23
 * question:这是一个tps(旅行家问题).
 * 
 * 给的距离(dist)，价钱(value)，都是随机出来，存在一个数组中。
 * 在求出他们的平均值，也存在数组中(ave)。
 * 使用的算法是仿照弗洛伊德的最短路径算法。
 */
package edu.xawl.daocao;import java.util.ArrayList;public class TPS
{
static private final int SIZE = 100;
static private Point[] point = null;
static private double[][] dist = null;
static private double[][] value = null;
static private double[][] ave = null;
static private ArrayList<Point> haveIn = null;
static private ArrayList<Point> haveNotIn = null;
static private double MIN = 0; int start = 0;
int end = SIZE - 1;

public static void main(String[] args)
{
TPS tps = new TPS();
haveIn = new ArrayList<Point>();
haveNotIn = new ArrayList<Point>(); double totalDist = 0;
double totalValue = 0;
double totalAve = 0; // new出来点数组
point = new Point[SIZE];
dist = new double[SIZE][SIZE];
value = new double[SIZE][SIZE];
ave = new double[SIZE][SIZE]; // new出来所有点
for (int i = 0; i < SIZE; i++)
{
point[i] = new Point();
point[i].setIndex(i);
}
// 计算各个点之间的举例，并存入数组dist中
for (int i = 0; i < SIZE; i++)
{
for (int j = i; j < SIZE; j++)
{
dist[i][j] = Point.distance(point[i], point[j]);
value[i][j] = Math.random() * 1000;
if (dist[i][j] != 0)
ave[i][j] = value[i][j] / dist[i][j];
}
}
for (int i = SIZE - 1; i >= 0; i--)
{
for (int j = i; j >= 0; j--)
{
dist[i][j] = dist[j][i];
value[i][j] = value[j][i];
ave[i][j] = ave[j][i];
}
} // 打印数组
System.out.println("打印距离数组:");
tps.printArr(dist);
System.out.println("打印价值数组:");
tps.printArr(value);
System.out.println("打印平均数数组:");
tps.printArr(ave); System.out.print("选取最优路径开始:");
// 调用查找最短路径方法
tps.FindShort();
System.out.println("得到的最短路径如下表");
for (int i = 0; i < haveIn.size(); i++)
{
if (i == 0)
{
System.out.print("从p" + haveIn.get(i).getIndex() + "开始-->");
} else if (i == haveIn.size() - 1)
{
System.out.println("p" + haveIn.get(i).getIndex() + "结束");
} else
{
System.out.print("p" + haveIn.get(i).getIndex() + "-->");
}
}

for (int i = 0; i < haveIn.size() - 1; i++)
{
totalDist = totalDist + dist[haveIn.get(i).getIndex()][haveIn.get(i + 1).getIndex()];
totalValue = totalValue + value[haveIn.get(i).getIndex()][haveIn.get(i + 1).getIndex()];
totalAve = totalAve + ave[haveIn.get(i).getIndex()][haveIn.get(i + 1).getIndex()];
}
System.out.println("总路程为:"+totalDist);
System.out.println("总路费为:"+totalValue);
System.out.println("平均值为:"+totalAve); } /**
 * 先把起点和终点举例算出来 然后一个点一个一个加进来 对于打印出来的结果不要奇怪，认为往两个点中间加一个点，就一定比两个点的距离大
 * 而实际上这里用的不只是距离一个参数，还使用了路费 最后参与比较的路费/距离，也就是ave平均数
 */
private void FindShort()
{
// 改变最小值
MIN = ave[start][end];
haveIn.add(point[start]);
haveIn.add(point[end]);
for (int i = 0; i < SIZE; i++)
{
if (i != start && i != end)
haveNotIn.add(point[i]);
}
System.out.println("(haveNotIn中有元素" + haveNotIn.size() + ")");
for (int i = 0; i < haveNotIn.size(); i++)
{
// 当前最小路径长度
double temp = MIN;
// 加入haveIn的point对象的位置
int mi = 1;
// 加上新点后的初始大小，位置为0与1之间插入
MIN = MIN + ave[haveIn.get(0).getIndex()][haveNotIn.get(i).getIndex()] + ave[haveNotIn.get(i).getIndex()][haveIn.get(1).getIndex()] - ave[haveIn.get(0).getIndex()][haveIn.get(1).getIndex()];
System.out.print("第" + i + "轮的最小值为：" + temp);
System.out.print(",将p" + haveNotIn.get(i).getIndex() + "插入位置" + mi + "后的最小值为" + MIN);
System.out.println();
// 从位置1开始到倒数第二位，看谁路径最短
for (int j = 1; j < haveIn.size() - 1; j++)
{
if (temp + ave[haveIn.get(j).getIndex()][haveNotIn.get(i).getIndex()] + ave[haveNotIn.get(i).getIndex()][haveIn.get(j + 1).getIndex()] - ave[haveIn.get(j).getIndex()][haveIn.get(j + 1).getIndex()] <= MIN)
{
mi = j + 1;
MIN = temp + ave[haveIn.get(j).getIndex()][haveNotIn.get(i).getIndex()] + ave[haveNotIn.get(i).getIndex()][haveIn.get(j + 1).getIndex()] - ave[haveIn.get(j).getIndex()][haveIn.get(j + 1).getIndex()];
System.out.println(temp + "转化有的最小值为:" + MIN);
}
}
System.out.println("p" + haveNotIn.get(i).getIndex() + "加入了haveIn的位置在" + mi);
haveIn.add(mi, haveNotIn.get(i));
System.out.println();
}
} private void printArr(double arr[][])
{
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
System.out.printf("%8f    ", arr[i][j]);
}
System.out.println();
}
}
}class Point
{
private double x;
private double y; private int index; public Point()
{
x = Math.random() * 1000;
y = Math.random() * 1000;
} public static double distance(Point p1, Point p2)
{
return Math.sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
} public int getIndex()
{
return index;
} public void setIndex(int index)
{
this.index = index;
}}