状态压缩 DP

动态规划

说明

用位掩码表示已选择集合；下例求小规模旅行商问题的最短回路，时间 O(n²2ⁿ)。

分析

mask 的每一位表示某个城市是否已经访问，dp[mask][v] 表示访问该集合并停在 v 的最短长度。对每个未访问城市尝试转移，最后加上回到起点的费用。

图解推演

三个城市的 bit0..bit2 记录访问集合，从 dp[001][0]=0 出发。路线 0→1→2 对应集合 001→011→111，费用 2+3，最后回 0 再加 4，合计 9。仅知道集合还不够，停在哪个城市决定下一条边的费用，所以状态必须同时含末端城市。

查看图表代码

适用前提与边界

状态数为 2ⁿ，适合 n 较小的精确求解，不适合大规模路线规划。

示例输入与调用

fmt.Println(TSP([][]int{{0, 2, 4}, {2, 0, 3}, {4, 3, 0}}))

运行输出

9

完整 Go 示例

package main

import "fmt"

func TSP(cost [][]int) int {
	n := len(cost)
	if n == 0 {
		return 0
	}
	inf := int(^uint(0)>>1) / 2
	dp := make([][]int, 1<<n)
	for m := range dp {
		dp[m] = make([]int, n)
		for i := range dp[m] {
			dp[m][i] = inf
		}
	}
	dp[1][0] = 0
	for mask := 1; mask < 1<<n; mask++ {
		for v := 0; v < n; v++ {
			if dp[mask][v] == inf {
				continue
			}
			for w := 0; w < n; w++ {
				if mask>>w&1 == 0 {
					next := mask | 1<<w
					dp[next][w] = min(dp[next][w], dp[mask][v]+cost[v][w])
				}
			}
		}
	}
	best := inf
	for v := range cost {
		best = min(best, dp[(1<<n)-1][v]+cost[v][0])
	}
	return best
}

func main() {
	fmt.Println(TSP([][]int{{0, 2, 4}, {2, 0, 3}, {4, 3, 0}}))
}