如何用1、0、-1权值找到精确为0成本的多维路径

Question

我得到了一个有n个节点和边的有向图，每条边都有一个长度为m的由1、0、-1数字组成的向量权重。我想找到任意一条路径（或者说这样的路径不存在），从一个节点到另一个节点（我们可以多次访问节点），使其权重之和等于只包含零的向量。我考虑使用暴力回溯算法，但不能保证它会结束。我们能否通过限制路径长度来控制n和m？以n=8，m=2为例的图形如下：

路径示例

- Kacper Kowalski

---

有趣的问题。它肯定是NP难问题，因为你可以通过设置m = n，并使每个点vi的所有入边在第i个位置上为+1，在其他位置上为0来解决（有向）哈密顿路径问题，然后再添加一个最终节点，该节点从每个其他节点连接一条入边，并在每个位置上都为-1。但我还不确定它是否属于NP问题（可能存在需要指数长的路径实例）。 - j_random_hacker

即使对于m=1，我认为它不属于NP：对于任意互质的正整数p、q，实例由两个环组成，这两个环在一个顶点相交，一个大小为p，每条边权值为+1，另一个大小为q，每条边权值为-1。这需要至少2pq长度的行走（在任何顺序下进行q次p循环和p次q循环）。但也许有一种不同的方式来编码一个在输入规模上始终是多项式的有效解决方案。或者这个问题甚至无法确定，并且可以模拟/编码图灵机 :) - j_random_hacker

抱歉，我的上一条评论显然是错误的：跨越公共顶点的2边行走就足够了。 但如果我们设置m = 4，并且有4个循环在单个顶点处相交，其中一个长度为p，具有所有向量[1 -1 0 0]，另一个长度也为p，具有所有向量[0 1 -1 0]，另一个长度为q，具有所有向量[0 0 1 -1]，另一个长度也为q，具有所有向量[-1 0 0 1]，那么每个行走必须访问所有4个循环，因此最短的行走长度为4pq。 - j_random_hacker

您对输入图有任何限制吗？（例如节点数、弧数、最大入/出度、所有向量的总和） - Dave

我想到的一个非常天真的解决方案包括三个步骤。1.识别所有循环，并为每个循环中的每个节点分配由沿着该节点所属的所有循环求和形成的可能向量。2.查找所有不重复节点的唯一路径。3.对于每条这样的路径，形成一个线性方程，它是沿着路径加权的总和以及在路径中计算的所有节点的(1)中的向量和未知向量的内积；并尝试解决每个方程。至少它是有界的。 - Sopel

Answer 1

我们可以通过注意到，如果这样的路径存在，它必须由简单路径和一些环的混合组成，从而限制路径长度的上界。每个路径最多可以有长度n。对于每个循环，我们可以有效地应用一个向量，该向量对应于通过其中一个这样的循环进行的更改。我们只能构造m个线性独立的循环（请注意，我们可能需要朝两个方向走），这足以覆盖简单路径本身的任何向量成本，因此我们可以通过正确地经过每个循环来解决任何残余（这取决于这样一条边的成本）。我们必须经过不同循环的次数的数量受到等效长度的最小公倍数的上界约束，这些不同循环的向量效果具有（大致）渐近边界O(n^2m)。如果这个上界成立（您可以通过将n分成大约n / m大小的m个区域，然后使它们成为从n / m倒数的质数长度，并将它们的依赖关系链接在一起来构造一个与之相当接近的情况，这将给出´O（（n/m）^m）`），那么解决方案的指数大小，这意味着使用（并报告）未压缩的路径长度的任何算法都不适合PSPACE（它是P和NP的超集）。

- Ninetails