欢迎光临
我们一直在努力

状态压缩dp——带权旅行商问题(TSP)


初步思考

为什么不能用一维dp[i]表示“进攻第 i 个星球的最少能量”?

因为没有记录进攻过哪些星球,路线很混乱,而且可能一直在同一个星球上

因此需要定义二维状态压缩DP,定义 dp[mask][u] :mask是二进制状态,表示已进攻的星球集合,u表示当前在星球u,dp数组的值表示从任意走过的路线到此时u的最小能量。

状态压缩:二进制状态是什么意思?

即用二进制数表示 “已经进攻过哪些星球”

n 个星球,每个星球对应二进制的一位:

  • 第 0 位为 1:表示星球 0 已经被进攻
  • 第 1 位为 1:表示星球 1 已经被进攻
  • …
  • 第 n-1 位为 1:表示星球 n-1 已经被进攻

所有可能的状态总数就是 2^n 种(每个星球都有 “已进攻 / 未进攻” 两种状态),所以数组长度设为 1 << n

<< 在Java中是左移运算符,表示把数字的二进制位向左移动 n 位,右边补 0。

数学上等价于:1 << n = 2^n(2 的 n 次方)

因此创建dp数组: dp=new double[ 1<<n ][ n ] ;

举个例子,当 n=3 时:

  • 1 << 3 = 8,所以第一维长度是 8
  • 状态 001(十进制 1):只进攻了星球 0
  • 状态 011(十进制 3):进攻了星球 0 和星球 1
  • 状态 111(十进制 7):所有星球都进攻完毕

完整理解 dp[mask][u]

结合起来,dp[mask][u] 的含义是:

已经进攻过的星球集合为 mask(二进制表示),当前飞船停在星球 u 时,所消耗的最少能量。

比如 dp[0b101][2](十进制 mask=5,u=2):

  • 二进制 101 表示星球 0 和星球 2 已经被进攻
  • 当前飞船在星球 2
  • 值就是 “按这个顺序进攻,最终停在星球 2 时的最少能量”

带权旅行商问题

  • 状态:dp[mask][u] 表示已经访问过的星球集合为 mask,当前在星球 u 时的最小能量消耗。
  • 初始化:dp[1 << u][u] = 0(从 u 出发,初始能量为 0)。
  • 转移:

dp[mask | (1 << v)][v] = min(
dp[mask | (1 << v)][v],
dp[mask][u] + 距离(u, v) * w[v]
)

  • 答案:所有 dp[(1<<n)-1][u] 的最小值。

Java完整代码:

import java.util.*;

public class Main {
static int n;
static int[] x, y, z, w;

// dp[mask][u] 表示状态mask,当前在u点的最小能量
static double[][] dp;

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
x = new int[n];
y = new int[n];
z = new int[n];
w = new int[n];
for (int i = 0; i < n; i++) {
x[i] = scan.nextInt();
y[i] = scan.nextInt();
z[i] = scan.nextInt();
w[i] = scan.nextInt();
}
scan.close();

// 状态压缩DP初始化
int fullMask = (1 << n) – 1;
dp = new double[1 << n][n];
for (double[] row : dp) {
Arrays.fill(row, Double.POSITIVE_INFINITY);
}

// 起点:只访问自己,能量为0
for (int i = 0; i < n; i++) {
dp[1 << i][i] = 0.0;
}

// 遍历所有状态
for (int mask = 0; mask < (1 << n); mask++) {
// 遍历当前在哪个星球u
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Double.POSITIVE_INFINITY) {
continue;
}
// 尝试走到下一个未访问的星球v
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
// 计算u到v的距离
double dist = Math.sqrt(
(x[u] – x[v]) * 1.0 * (x[u] – x[v]) +
(y[u] – y[v]) * 1.0 * (y[u] – y[v]) +
(z[u] – z[v]) * 1.0 * (z[u] – z[v])
);
double cost = dist * w[v];
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + cost);
}
}
}

// 所有星球都访问完,取最小值
double ans = Double.POSITIVE_INFINITY;
for (int i = 0; i < n; i++) {
ans = Math.min(ans, dp[fullMask][i]);
}
// 保留两位小数输出
System.out.printf("%.2f\\n", ans);
}
}

赞(0)
未经允许不得转载:171主机测评 » 状态压缩dp——带权旅行商问题(TSP)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址