package com.dam.heuristic.ts.test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
/**
 * 禁忌搜索
 */
public class TsApi {
    //当前已占用的禁忌表长度
    private int curUsedTabooLen;
    //禁忌表长度
    private int tabooTableLength;
    //序列长度
    private int sequenceLen;
    //最大的迭代次数
    private int maxGen;
    //每次搜索领域的个数
    private int neighbourNum;
    //距离矩阵
    private double[][] distanceMatrix;
    /**
     * 构造函数，用于创建对象
     *
     * @param tabooTableLength
     * @param maxGen
     * @param neighbourNum
     * @param distanceMatrix
     */
    public TsApi(int tabooTableLength, int maxGen, int neighbourNum, double[][] distanceMatrix) {
        this.curUsedTabooLen = 0;
        this.tabooTableLength = tabooTableLength;
        this.sequenceLen = distanceMatrix[0].length;
        this.maxGen = maxGen;
        this.neighbourNum = neighbourNum;
        this.distanceMatrix = distanceMatrix;
    }
    /**
     * 禁忌搜素算法接口
     */
    public void solve() {
        定义变量
        long startTime = System.currentTimeMillis();
        //禁忌表
        int[][] tabooTable = new int[this.tabooTableLength][this.sequenceLen];//禁忌表
        //代数
        int t = 0;
        ///最优解
        //最优代数
        int bestT = 0;
        //序列
        int[] localSequence = new int[this.sequenceLen];
        //最优序列
        int[] bestSequence;
        //存储暂时序列
        int[] tempSequenceInNeighbour;
        //存储邻居中最好的序列对
        int[] bestSequenceInNeighbour = null;
        //存储求得最优解的时间
        long bestTime = 0;
        //最优序列对应的目标函数值
        double bestObjectValue = 0;
        生成初始序列
        this.generateInitialSequence(localSequence);
        //初始化bestSequence，刚开始的最优序列为初始序列
        bestSequence = localSequence.clone();
        bestObjectValue = this.getObjectValue(bestSequence);
        System.out.println("初始序列：" + Arrays.toString(bestSequence));
        System.out.println("初始目标函数值：" + bestObjectValue);
        对序列进行迭代优化
        while (t++ < this.maxGen) {
            //如果目标是最小化函数值，则初始化为Double.MAX_VALUE；反之，初始化为-Double.MAX_VALUE
            double bestObjectValueInNeighbour = Double.MAX_VALUE;
            //neighbourNum ：搜索领域个数
            int i = 0;
            while (i < this.neighbourNum) {
                //产生一条新序列
                tempSequenceInNeighbour = this.generateNewSequence(localSequence);
                //判断是否在禁忌表中
                if (isSequenceAtTabooTable(tabooTable, tempSequenceInNeighbour) == false) {
                    //搜索到的邻居序列不在禁忌表中，i才加一
                    i++;
                    //不在禁忌表中时，执行下面的计算，获取tempSequence所对应的目标函数值
                    double tempObjectValue = this.getObjectValue(tempSequenceInNeighbour);
                    //更新最优解
                    if (tempObjectValue < bestObjectValueInNeighbour) {
                        bestObjectValueInNeighbour = tempObjectValue;
                        bestSequenceInNeighbour = tempSequenceInNeighbour.clone();
                    }
                }
            }
            //解禁忌表，LocalGh加入禁忌表
            this.addSequenceToTabooTable(tabooTable, bestSequenceInNeighbour);
            //接受邻居序列中的最优序列，让算法可以跳出局部最优
            localSequence = bestSequenceInNeighbour.clone();
//            System.out.println("当前最优邻居目标函数值：" + bestObjectValueInNeighbour);
//            System.out.println("当前最优邻居解：" + Arrays.toString(bestSequenceInNeighbour));
//            System.out.println("当前最优解为：" + bestObjectValue + "，求得最优解的时间：" + bestTime + "ms");
            //更新全局最优解
            if (bestObjectValueInNeighbour < bestObjectValue) {
                //更新最优代数
                bestT = t;
                //更新最优目标函数值
                bestObjectValue = bestObjectValueInNeighbour;
                //更新最优序列
                bestSequence = localSequence.clone();
                System.out.println("----------------------------------------------------------------------------------------------------------------");
                System.out.println("当前代数：" + t);
                System.out.println("当前最优解为：" + bestObjectValue);
                bestTime = (System.currentTimeMillis() - startTime);
                System.out.println("当前计算时间为：" + bestTime + "ms");
                System.out.println("----------------------------------------------------------------------------------------------------------------");
            }
//            System.out.println("当前计算时间为：" + (System.currentTimeMillis() - startTime) + "ms");
//            System.out.println("----------------------------------------------------------------------------------------------------------------");
        }
        System.out.println("最佳迭代次数:" + bestT);
        System.out.println("最优目标函数值:" + bestObjectValue);
        System.out.println("最优解对应序列：" + Arrays.toString(bestSequence));
        System.out.println("计算时间为：" + (System.currentTimeMillis() - startTime) + "ms");
    }
    /**
     * 生成初始序列
     */
    public void generateInitialSequence(int[] sequence) {
      /*  HashSet<Integer> sequenceSet = new HashSet<>();
        for (int i = 1; i < sequence.length; i++) {
            sequenceSet.add(i);
        }
        //贪婪算法获取初始序列，从城市0开始旅行，即城市0为起点城市
        sequence[0] = 0;
        //每次获取离当前城市最近的城市，并加入到sequence
        for (int i = 1; i < sequence.length; i++) {
            //寻找离i-1城市最近的城市，即确定第i个城市是哪个
            double smallDistance = Double.MAX_VALUE;
            int curCity = 0;
            for (Integer j : sequenceSet) {
                if (this.distanceMatrix[sequence[i - 1]][j] < smallDistance && j != sequence[i - 1] ) {
                    smallDistance = this.distanceMatrix[sequence[i - 1]][j];
                    curCity = j;
                }
            }
            sequence[i] = curCity;
            sequenceSet.remove(curCity);
        }*/
        for (int i = 0; i < sequence.length; i++) {
            sequence[i] = i;
        }
    }
    /**
     * 根据当前序列获取目标函数值
     *
     * @param sequence
     * @return
     */
    public double getObjectValue(int[] sequence) {
        double objectValue = 0;
        //计算从第0个城市到最后一个城市的路程
        for (int i = 0; i < sequence.length - 1; i++) {
            objectValue += this.distanceMatrix[sequence[i]][sequence[i + 1]];
        }
        //计算最后一个城市到第0个城市的路程
        objectValue += this.distanceMatrix[sequence[0]][sequence[sequence.length - 1]];
        return objectValue;
    }
    /**
     * 生产新序列
     *
     * @param sequence
     * @return
     */
    public int[] generateNewSequence(int[] sequence) {
        int[] sequenceClone = sequence.clone();
        //对序列中的元素进行打乱，即可产生新的序列
        Random random = new Random();
        int i = random.nextInt(sequence.length);
        int j = random.nextInt(sequence.length);
        while (i == j) {
            j = random.nextInt(sequence.length);
        }
        int temp = sequenceClone[i];
        sequenceClone[i] = sequenceClone[j];
        sequenceClone[j] = temp;
        return sequenceClone;
    }
    /**
     * 将序列加入禁忌表，如果禁忌表已满，根据先进先出的原则移除最早进入禁忌表的序列
     *
     * @param tabooTable
     * @param sequence
     */
    public void addSequenceToTabooTable(int[][] tabooTable, int[] sequence) {
        if (this.curUsedTabooLen < this.tabooTableLength) {
            //如果当前禁忌表还有空位，则直接加入即可
            for (int i = 0; i < sequence.length; i++) {
                tabooTable[this.curUsedTabooLen][i] = sequence[i];
            }
            this.curUsedTabooLen++;
        } else {
            //如果禁忌表已经满了，则移除第一个进表的路径，添加新的路径到禁忌表末尾
            //后面的禁忌编码全部向前移动一位，覆盖掉当前第一个禁忌编码
            for (int i = 0; i < tabooTable.length - 1; i++) {
                tabooTable[i] = tabooTable[i + 1].clone();
            }
            //将sequence加入到禁忌队列的最后
            for (int i = 0; i < sequence.length; i++) {
                tabooTable[tabooTable.length - 1][i] = sequence[i];
            }
        }
    }
    /**
     * 判断序列对是否存在于禁忌表中
     *
     * @param tabooTable
     * @param sequence
     * @return
     */
    public boolean isSequenceAtTabooTable(int[][] tabooTable, int[] sequence) {
        for (int i = 0; i < tabooTable.length; i++) {
            boolean flag = true;
            for (int j = 0; j < sequence.length; j++) {
                if (sequence[j] != tabooTable[i][j]) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) {
                return true;
            }
        }
        return false;
    }
}

