如何找到具有1，0，-1权重的精确0成本的多维路径

Question

我得到了有向图，其中有n个节点，边为具有向量1（0，-1）的向量（每个向量的长度为m）的维数。我想找到从一个节点到另一节点（我们可以多次访问节点）的任何路径（或者说这种路径不存在），这样其权重之和就等于零向量。我当时在考虑蛮力回溯算法，但不能保证它会结束。我们可以以n和m的方式限制这种路径的长度吗？n = 8，m = 2的图形示例 路径示例

Answer 1

我们可以对路径的长度进行上限，注意如果这样的路径存在，它必须由简单路径和一些循环的混合组成。每条路径的长度最多为 n。对于每个周期，我们可以有效地应用一个向量，该向量与经历其中一个周期所发生的变化相对应。我们只能构建彼此线性独立的 m 个循环（请注意，我们可能需要在两个方向上进行），这足以覆盖简单路径本身成本的任何向量，因此我们可以通过遍历每个循环来解决任何残差循环正确的次数（这取决于此类边缘的成本）。我们必须经历不同循环的次数的上限等于不同循环的每个向量效应的有效长度的最低公共乘数，其具有（粗略）渐近界限O(n^2m)。如果这个上限成立（您可以通过将 n 分成大小大约为 n/m 的 m 个区域来构建一个相当接近它的情况，然后让它们从 n/m 开始倒数素数长度，然后将它们的依赖关系链接在一起，这将给出 \xc2\xb4O((n/m)^m)`)，则解为指数大小，这意味着任何使用（并报告）未压缩路径长度的算法都不适合 PSPACE（它是 P 的超集）和 NP）。

\n