3

我们可以简单地修改旅行商问题以得到在 O(2^N * N^2) 时间复杂度内是否存在 Hamilton walk。

但是我在 codeforces 上读到它可以在 O(2^N * N) Time 中解决这个问题。

虽然，我无法理解他们正在考虑的状态，但他们有点压缩旅行商问题的原始状态。

谁能给我一个详细的解释，我是位掩码+ DP的新手（事实上我今天开始了：D）

如果您愿意，可以查看Codeforces的第 4 点

4

2 回答 2

3

术语：

  1. binary (x)手段x是基础2。
  2. 节点编号从0
  3. mask总是代表一个set节点。一个节点i在maskmean中2^i AND mask != 0。以同样的方式，集合mask-i（这里-意味着i从集合中移除）可以表示为mask XOR 2^i位掩码。

让mask是一组节点的位掩码。我们定义dp[mask]为另一组节点的位掩码，其中包含一个节点i当且仅当：

  1. i在mask
  2. 存在于节点集的汉密尔顿步行mask，它以 node 结束i

例如，dp[binary(1011)] = binary(1010)意味着存在一个binary(1011)以 node 结尾的1hamilton walk，并且存在另一个以 nodebinary(1011)结尾的 hamilton walk3

所以对于N节点，如果dp[2^N - 1] != 0

然后如您发布的 Codeforces 链接中所述，我们可以dp[]通过以下方式计算：

mask仅包含一个节点时i

dp[2^i] = 2^i（这意味着对于单个节点，游走始终存在，并以自身结束。

否则

给定mask，根据 的定义dp[mask]，对于 中的每个节点 i，mask我们想知道是否存在针对 的游走mask，并且结束于i。为了计算这一点，我们首先检查节点集合是否存在任何游走 mask-i，然后在 的这些游走中检查是否在连接到mask-i的节点处有游走结束。由于将它们结合起来，我们就可以走到.jimaski

为了使这一步更快，我们预处理为M[i]连接到的所有音符的位掩码i。所以i在dp[mask]如果dp[mask XOR 2^i] AND M[i] != 0。

多解释一下这一步，dp[mask XOR 2^i]是mask-i可以结束行走的M[i]节点集，是直接连接到的节点集i。所以他们的意思是是否存在任何结束的AND步行。maski

dp[]在O(2^N)太空中。计算dp[]看起来像

for mask = range(0, 2^N):
  for i in range(0,N):
    if 2^i AND mask != 0: # Node i in mask
      if (mask only has one node) || (dp[mask XOR 2^i] AND M[i] != 0):
        dp[mask] = dp[mask] OR 2^i # adding node i to dp[mask]

这是 O(2^N * N)

于 2015-07-15T21:06:07.880 回答
2

[编辑：看到另一个答案后，我意识到我回答错了问题。也许这些信息仍然有用？如果没有，我会删除这个。请在评论中告诉我。]

它们清楚地说明了 DP 表的每个条目将包含什么。它是对仅由特定顶点子集组成的特定子问题的解决方案，并具有路径必须在特定顶点处结束的附加约束：

令 dp[mask][i] 为由 mask 中的顶点生成的子图中最短哈密顿游走的长度，它以顶点 i 结束。

每条路径都在某个顶点处结束，因此可以通过寻找dp[(1 << n) - 1][i]所有 0 <= i < n 的最小值来找到原始问题的解决方案（或至少是它的长度）（(1 << n) - 1这只是使用最低n位全部设置为 1)。

主要更新规则（由于格式限制，我在下面稍作解释）可能会受益于更多解释：

dp[mask][i] = min(dp[mask XOR (1 << i)][j] + d(j, i)) 对所有 j 使得 bit(j, mask) = 1 和 (j, i ) 是一条边

因此，要填充dp[mask][i]，我们要mask在路径中的最后一个顶点为 的约束下解决 中的顶点集的子问题i。首先，请注意，任何P经过所有顶点mask并结束于的路径都i必须有一条最终边（假设 中至少有 2 个顶点mask）。这条边将从 中的某个非i顶点j到。为方便起见，设为具有 出边的顶点数。让与 相同的路径，但丢弃其最终边：那么 的长度为。由于任何maskikmaskiQP(j, i)Plength(Q) + d(j, i)路径可以这样分解，我们可以将所有路径的集合mask根据它们的最终边i分解成k组，在每个组中找到最好的路径，然后从这些k最小值中挑选出最好的，这样可以保证我们没有没有忽略任何可能性。

更正式地说，要找到最短路径，考虑所有可能的最终边P就足够了，对于每个这样的选择，找到一条通过剩余顶点（即除自身之外的所有顶点）结束并最小化的路径，然后选择最小值这些最小值。k(j, i)Qmaskijlength(Q) + d(j, i)

起初，按最终边缘分组似乎没有多大帮助。但请注意，对于 的特定选择jQ，任何以 为结尾j并最小化的路径length(Q) + d(j, i)也会最小化length(Q)，反之亦然，因为当（当然）固定时，d(j, i)这只是固定的额外成本。碰巧我们已经知道这样一条路径（或者至少它的长度，这是我们真正需要的）：它是！ 表示“二进制整数左移 1次”——这将创建一个由单个顶点组成的位集，即; 具有删除该顶点的效果（因为我们已经知道相应的位必须为 1 ）。总而言之，意味着jidp[mask XOR (1 << i)][j](1 << i)iiXORmaskmaskmask XOR (1 << i)mask \ {i}用更多的数学符号表示。

我们仍然不知道哪个倒数第二个顶点j是最好的，所以我们必须尝试所有这些并像以前一样选择最好的——但是为每个选择k找到最佳路径现在是一个简单的 O(1) 数组查找，而不是指数时间搜索:)Qj

于 2015-07-15T21:21:37.290 回答