Kaz*_*oom 7 algorithm graph traveling-salesman np-hard
我有一个强连接的有向图(即,对于图G中的每对节点(i,j),存在从i到j和j到i的路径).我希望从该图中找到一个强连通图,使得所有边的总和最小.
换句话说,我需要摆脱边缘,以便在移除它们之后,图形仍将是强连接的,并且边缘总和的成本最低.
我认为这是NP难题.我正在为一小组数据(如20个节点)寻找最佳解决方案,而不是近似.
编辑
更一般的描述:给定grap G(V,E)找到图G'(V,E'),使得如果在G中存在从v1到v2的路径,则在G中存在v1和v2之间的路径'和E'中每个ei的总和是最不可能的.所以它类似于找到最小等效图,只是在这里我们想要最小化边权重的总和而不是边的总和.
编辑:
到目前为止我的方法:我想过使用多次访问的TSP来解决它,但这是不正确的.我的目标是覆盖每个城市,但使用最低成本路径.所以,它更像是封面设置问题,我猜,但我不完全确定.我需要使用总成本最低的路径来覆盖每个城市,因此多次访问已访问过的路径不会增加成本.
sdc*_*vvc 12
您的问题被称为最小跨越强子(di)图(MSSS),或者更一般地说,最小成本跨越子(di)图并且确实是NP难的.另见另一本书:第501 页和第480页.
我开始删除所有不满足三角不等式的边 - 你可以删除边a - > c如果去a - > b - > c更便宜.这让我想起了TSP,但不知道这是否会带来任何影响.
我以前的答案是使用Chu-Liu/Edmonds算法来解决Arborescence问题; 正如Kazoom和ShreevatsaR指出的那样,这没有用.