package com.dam.heuristic.ts.test;
import java.io.File;
import java.io.FileInputStream;
public class TsMainRun {
    public static void main(String[] args) throws Exception {
        声明变量
        //距离矩阵，可以直接获取任意两个编号城市的距离
        double[][] distanceMatrix;
        读取数据
        String data = read(new File("src/main/java/com/data/tsp/att48.txt"), "GBK");
        String[] cityDataArr = data.split("\n");
        //初始化数组
        distanceMatrix = new double[cityDataArr.length][cityDataArr.length];
        for (int i = 0; i < cityDataArr.length; i++) {
            String[] city1Arr = cityDataArr[i].split(" ");
            int cityOne = Integer.valueOf(city1Arr[0]);
            for (int j = 0; j < i; j++) {
                String[] city2Arr = cityDataArr[j].split(" ");
                int cityTwo = Integer.valueOf(city2Arr[0]);
                if (cityOne == cityTwo) {
                    distanceMatrix[cityOne - 1][cityTwo - 1] = 0;
                } else {
                    distanceMatrix[cityOne - 1][cityTwo - 1] = getDistance(Double.valueOf(city1Arr[1]), Double.valueOf(city1Arr[2]), Double.valueOf(city2Arr[1]), Double.valueOf(city2Arr[2]));
                    //对称赋值
                    distanceMatrix[cityTwo - 1][cityOne - 1] = distanceMatrix[cityOne - 1][cityTwo - 1];
                }
            }
        }
     /*   System.out.println("输出距离矩阵-------------------------------------------------------------------");
        for (double[] matrix : distanceMatrix) {
            System.out.println(Arrays.toString(matrix));
        }*/
        TsApi TSApi = new TsApi(20, 100000, 100, distanceMatrix);
        TSApi.solve();
    }
    /**
     * 给定两个城市坐标，获取两个城市的直线距离
     *
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    private static double getDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt((Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2))/10);
    }
    private static String read(File f, String charset) throws Exception {
        FileInputStream fstream = new FileInputStream(f);
        try {
            int fileSize = (int) f.length();
            if (fileSize > 1024 * 512) {
                throw new Exception("File too large to read! size=" + fileSize);
            }
            byte[] buffer = new byte[fileSize];
            fstream.read(buffer);
            return new String(buffer, charset);
        } finally {
            try {
                fstream.close();
            } catch (Exception e) {
            }
        }
    }
}