我试图找出寻找与正沿成本曲线的推移槽节点的子集2个节点之间的最短路径的有效方式。

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.

更正式地说：

给定一个图形G =（U，V），其中U是在图中的一组的所有节点，并且V为图中的所有的边，U子集称为U'和成本函数说：

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,

我要找到一个源节点和进入低谷的所有节点U目标节点之间的最短路径。

I have to find the shortest path between a source node and a target node that goes trough all the nodes in U'.

在我访问节点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.

我最初的想法是利用罗伊 - 弗洛伊德算法生成成本矩阵。 然后，对于U中节点的我会计算源和这样的目标之间的成本每个排列：（ 1 source_node，P）F + F（P 1 ，P 2 ）+ ... + F（P K ，目标）为节省成本最低的配置，然后重建路径。

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.

在这种方法的复杂性是为O（n 3 + K！）为O（n 3 + K * K！），其中， n是图中的节点的数量和k节点的数量在子集U'，这是禁区，因为我必须处理图形最大N = 2000的节点哪个最大N - 2节点将该U'子集的一部分。

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.

推荐答案

这是旅行商的推广。如果U'== U，你得到完全TSP。

This is a generalization of travelling salesman. If U' == U, you get exactly TSP.

您可以使用为O（n ^ 2 * 2 ^ n）的TSP算法，其中的指数为满量程TSP（2 ^ n）的将降低到k = | U'|，这样你会得到O（ N ^ 2 * 2 ^ K）。

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).

这有DP解决方案，TSP。

This has the DP solution to TSP.

http://www.lsi.upc.edu /~mjserna/docencia/algofib/P07/dynprog.pdf