最小成本强连通有向图 [英] Minimum cost strongly connected digraph

查看:155
本文介绍了最小成本强连通有向图的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有强烈连接(即有从i的路​​径j和j为i的每对节点的(I,J)中的图G)一个有向图。我希望能够找到一个强连接图出该曲线图,使得所有边的总和是最小的。

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.

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

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.

修改

一个更一般的描述:给定一个GRAP G(V,E)的发现图G'(V,E'),使得如果比还存在V1之间的路径存在从v1的G中的路径v2和V2'在电子商务各EI和求和G中是最可能的。因此,其类似寻找最小等效图,只有在这里我们希望尽量减少边权边的总和,而不是总和

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.

编辑:

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

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.

推荐答案

您的问题是更普遍被称为最小生成树强子(二)图(MSSS),或者,最低的成本跨越子(迪)​​图,是 NP-艰难的。又见另一本书:页501 和的 480页

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.

我会先移除不满足三角不等式所有的边缘 - 你可以删除边缘 - > c。如果去一个 - > B - > c是便宜。这使我想起TSP的我,但不知道这是否导致任何地方。

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.

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

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.

这篇关于最小成本强连通有向图的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