如何找到具有1，0，-1权重的精确0成本的多维路径 [英] How to find multidimensional path of exact 0 cost with 1, 0, -1 weights

问题描述

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

I was given directed graph with n nodes and edges with weigths of vectors (every vector has length m) of numbers 1, 0, -1. I would like to find any path (or say that such path doesn't exist) from one node to other (we can visit nodes many times) such sum of its weights equals to vector of only zeros. I was thinking of bruteforce backtracking algorithm but it is not guaranteed that it would end. Can we somehow limit length of such path in terms of n and m? Example of graph for n=8, m=2 Example of path

推荐答案

我们可以通过指出如果存在这样的路径来限制路径长度的上限，该路径必须由简单路径和一些循环组成。这些路径中的每条路径最多可以具有n个长度。对于每个循环，我们都可以有效地应用一个向量，该向量与经历这样一个循环而发生的变化相对应。我们只能构造彼此线性独立的m个周期（请注意，我们可能需要双向移动），这足以覆盖简单路径本身所花费的任何矢量，因此我们可以通过遍历每个周期来解决任何残差循环正确的时间（这取决于这种优势的成本）。我们必须经历的不同周期的时间上限由一个等于最小公倍数的上限来表示，不同周期的每个矢量效应的有效长度都具有最低公倍数，其（粗糙）共济会边界 O（n ^ 2m）。如果这个上限成立（您可以通过将n划分为大小为n / m的m个区域，然后使它们的质数长度从n / m开始倒数，然后将它们的依存关系链接在一起，来构造一个合理接近的案例。将给出´O（（n / m）^ m）`），则解为指数大小，这意味着使用（并报告）未压缩路径长度的任何算法都不适用于PSPACE（P和NP的超集） ）。

We can upper bound the length of the path, by noting that if such a path exists it must consists of a mix of a simple path and some cycles. Each of those paths can have at most lenght n. For each cycle we can effectively apply a vector that corrispond to the change that happens by going through one of such cycles. We can only construct m cycles that are linearly indepednt of each other (note that we might need to go in both directions), which is sufficient to cover any vector that the simple path itself costs, so we can resolve any residual by going through each cycle the right amount of times (this relies on the cost of such an edge). The amount of times we have to go through the different cycles is upper bounded by something equivalent to the lowest common multiplier for the effective lengths of each of the vectors effects of the different cycles, which has the (rough) assymtotic bound O(n^2m). If this upper bound holds (you can construct a case reasonably close to it by sperating n into m regions of size roughly n/m, and then have them prime number lengths counting down from n/m, and then chain their dependencies together, which would give ´O((n/m)^m)`), then the solution as exponential size, which means any algorithm that uses (and reports) uncompressed path lengths would not fit in PSPACE (which is a superset of P and NP).

这篇关于如何找到具有1，0，-1权重的精确0成本的多维路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！