2021-04-23：TSP问题 有N个城市，任何两个城市之间的都有距离

2021-04-23：TSP问题 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的距离都为0。所有点到点的距 离都存在一个N*N的二维数组matrix里，也就是整张图由邻接矩阵表示。现要求一旅行商从k城市 出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的k城，返回总距离最短的路的 距离。参数给定一个matrix，给定k。

福大大 答案2021-04-23：

动态规划。

代码用golang编写。代码如下：

代码语言：txt复制

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代码

java matrix 动态规划

0 人点赞