题目描述
给定一张 $n $个点的带权无向图,点从 $0∼n−1$ 标号,求起点 $0$ 到终点 $n−1 $的最短 Hamilton 路径。
Hamilton 路径的定义是从 $0$ 到 $n−1$ 不重不漏地经过每个点恰好一次。
问题分析
如果使用暴力算法,那就是对1~n-2进行全排列,那么时间复杂度是(n-2)!,超时。
算法设计
状态压缩DP。
代码实现
package main
import "fmt"
const INF = 1000000000
func main(){
var n int
fmt.Scan(&n)
w := make([][]int, n)
for i := 0;i < n;i ++{
w[i] = make([]int, n)
}
// f[i][j] 表示从0点走到j点且路径状态为i的所有路径
f := make([][]int, 1 << n)
for i := 0;i < 1 << n;i ++{
f[i] = make([]int, n)
for j := 0;j < n;j ++{
f[i][j] = INF
}
}
for i := 0;i < n;i ++{
for j := 0;j < n;j ++{
fmt.Scan(&w[i][j])
}
}
// DP f[1][0] 表示路径中只有第0个点并且终点也是0,故f[1][0] = 0
f[1][0] = 0
for i := 0; i < 1 << n;i ++{
// 枚举路径终点
for j := 0;j < n;j ++{
if i >> j & 1 != 1{
continue
}
// 枚举路径倒数第二个点
for k := 0;k < n;k ++{
if (i - (1 << j)) >> k & 1 == 1{
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j])
}
}
}
}
// 结果需要进过所有节点并且到达n-1点
fmt.Println(f[(1 << n) - 1][n-1])
}
func min(x,y int) int{
if x > y{
return y
}
return x
}
复杂度分析
三重循环$O(n*n*2^n) $,$0 \le n\le 20$,故为 4*10^8