我试图证明最短权重约束路径问题的 NP 完备性。我已经阅读了多篇论文，但是看在上帝的份上，无法弄清楚如何将其减少为分区问题。
问题是针对每条边给出的，权重 w 和长度 l，表明对于无向图，寻找路径的问题使得路径上的权重总和 < W 并且路径的长度总和 < L 其中，L和 W 是问题中给我们的常数。
我查看了 Garey 和 Johnson，它只是指出问题是 NP 完全的，并且没有提供证明或减少的方法。
我试图证明最短权重约束路径问题的 NP 完备性。我已经阅读了多篇论文，但是看在上帝的份上，无法弄清楚如何将其减少为分区问题。
问题是针对每条边给出的，权重 w 和长度 l，表明对于无向图，寻找路径的问题使得路径上的权重总和 < W 并且路径的长度总和 < L 其中，L和 W 是问题中给我们的常数。
我查看了 Garey 和 Johnson，它只是指出问题是 NP 完全的，并且没有提供证明或减少的方法。