我有一个强连接的有向图（即图 G 中的每对节点 (i, j) 都有一条从 i 到 j 和 j 到 i 的路径）。我希望从该图中找到一个强连通图，使得所有边的总和最小。
换句话说，我需要以这样的方式删除边，即删除它们后，图仍然是强连接的，并且边总和的成本最小。
我认为这是一个NP难题。我正在为 20 个节点等一小组数据寻找最佳解决方案，而不是近似值。
编辑
更一般的描述：给定一个图 G(V,E) 找到一个图 G'(V,E')，这样如果 G 中存在从 v1 到 v2 的路径，那么也存在G' 中 v1 和 v2 之间的路径与 E' 中每个 ei 之和是最小可能的。所以它类似于寻找最小等效图，只是在这里我们想要最小化边权重的总和而不是边的总和。
编辑：
到目前为止我的方法：
我想过使用多次访问的TSP来解决它，但这是不正确的。我的目标是使用最低成本路径覆盖每个城市。所以，我猜这更像是封面设置问题，但我不太确定。我需要使用总成本最小的路径覆盖每个城市，因此多次访问已经访问过的路径不会增加成本。
I have a digraph which is strongly connected (i.e. there is a path from i to j and j to i for each pair of nodes (i, j) in the graph G). I wish to find a strongly connected graph out of this graph such that the sum of all edges is the least.
To put it differently, I need to get rid of edges in such a way that after removing them, the graph will still be strongly connected and of least cost for the sum of edges.
I think it's an NP hard problem. I'm looking for an optimal solution, not approximation, for a small set of data like 20 nodes.
Edit
A more general description: Given a grap G(V,E) find a graph G'(V,E') such that if there exists a path from v1 to v2 in G than there also exists a path between v1 and v2 in G' and sum of each ei in E' is the least possible. so its similar to finding a minimum equivalent graph, only here we want to minimize the sum of edge weights rather than sum of edges.
Edit:
My approach so far:
I thought of solving it using TSP with multiple visits, but it is not correct. My goal here is to cover each city but using a minimum cost path. So, it's more like the cover set problem, I guess, but I'm not exactly sure. I'm required to cover each and every city using paths whose total cost is minimum, so visiting already visited paths multiple times does not add to the cost.
发布评论
评论（7）
您的问题称为最小跨越强子(di)图 (MSSS)，或者更一般地说，最小成本跨越子(di)图，并且是确实是 NP 难。另请参阅另一本书：第 501 页和第 480 页。
我首先删除所有不满足三角形不等式的边 - 您可以删除边 a -> c 如果去 a -> b-> c 比较便宜。这让我想起了 TSP，但不知道这是否会导致任何结果。
我之前的答案是使用 Chu-Liu/Edmonds 算法 来解决 树序问题；正如 Kazoom 和 ShreevatsaR 指出的那样，这没有帮助。
Your problem is known as minimum spanning strong sub(di)graph (MSSS) or, more generally, minimum cost spanning sub(di)graph and is NP-hard indeed. See also another book: page 501 and page 480.
I'd start with removing all edges that don't satisfy the triangle inequality - you can remove edge a -> c if going a -> b -> c is cheaper. This reminds me of TSP, but don't know if that leads anywhere.
My previous answer was to use the Chu-Liu/Edmonds algorithm which solves Arborescence problem; as Kazoom and ShreevatsaR pointed out, this doesn't help.
我会以动态编程的方式尝试这个。
0- 将图放入列表中
1- 列出前一个列表中每个图的新子图，其中为每个新子图删除一条不同的边
2- 从新列表中删除重复项
3- 从新列表中删除所有图非强连接的新列表
4- 将新列表中的最佳图与当前最佳图进行比较，如果更好，则设置新的当前最佳图
5- 如果新列表为空，则当前最佳图为解决方案，否则，递归/ Loop/goto 1
在 Lisp 中，它可能看起来像这样：
strongly-connected、list-subgraphs-1、digraph-equal的定义>、best和better留给读者作为练习。I would try this in a dynamic programming kind of way.
0- put the graph into a list
1- make a list of new subgraphs of each graph in the previous list, where you remove one different edge for each of the new subgraphs
2- remove duplicates from the new list
3- remove all graphs from the new list that are not strongly connected
4- compare the best graph from the new list with the current best, if better, set new current best
5- if the new list is empty, the current best is the solution, otherwise, recurse/loop/goto 1
In Lisp, it could perhaps look like this:
The definitions of
strongly-connected,list-subgraphs-1,digraph-equal,best, andbetterare left as an exercise for the reader.此问题相当于此处描述的问题：http://www.facebook。 com/careers/puzzles.php?puzzle_id=1
This problem is equivalent to the problem described here: http://www.facebook.com/careers/puzzles.php?puzzle_id=1
一些帮助我解决著名的facebull难题的想法：
预处理步骤：
修剪：如果有更便宜或具有相同成本的路径，则删除所有边ab，例如：acb。
图分解：如果图有铰接点，则可以解决子问题
如果只有一条出边，则将顶点合并为一个虚拟顶点。
计算步骤：
使用有向 TSP 重复访问获得近似解。使用 Floyd Warshall，然后使用匈牙利方法解决分配问题 O(N^3)。如果我们有一次循环 - 它是定向 TSP 解决方案，如果没有 - 使用分支定界 TSP。之后我们得到上界值 - 最小成本的循环。
精确解 - 分支定界法。我们从最短循环中删除顶点，并尝试以低于上限的成本构建强连通图。
这就是大家。如果您想测试您的解决方案 - 请在此处尝试：http://codercharts.com/puzzle/caribbean-salesman
Few ideas that helped me to solve the famous facebull puzzle:
Preprocessing step:
Pruning: remove all edges a-b if there are cheaper or having the same cost path, for example: a-c-b.
Graph decomposition: you can solve subproblems if the graph has articulation points
Merge vertexes into one virtual vertex if there are only one outgoing edge.
Calculation step:
Get approximate solution using the directed TSP with repeated visits. Use Floyd Warshall and then solve Assignment problem O(N^3) using hungarian method. If we got once cycle - it's directed TSP solution, if not - use branch and bound TSP. After that we have upper bound value - the cycle of the minimum cost.
Exact solution - branch and bound approach. We remove the vertexes from the shortest cycle and try build strongly connected graph with less cost, than upper bound.
That's all folks. If you want to test your solutions - try it here: http://codercharts.com/puzzle/caribbean-salesman
听起来你想使用 Dijkstra 算法
Sounds like you want to use the Dijkstra algorithm
看起来您基本上想要的是旅行推销员的最佳解决方案，其中允许节点被多次访问。
编辑：
嗯。您能否通过本质上迭代每个节点 i ，然后创建指向该节点 i 的所有边的最小生成树，并与指向远方的所有边的另一个最小生成树联合来解决这个问题 从那个节点？
Seems like what you basically want is an optimal solution for traveling-salesman where it is permitted for nodes to be visited more than once.
Edit:
Hmm. Could you solve this by essentially iterating over each node i and then doing a minimum spanning tree of all the edges pointing to that node i, unioned with another minimum spanning tree of all the edges pointing away from that node?
通过取最小内分支和最小外分支的并集来获得最小强连通子图的2近似，两者都以相同（但任意）顶点为根。
外分支，也称为树序，是一棵以单个顶点为根、跨越所有顶点的有向树。内分支与反向边缘相同。这些可以通过 Edmonds 算法及时找到 O(VE)< /em>，并且加速到O(E log(V))（请参阅wiki 页面）。甚至还有一个开源实现。
2 近似结果的原始参考文献是 JaJa 和 Frederickson 的论文 ，但该论文不能自由获取。
Adrian Vetta 甚至提出了 3/2 近似 (PDF)，但更复杂比上面的。
A 2-approximation to the minimal strongly connected subgraph is obtained by taking a union of a minimal in-branching and minimal out-branching, both rooted at the same (but arbitrary) vertex.
An out-branching, also known as arborescence, is a directed tree rooted at a single vertex spanning all vertexes. An in-branching is the same with reverse edges. These can be found by Edmonds' algorithm in time O(VE), and there are speedups to O(E log(V)) (see the wiki page). There is even an open source implementation.
The original reference for the 2-approximation result is the paper by JaJa and Frederickson, but the paper is not freely accessible.
There is even a 3/2 approximation by Adrian Vetta (PDF), but more complicated than the above.