如何在 O(2^n) 内存和 O(2^n *n) 时间中检查哈密顿行走是否存在

Question

我们可以简单地修改旅行商问题，以在 O(2^N * N^2) 时间复杂度内获得汉密尔顿行走是否存在。

但我在 codeforces 上看到它可以在 O(2^N * N) 时间内解决这个问题。

虽然，我无法理解他们考虑的状态，但他们对旅行商问题的原始状态进行了某种压缩。

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

如果需要，可以在 Codeforces

查看第 4 点

Answer 1

术语：

binary (x) 表示 x 基于 2.
从 0
mask 总是代表 set 个节点。 i 中的节点 mask 表示 2^i AND mask != 0。以同样的方式设置 mask-i（这里 - 表示从集合中删除 i）可以表示为位掩码中的 mask XOR 2^i。

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

i 在 mask
存在节点集 mask 的汉密尔顿游走，其结束于节点 i

例如，dp[binary(1011)] = binary(1010) 表示 binary(1011) 存在一个汉密尔顿游走，它以节点 1 结束，而 binary(1011) 存在另一个汉密尔顿游走，它以节点结束3

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

然后按照您发布的 Codeforces link 中的描述，我们可以通过以下方式计算 dp[]：

当mask只包含一个节点时i

dp[2^i] = 2^i (which means for a single node, a walk always exists, and it ends at itself.

否则

Given mask, by definition of dp[mask], for every node i in mask, we want to know if a walk exist for mask, and ends at i. To calculate this, we first check if any walk exists for the set of nodes mask-i, then check among those walks of mask-i, if there's a walk ends at a node j that's connected to i. Since combining them gives us a walk of mask that ends at i.

To make this step faster, we pre-process M[i] to be the bitmask of all notes connected to i. So i in dp[mask] if dp[mask XOR 2^i] AND M[i] != 0.

To explain a bit more about this step, dp[mask XOR 2^i] is the set of nodes that walk of mask-i can end, and M[i] is the set of nodes that's directly connected to i. So the AND of them means if any walk of mask that ends in i exists.

dp[] 是 space 中的 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)

Answer 2

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

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

Let dp[mask][i] be the length of the shortest Hamiltonian walk in the subgraph generated by vertices in mask, that ends in the vertex i.

每条路径都在某个顶点结束，因此可以通过在所有 0 <= i < n ((1 << n) - 1 只是创建位集的一个好技巧，最底部的 n 位都设置为 1).

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

dp[mask][i] = min(dp[mask XOR (1 << i)][j] + d(j, i)) over all j such that bit(j, mask) = 1 and (j, i) is an edge

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

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

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

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

如何在 O(2^n) 内存和 O(2^n *n) 时间中检查哈密顿行走是否存在

How to Check for existence of Hamiltonian walk in O(2^n) of memory and O(2^n *n) of time

algorithm

language-agnostic

dynamic-programming

bitmask

bit-masks