一、問題描述
旅行推銷員問題（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個NP難問題，在運籌學(xué)和理論計算機科學(xué)中非常重要。
二、解決思路
這個問題有點像地圖著色問題但是是不一樣的，地點之間是帶權(quán)路徑，地圖著色相當于是節(jié)點的選擇，順序無關(guān)性，這個是順序有關(guān)性，求解選擇哪個節(jié)點，哪一個則是節(jié)點的路徑選擇問題。首先定義解空間。
三、代碼
public class TravelPlan {
public static void main(String[] args) {
int[][] adjacencyMartix = new int[][]{
{-1, 3, -1, 8, 9},
{3, -1, 3, 10, 5},
{-1, 3, -1, 4, 3},
{8, 10, 4, -1, 20},
{9, 5, 3, 20, -1}};
Scanner scanner = new Scanner(System.in);
int originNode = scanner.nextInt();
int[] currentValueStatus = new int[]{-1, -1, -1, -1, -1};
// 設(shè)置源點已經(jīng)被訪問過
currentValueStatus[originNode - 1] = 1;
int[] bestValueStatus = new int[adjacencyMartix.length];
System.out.println(calc(adjacencyMartix, originNode - 1, currentValueStatus, bestValueStatus, Integer.MAX_VALUE, 0, 1, originNode - 1));
System.out.println(Arrays.toString(bestValueStatus));
}
/**
* 進行計算
*
* @param adjacencyMatrix 記錄城市間關(guān)系
* @param lastCityIndex 記錄上個城市的索引 也是起始城市節(jié)點
* @param currentValue 此路徑城市到訪狀態(tài)維護
* @param bestValueStatus 最好結(jié)果城市最好路徑記錄
* @param bestValue 最好的結(jié)果
* @param currentValue 當前結(jié)果值
* @param loopIndex 第幾次路徑選擇
* @param originNode 起始節(jié)點因為最后要回到起始節(jié)點所以需要記錄下
*/
public static Integer calc(int[][] adjacencyMatrix, int lastCityIndex, int[] currentValueStatus, int[] bestValueStatus, int bestValue, int currentValue, int loopIndex, int originNode) {
/**
* 收集 到達鏈路的終點
*/
if (loopIndex > currentValueStatus.length - 1) {
//最后一個城市和起始點有邊
if (currentValue + adjacencyMatrix[lastCityIndex][originNode] < bestValue && adjacencyMatrix[lastCityIndex][originNode] != -1) {
// 記錄最優(yōu)的解 再加上回到原點的值
bestValue = currentValue + adjacencyMatrix[lastCityIndex][originNode];
for (int j = 0; j < currentValueStatus.length; j++) {
bestValueStatus[j] = currentValueStatus[j];
}
}
return bestValue;
} else {
//搜索 這里如果用交換的算法可以較少遍歷 也就是將狀態(tài)維護為到訪區(qū)間和未到訪區(qū)間 KISS原則怎么容易看怎么來
// 這里由于起源節(jié)點已經(jīng)被設(shè)置為訪問過，所以不會再訪問
for (int j = 0; j < adjacencyMatrix.length; j++) {
// 起始節(jié)點最后到達葉子處理
if (j == originNode) {
continue;
}
// 上一節(jié)點和當前節(jié)點是通路并且 到達當前節(jié)點后的值還是小于最優(yōu)值才可以繼續(xù) 當前節(jié)點沒有被訪問過
if ((adjacencyMatrix[lastCityIndex][j] != -1 && adjacencyMatrix[lastCityIndex][j] + currentValue < bestValue && currentValueStatus[j] == -1)) {
// 標記為已經(jīng)到訪 -.- loop代表訪問的第幾個節(jié)點
loopIndex += 1;
currentValueStatus[j] = loopIndex;
// 值累加 前一個節(jié)點到當前節(jié)點的距離
currentValue += adjacencyMatrix[lastCityIndex][j];
// 遞歸向下走 j節(jié)點變成前一個幾點
bestValue = calc(adjacencyMatrix, j, currentValueStatus, bestValueStatus, bestValue, currentValue, loopIndex, originNode);
//回溯當前節(jié)點累加的值
currentValueStatus[j] = -1;
loopIndex -= 1;
currentValue -= adjacencyMatrix[lastCityIndex][j];
}
}
return bestValue;
}
}
}
