/**
 * 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;
    }

}