查找图中两个节点之间经过节点子集的最短路径
我试图找到一种有效的方法来找到图中两个节点之间的最短路径，其正边成本穿过节点的子集。
更正式地
说：给定一个图 G = (U, V)，其中 U 是图中所有节点的集合，V 是图中所有边的集合，U 的子集称为 U'，成本函数为：
f : UxU -> R+
f(x, y) = cost to travel from node x to node y if there exists an edge
between node x and node y or 0 otherwise,
I必须找到源节点和目标节点之间经过 U' 中所有节点的最短路径。
我访问 U' 中的节点的顺序并不重要，并且我可以多次访问一个节点。
我最初的想法是利用Roy-Floyd算法来生成成本矩阵。 然后，对于 U' 中节点的每个排列，我将计算源和目标之间的成本，如下所示：f(source_node, P1) + f(P1) sub>, P2) + ... + f(Pk, target) 以最低成本保存配置，然后重建路径。
此方法的复杂度为 O(n3 + k!) O(n3 + k*k!)，其中 n 是图中的节点数和 k 子集 U' 中的节点数，这是不受限制的，因为我必须处理最大 n = 2000 个节点的图，其中最大 n - 2 个节点将成为U'子集。
I'm trying to find out an efficient way of finding the shortest path between 2 nodes in a graph with positive edge costs that goes trough a subset of nodes.
More formally:
Given a graph G = (U, V) where U is the set of all nodes in the graph and V is the set of all edges in the graph, a subset of U called U' and a cost function say:
f : UxU -> R+
f(x, y) = cost to travel from node x to node y if there exists an edge
between node x and node y or 0 otherwise,
I have to find the shortest path between a source node and a target node that goes trough all the nodes in U'.
The order in which I visit the nodes in U' doesn't matter and I am allowed to visit a node more than once.
My original idea was to make use of Roy-Floyd algorithm to generate the cost matrix.
Then, for each permutation of the nodes in U' I would be computing the cost between the source and the target like this: f(source_node, P1) + f(P1, P2) + ... + f(Pk, target) saving the configuration for the lowest cost and then reconstructing the path.
The complexity for this approach is O(n3 + k!) O(n3 + k*k!), where n is the number of nodes in the graph and k the number of nodes in the subset U', which is off limits since I'll have to deal with graphs with maximum n = 2000 nodes out of which maximum n - 2 nodes will be part of the U' subset.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是旅行推销员的概括。如果 U' == U，则恰好得到 TSP。
您可以使用 O(n^2 * 2^n) TSP 算法，其中满量程 TSP (2^n) 的指数因子将减少到 k = |U'|，因此您将得到 O(n^2 * 2^k）。
这就有了TSP的DP解。
http://www.lsi.upc.edu/~mjserna /docencia/algofib/P07/dynprog.pdf
This is a generalization of travelling salesman. If U' == U, you get exactly TSP.
You can use the O(n^2 * 2^n) TSP algorithm, where the exponential factor for full scale TSP (2^n) will reduce to k = |U'|, so you'd get O(n^2 * 2^k).
This has the DP solution to TSP.
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
将源节点s和目标节点t合并为单个节点z，并定义节点集U'' := U ' 并集 {z}，到 z 的距离由 f(z,x) := f(s,x) 和 定义>f(x,z) := f(x,t) 对于U \ {s, t} 中的所有x。计算 U'' 的所有节点之间的最短路径，并令 f'(x,y) 为最短距离，如果没有合适的路径，则为无穷大。瞧，您现在在带有顶点 U'' 和边权 f' 的完整有向图上遇到了旅行商问题。
Combine the source node s and target node t into a single node z, and define the node set U'' := U' union {z}, with the distances to and from z defined by f(z,x) := f(s,x) and f(x,z) := f(x,t) for all x in U \ {s, t}. Compute shortest paths between all nodes of U'' and let f'(x,y) be the shortest distances, or infinity when there is no appropriate path. Voila, you now have a travelling salesman problem on the complete directed graph with vertices U'' and edge weights f'.