2021-04-23：TSP问题 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的距离都为0。所有点到点的距 离都存在一个N*N的二维数组matrix里，也就是整张图由邻接矩阵表示。现要求一旅行商从k城市 出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的k城，返回总距离最短的路的 距离。参数给定一个matrix，给定k。
福大大 答案2021-04-23：
动态规划。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
matrix := [][]int{
{0, 2, 4, 5},
{2, 0, 4, 4},
{4, 4, 0, 2},
{5, 4, 2, 0}}
ret := t4(matrix)
fmt.Println(ret)
}
func t4(matrix [][]int) int {
N := len(matrix) // 0...N-1
statusNums := 1 << N
dp := make([][]int, statusNums)
for i := 0; i < statusNums; i++ {
dp[i] = make([]int, N)
}
for status := 0; status < statusNums; status++ {
for start := 0; start < N; start++ {
if (status & (1 << start)) != 0 {
if status == (status & (^status + 1)) {
dp[status][start] = matrix[start][0]
} else {
min := math.MaxInt32 //Integer.MAX_VALUE;
// start 城市在status里去掉之后，的状态
preStatus := status & (^(1 << start))
// start -> i
for i := 0; i < N; i++ {
if (preStatus & (1 << i)) != 0 {
cur := matrix[start][i] + dp[preStatus][i]
min = getMin(min, cur)
}
}
dp[status][start] = min
}
}
}
}
return dp[statusNums-1][0]
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码