这个问题可以能也不是严格意义上的TPS（旅行家问题），有错的话希望大家指出。
- Java code
/** * 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; }}