给定一个加权无向图G和两个顶点a、b，我们想要找到两条路径a->b和b->a，使它们不共享任何边，并且这两条路径上所有边的权重之和最小。该图中可能有多达1,000个顶点和10,000条边。
我最初尝试使用动态规划方法来解决问题，但是没有找到可行的方案。如果您有任何想法或建议，将不胜感激。
我最初尝试使用动态规划方法来解决问题，但是没有找到可行的方案。如果您有任何想法或建议，将不胜感激。
两个指定顶点之间的最短不相交路径
5
- Chris
6
权重可以为负数吗？ - 6502
如果我正确理解了你的问题。那么首先检查是否存在两条不共享任何边的不同路径，以给定的顶点对为基础。如果存在，则在使用动态规划从源到目的地行走时，请注意所有边缘并从原始图G =（v，E）中删除这些边缘，这将减少到G'（V，E'）。然后，由于图G'已经被减少，因此尝试应用动态规划从目的地到源头... - Imposter
@6502 不，权重不能为负数。 - Chris
@冒牌者：那不行。以http://raksy.dyndns.org/graph.png为反例，其中有两条不同的路径（A345B和B12A），但是如果你从A开始寻找最小路径，你最终得到的是A12B，然后就没有回头的路了。 - 6502
@6502：他说这张图是无向的。话虽如此，我认为他试图表达的东西由于Evgeny在下面提供的反例而行不通（尽管我不明白动态规划从何而来...）。 - BlueRaja - Danny Pflughoeft
@BlueRaja-DannyPflughoeft：哦...抱歉，我把它误读为"unidirected"（像单向的），但这不知何故不是一个英语单词。 - 6502
1个回答
7
这是最小费用流问题。你可以为每条边分配流量容量等于1，然后在流量为2的情况下寻找从a到b的最小费用流。
有人可能认为可以使用简单的算法从a到b找到最短路径，然后从图中删除其边缘，再寻找另一条最短路径。但这种方法并不总是最优的。对于某些图形，它可以给出一个很好的近似值。对于其他图形，它可能会给出一个非常糟糕的解决方案：
有人可能认为可以使用简单的算法从a到b找到最短路径，然后从图中删除其边缘，再寻找另一条最短路径。但这种方法并不总是最优的。对于某些图形，它可以给出一个很好的近似值。对于其他图形，它可能会给出一个非常糟糕的解决方案：
- Evgeny Kluev
5
感谢您的解释，但有没有理论方法来证明这一点，因为上述方法有点贪心，我们选择了最短的路径前往，然后选择了最短的路径返回，所以我们实际上正在寻找局部最优解。如果可能的话，我们如何在拟阵理论中使用拟阵来理论上证明它。因为我想学习如何在拟阵理论中证明或表示这些情况。 - Imposter
@冒名顶替者：抱歉，我不明白 - 证明什么？ - Evgeny Kluev
为了证明贪心算法是否会导致最优解，我们使用拟阵理论。因此，在上述说明中，我们希望证明贪心算法不会导致最优解。我希望有人能够用拟阵理论来解释这个证明（尽管从所示的图表中很清楚，但如果图表非常复杂怎么办呢…）我可能完全错了。如果我错了，请纠正我。 - Imposter
3@Imposter: 很抱歉，我无法证明在拟阵理论的条件下非最优解。对于负面证明，只需提供一个反例就足以说明猜想是不正确的。 - Evgeny Kluev
+1 个反例，那个简单的算法是我第一个想到的，但感觉不正确 :) - BlueRaja - Danny Pflughoeft
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接