我想要一个算法或指针来进一步研究如何在加权无向图中找到两个节点之间的固定长度路径。
问问题
746 次
1 回答
0
找到从给定节点到给定长度的给定节点的简单路径是 NP 完全的：哈密顿循环问题是此类问题，它是 NP 完全的。
如果边是加权的，那么子集和问题是这个问题的一个特例，所以我们仍然是 NP 完全的
在这两种情况下，您都可以枚举路径，修剪不简单的路径或theta(b^len)预期时间过长的路径，其中b分支因子（平均出度）。
找到一条允许重复边的路径（有时称为步行）可以在 [length] 矩阵乘法中完成，总O(v^3 * len)时间复杂度或更好。
让我们A表示图的邻接矩阵。然后A^len保存每对顶点之间长度为 len 的路径数。您可以1+1 = 1在乘法期间使用（布尔加法 - 不确定它如何与高级矩阵乘法算法一起使用），那么您只会得到这样的路径，但同时避免整数溢出。
准备A^1..A^len（O(n^3 len)）。然后，对于 中的每个距离d，1..len找到一个顶点v[d]，它是 的子节点，v[d-1]并且具有len-d到目标 ( ) 的 -long 路径O(n len)。
如果您只需要知道是否存在这样的路径，那么您不需要A..A^len，只需A^len. O(n^3 log(len))您可以通过平方和乘法算法及时计算它，甚至可以O(n^2.37 log(len))与Coppersmith-Winograd 矩阵乘法算法结合使用。
或者，您可以只搜索[node x distance]状态空间并在O(n*b*len).
于 2012-11-18T15:17:53.783 回答