April 23, 2021: there are n cities in the TSP problem, and there is a distance between any two cities

2021-04-23：TSP problem Yes N Cities , There is a distance between any two cities , The distance from any city to itself is 0. All point to point distances There is one for each N*N Two dimensional array of matrix in , That is, the whole graph is represented by adjacency matrix . We now require a travel agent to start from k City You must go through every city and only stay in one city once , Finally return to the departure k city , Return to the path with the shortest total distance distance . The parameter is given a matrix, Given k.

Fuda answer 2021-04-23：

Dynamic programming .

The code to use golang To write . The code is as follows ：

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  Cities in status After removing the , The state of 
                    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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code