我有一个强连接的有向图（即图 G 中的每对节点 (i, j) 都有一条从 i 到 j 和 j 到 i 的路径）。我希望从该图中找到一个强连通图，使得所有边的总和最小。
换句话说，我需要以这样的方式删除边，即删除它们后，图仍然是强连接的，并且边总和的成本最小。
我认为这是一个NP难题。我正在为 20 个节点等一小组数据寻找最佳解决方案，而不是近似值。
Edit
更一般的描述：给定一个图 G(V,E) 找到一个图 G'(V,E')，如果 G 中存在从 v1 到 v2 的路径，则 G 中也存在 v1 和 v2 之间的路径' 并且 E' 中每个 ei 的总和是最小可能的。所以它类似于寻找最小等效图，只是在这里我们想要最小化边权重的总和而不是边的总和。
Edit:
到目前为止我的方法：
我想过使用多次访问的TSP来解决它，但这是不正确的。我的目标是使用成本最低的路径覆盖每个城市。所以，我猜这更像是封面设置问题，但我不太确定。我需要使用总成本最小的路径覆盖每个城市，因此多次访问已经访问过的路径不会增加成本。
你的问题被称为最小跨度强子(di)图（MSSS），或者更一般地说，跨越子（di）图的最小成本，并且是。另见另一本书： and .
我首先删除所有不满足三角形不等式的边 - 如果 a -> b -> c 更便宜，则可以删除边 a -> c 。这让我想起了 TSP，但不知道这是否会导致任何结果。
我之前的回答是使用Chu-Liu/Edmonds 算法 http://en.wikipedia.org/wiki/Edmonds%27s_algorithm这解决了树状 http://en.wikipedia.org/wiki/Arborescence_%28graph_theory%29问题;正如 Kazoom 和 ShreevatsaR 指出的那样，这没有帮助。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
