8

我有一个强连接的有向图（即，对于图 G 中的每对节点（i，j），都有一条从 i 到 j 和 j 到 i 的路径）。我希望从这个图中找到一个强连通图，使得所有边的总和最小。

换句话说，我需要以这样一种方式摆脱边缘，即在移除它们之后，图形仍将是强连接的，并且边缘总和的成本最低。

我认为这是一个NP难题。我正在为一小组数据（如 20 个节点）寻找最佳解决方案，而不是近似值。

编辑

更一般的描述：给定一个图 G(V,E) 找到一个图 G'(V,E') 使得如果在 G 中存在从 v1 到 v2 的路径，那么在 G 中也存在 v1 和 v2 之间的路径' 和 E 中每个 ei 的总和是最不可能的。所以它类似于找到一个最小等价图，只是在这里我们想要最小化边权重的总和而不是边的总和。

编辑：

到目前为止我的方法：我想过使用多次访问的 TSP 来解决它，但它是不正确的。我的目标是覆盖每个城市，但使用最低成本路径。所以，我猜这更像是封面设置问题，但我不确定。我需要使用总成本最低的路径覆盖每个城市，因此多次访问已经访问过的路径不会增加成本。

4

7 回答 7

12

您的问题被称为最小跨度强子（二）图（MSSS），或者更一般地说，最小成本跨度子（二）图并且确实是NP-hard。另见另一本书：第 501页和第 480 页。

我将从删除所有不满足三角形不等式的边开始 - 如果 a -> b -> c 更便宜，您可以删除边 a -> c。这让我想起了 TSP，但不知道这是否会导致任何地方。

我之前的回答是使用解决树状问题的Chu-Liu/Edmonds 算法；正如 Kazoom 和 ShreevatsaR 指出的那样，这无济于事。

于 2009-10-10T20:14:31.623 回答
2

我会以动态编程的方式尝试这个。

0- 将图表放入列表中

1-列出上一个列表中每个图的新子图，其中为每个新子图删除一条不同的边

2-从新列表中删除重复项

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

4-将新列表中的最佳图表与当前最佳图表进行比较，如果更好，则设置新的当前最佳图表

5-如果新列表为空，则当前最佳为解决方案，否则，递归/循环/转到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留给读者作为练习。

于 2009-10-08T08:30:27.980 回答
1

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

于 2010-01-04T19:40:36.550 回答
1

帮助我解决著名的facebull难题的几个想法：

预处理步骤：

  1. 修剪：如果有更便宜或具有相同成本路径，则删除所有边 ab，例如：acb。

  2. 图分解：如果图有关节点，则可以解决子问题

  3. 如果只有一条出边，则将顶点合并为一个虚拟顶点。

计算步骤：

  1. 使用有向 TSP 反复访问得到近似解。使用 Floyd Warshall，然后使用匈牙利方法解决分配问题 O(N^3)。如果我们有一次循环 - 它是定向 TSP 解决方案，如果没有 - 使用分支和绑定 TSP。之后我们就有了上限值——最小成本的循环。

  2. 确切的解决方案 - 分支和绑定方法。我们从最短循环中删除顶点，并尝试以低于上限的成本构建强连通图。

这就是所有人。如果您想测试您的解决方案 - 在这里尝试： http: //codercharts.com/puzzle/caribbean-salesman

于 2012-05-31T14:15:48.337 回答
0

似乎您基本上想要的是旅行推销员的最佳解决方案，其中允许多次访问节点。

编辑：

唔。你能通过本质上迭代每个节点 i 来解决这个问题，然后做一个指向该节点 i 的所有边的最小生成树，与指向远离该节点的所有边的另一个最小生成树联合吗？

于 2009-10-08T07:12:50.960 回答
0

听起来你想使用Dijkstra 算法

于 2009-10-08T07:17:38.060 回答
0

最小强连通子图的 2 近似值是通过将最小内分支和最小外分支联合来获得的，两者都以相同（但任意）顶点为根。

分支，也称为树状，是一个有向树，其根植于跨越所有顶点的单个顶点。内分支与反向边缘相同。这些可以通过Edmonds 的算法在O(VE)时间内找到，并且可以加速到O(E log(V))（参见wiki 页面）。甚至还有一个开源实现。

2 近似结果的原始参考是JaJa 和 Frederickson的论文，但该论文不可免费访问。

Adrian Vetta (PDF)甚至有一个 3/2 的近似值，但比上面的更复杂。

于 2017-01-20T10:50:49.603 回答