最低成本强连通有向图(Minimum cost strongly connected digraph

我有强烈连接（即，存在从i到j和j在图G每对节点的（I，J）的路径至i）有向图。我想找出这个图的强连通图，使得所有边的总和最小。

换一种说法，我需要以这样的方式来摆脱边缘的，取消他们之后，图表仍然会强连接和边缘的总和的最低成本。

我认为这是一个NP难问题。我正在寻找最佳的解决方案，不近似，对于一小部分像20个节点的数据。

编辑

更一般的描述：给定一个GRAP G（V，E）发现的图G“（V，E”），使得如果存在从V1的路径G中v2的比也存在v1和v2中G的路径“和E各自EI的总和”是尽可能少的。所以它类似于找到最低相当于图，只有在这里，我们希望尽量减少边权的边缘的总和，而不是总和。

编辑：

我的做法至今：我想用TSP与多次访问解决它，但它是不正确的。在这里，我的目标是覆盖每个城市，但使用成本最低的路径。所以，它更像封面设置问题，我想，但我不能完全确定。我需要支付每使用，其总成本最小的路径的每一个城市，所以访问已访问过的路径多次不增加成本。

Answer 1:

你的问题被称为最小生成树强子（DI）图 （MSSS）或更一般地，最低的成本跨越子（DI）图和为NP-艰难的。又见另一本书： 501页和480页。

我与消除不满足三角不等式所有边缘开始 - 可以去除边缘 - > c。如果去一个 - “乙 - > c是便宜。这让我想起了TSP的，但不知道是否导致任何地方。

我以前的答案是使用楚刘/埃德蒙兹算法解决了树状的问题; 作为Kazoom和ShreevatsaR指出，这并不能帮助。

Answer 2:

我会在一个动态规划的一种方式试试这个。

0-将图表放入一个列表

1-使在前面的列表，在这里你删除一个不同的边缘为每个新子图的每个图的新的子图的列表

从将新列表2-删除重复

3-从非强连接新的列表中删除所有图表

4-从新列表与目前最好的比较最好的图形，如果更好，设置新的当前最佳

5-如果新的列表为空，当前最好的是溶液，否则，递归/循环/ GOTO 1

在Lisp中，它也许可以是这样的：

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

的定义strongly-connected ， list-subgraphs-1 ， digraph-equal ， best和better的作为一个练习留给读者。

Answer 3:

这个问题等同于这里所描述的问题： http://www.facebook.com/careers/puzzles.php?puzzle_id=1

Answer 4:

一些想法，帮助我解决了著名facebull之谜：

预处理步骤：

修剪：删除所有边AB，如果有更便宜的或具有相同的成本的路径，例如：ACB。
图分解：你能解决的子问题，如果有图有铰接点
合并顶点到一个虚拟顶点如果仅存在一个出边。

计算步骤：

利用定向TSP反复考察获得近似解。使用弗洛伊德沃肖尔进而解决使用匈牙利语方法分配问题O（N ^ 3）。如果我们得到了一次循环 - 它是针对TSP解决方案，如果没有 - 使用分支限界TSP。之后，我们就得上限值 - 最小成本的周期。
精确解 - 分支和约束的做法。我们请从最短周期的顶点，并尝试用更低的成本建立强连通图，超过上限。

这是所有乡亲。如果你想测试你的解决方案-在这里试试吧： http://codercharts.com/puzzle/caribbean-salesman