问如何检验记忆的O(2^n)和时间的O(2^n *n)中哈密顿游动的存在性

EN

术语：

1. binary (x)的意思是x是基于2的。
2. 从0开始编号的节点
3. mask总是表示节点的set。节点i在mask中，意思是2^i AND mask != 0。同样，set mask-i (此处-表示从集合中移除i )可以表示为位掩码中的mask XOR 2^i。

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

1. i in mask
2. 节点mask集存在汉密尔顿游走，其结束为节点i。

例如，dp[binary(1011)] = binary(1010)意味着binary(1011) (以节点1结尾)存在汉密尔顿步行，而以节点3结尾的binary(1011)则存在另一个汉密尔顿步行。

因此，对于N节点，如果dp[2^N - 1] != 0，则对所有节点都存在汉密尔顿步行。

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

当mask只包含一个节点时，i

dp[2^i] = 2^i (这意味着对于单个节点来说，步行总是存在的，其结束于自身。

否则

给定mask，根据dp[mask]的定义，对于mask中的每个节点i，我们想知道mask是否存在步行，是否以i结束。为了计算这一点，我们首先检查节点集mask-i是否存在任何遍历，然后在这些mask-i行之间进行检查，在连接到i的节点j上是否有步行结束。因为将它们结合在一起，我们就可以走到mask的尽头，以i为终点。 为了加快这一步，我们将M[i]预处理为连接到i的所有注释的位掩码。所以i in dp[mask] if dp[mask XOR 2^i] AND M[i] != 0。 为了进一步解释这个步骤，dp[mask XOR 2^i]是mask-i可以结束的节点集合，M[i]是直接连接到i的节点集。因此，它们的AND意味着是否存在以i结尾的任何类型的mask。

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)

编辑:看到另一个答案后，我意识到我回答错了问题。也许这个信息还是有用的？如果没有，我会删除这个。在评论中让我知道.

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

设by掩码是掩码中顶点生成的子图中最短哈密顿游动的长度，以顶点i结束。

每条路径都以某个顶点结束，因此可以通过在所有0 dp[(1 << n) - 1][i] i(1 << n) - 1只是一个很好的技巧，用于创建一个位集，其中最底层的n位全部设置为1)。

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

所有j上的d掩码=min(dp掩码XOR (1 << i) + d(j，i))，使得位(j，掩码)=1，且(j，i)是边

因此，为了填充dp[mask][i]，我们想要解决mask中顶点集合的子问题，在路径中的最后一个顶点是i的约束下。首先，请注意，任何通过P中所有顶点并以i结束的路径都必须有最终的边(假设mask中至少有两个顶点)。这个边将从非i顶点j在mask，到i.为了方便起见，让k是mask中具有i外边的顶点的数目。假设Q是与P相同的路径，但是它的最后一个边(j, i)被丢弃了:那么P的长度是length(Q) + d(j, i)。由于任何路径都可以通过这种方式分解，我们可以根据mask到i的最终边缘将所有路径分解为k组，找到每个组中的最佳路径，然后选择这些k最小值中的最佳路径，这将保证我们没有忽略任何可能性。

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

起初，按最终边缘分组似乎没有多大帮助。但是请注意，对于特定的j选择，任何以j结束并最小化length(Q) + d(j, i)的路径Q也会最小化length(Q)，反之亦然，因为当j (当然还有i)被修复时，d(j, i)只是一个固定的额外成本。碰巧我们已经知道了这样一条路径(或者至少它的长度，这是我们真正需要的)：它是dp[mask XOR (1 << i)][j]！(1 << i)的意思是“二进制整数1移位左i时间”--这创建了一个由单个顶点组成的位集，即i；XOR的作用是从mask中删除这个顶点(因为我们已经知道对应的位在mask中必须是1)。总而言之，mask XOR (1 << i)在更多的数学表示法中是mask \ {i}的意思。

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