K图中的互斥路线

Question

输入:图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更精确).我们可以做得更好吗？如果我们假设图形是2d网格结构怎么办？(相当于解决https://play.google.com/store/apps/details?id=com.bigduckgames.flow 游戏,但不填写每个方格要求).

Answer 1

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

这个解决方案并不简单但有效 - 只有O(N ²)时间复杂度,其中N是顶点数.只有当K是一个小常数时才有效.

也可以将其解决为多商品流问题.但我怀疑任何多商品专用算法都足够有效.因为一般的多商品流问题(当至少一种商品的流量大于一时)是NP难的.

作为单一商品流动问题,这不太可能解决.例如,以下是以下提案的反例:

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

                                           

很容易找到容量为1.5的流量(此流程如图所示).但是没有办法将两个(绿色和红色)顶点对与不相交的路径连接起来.

Answer 2

您可以使用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. 将MaxFlow从S运行到T,并保存流路径的信息.显然,这个新图的最大流量是2.并且两个流路径指示所需的路线.因为算法总是找到最大流量,所以最终流量路径必须是X1 - > Y1,X2 - > Y2 ...... Xk - > Yk.

证明

因为我们将每个顶点分开并由一个容量为1的边替换,所以原始图中的每个顶点都可以遍历一个流.换句话说,它还意味着每个顶点可以属于一个路径.

延伸

如果要最小化两个路径的总长度,可以只扩展算法.在新图表中添加一个属性:cost.原点图的边成本为0; 并且表示单独顶点的新边的成本将为1.您可以运行Min-Cost-Max-Flow算法,并获取所需信息.

复杂

通过使用Dinic算法,MaxFlow的复杂度为O(N*N*M).并且Min-Cost-Max-Flow的复杂度也约为O(N*N*N).