9

输入：图 G（假设所有边都有单位权重），源-目的顶点对 (X1, Y1) , (X2 Y2) , ..., (Xk, Yk) （它们都是不同的）。

输出：路线 R1（从 X1 到 Y1）、R2（从 X2 到 Y2）、...、Rk（从 Xk 到 Yk）使得 R1、R2、...、Rk 在它们之间不共享任何顶点。无需优化路线长度。

使用什么算法？这个问题的复杂性是什么？我需要一个理论上强大的解决方案，而不是启发式的大部分时间都有效的解决方案。

最明显的解决方案是将每个自由顶点（不在 X1、X2、..Xk 或 Y1、Y2、...、Yk 中）分配给 k 条路径之一，看看它们是否真的以所需的方式形成路径。有可能的 n^k 分配（ (n-2k)^k 更准确）。我们能做得更好吗？如果我们假设图形是二维网格结构怎么办？（相当于解决https://play.google.com/store/apps/details?id=com.bigduckgames.flow 游戏，但没有满足每个方格的要求）。

4

3 回答 3

10

您可以在本文中找到一种可能的解决方案：Ken-ichi Kawarabayashi、Yusuke Kobayashi、Bruce Reed 的“二次时间中的不相交路径问题” (pdf)。

这个解决方案不是微不足道的而是高效的——只有 O(N 2 ) 时间复杂度，其中 N 是顶点的数量。只有当 K 是一个小常数时，它才是有效的。

也可以将其解决为多商品流动问题。但我怀疑任何特定于多商品的算法是否足够有效。因为一般的多商品流量问题（当至少一种商品的流量大于一种时）是 NP 难的。

这不太可能作为单一商品流动问题来解决。例如，以下是以下提议的反例：

...将 S 到 X2 和 T 到 Y2 边缘限制为容量 0.5？如果有一对不相交的路线与所需的匹配，那么从 S 到 T 的总流量可能为 1.5 ......我相信这种方法会准确报告是否存在一组不相交的路径。

                                           反例图

很容易找到容量为 1.5 的流（此流如图所示）。但是没有办法用不相交的路径连接两个（绿色和红色）顶点对。

于 2012-12-04T17:03:37.273 回答
6

您可以使用 MaxFlow 来解决这个问题。如果你不熟悉 Flow，你可以阅读一些关于它的资料。

算法

  1. 制作一个超级水槽顶点 S 和一个超级目标顶点 T。连接一些新边S -> X1, S -> X2, Y1 -> T, Y2 -> T....., S -> Xk, Yk -> T，并将每对边的容量设置为 1, 0.75, 0.5 .....
  2. 将每个顶点p分成两个新顶点p'和p"，将p'和p"与容量也为 1 的新边连接起来。
  3. 从S到T运行MaxFlow，保存流路信息。很明显，这个新图的最大流量为 2。两条流路表示所需的路线。因为算法总是找到最大流，所以最终的流路径一定是 X1 -> Y1, X2 -> Y2 ... Xk -> Yk。

证明

因为我们将每个顶点分开，并用一条容量为1的边代替，所以原图中的每个顶点都可以被一个流遍历。换句话说，它也意味着每个顶点可以属于一个路径。

延长

如果你想最小化两条路径的总长度，你可以扩展算法。在新图中添加每条边一个属性：成本。来自原始图的边的成本将为 0；并且指示单独顶点的新边的成本将为 1。您可以运行 Min-Cost-Max-Flow 算法，并获取所需的信息。

复杂

MaxFlow的复杂度是O(N * N * M)，使用Dinic算法。并且 Min-Cost-Max-Flow 的复杂度也大约为 O(N * N * N)。

于 2012-11-27T05:26:09.343 回答
2

我没有完整的解决方案，但我确实有一个可以作为第一步的减少。首先，将图分解为其双连通分量。这种分解识别了所有切割的顶点，一个顶点，如果被移除，就会将图形断开为两个组件。对于每个切割顶点，源和目标顶点对要么在切割的同一侧，作为非分割对，要么在切割的相对侧，作为分割对。（如果切割顶点也是源或目标，则将其计为分割对。）

  • 如果任何切割顶点有两个或多个分割对，则问题没有解决方案，因为两条路径都必须通过切割顶点。（这是我上面评论中梅花形图示例的概括。）

  • 如果没有拆分对，则问题会分解为两个较小的问题，每个组件上都有一个问题。解决方案是每个较小解决方案的组合。

  • 如果恰好有一个分割对，那么您将问题简化为一对较小的问题，一个在每个组件的相关版本上，其中切割顶点在图之间重复。假设切割顶点X_1在某个组件中；在该组件中标记重复的切割顶点Y_1。其他组件反之亦然。和以前一样，解决方案是两个较小解决方案的组合。

该解决方案的本质是鸽巢原理，因为两条路径不能通过一个点。上一步，三分不能过两分。这会立即导致检查三联组件并使用SPQR 树。从这个结构中，您可以枚举所有两点切割。和之前的划分一样，顶点分成两组并类似地进行，除了你必须考虑分裂对的所有排列。子问题现在都在三联组件上。

你可以看到这会导致什么。我不知道 SPQR 树是否已被推广到更高程度的连通性。即使它们曾经是，您也可以期待一般的组合爆炸。而这一切都导致了一个难题。

起初，我怀疑这个问题在平面图上很容易解决。它不是; 请参阅上面引用的论文。它仍然是NP完全的。

给定上述算法，您可以在双连通图上假设一个问题。这里的区别在于，平面图只有“局部”边（通过将图嵌入球体上可见）；“远程”边缘必须跨越其他边缘。这意味着最小割集的行为表现得更好。但表现得不够好，不足以解决问题。

于 2012-12-04T02:08:08.827 回答