最小路径 - 所有边至少有一次

我有很多周期的定向图，可能强烈连接，我需要从它得到一个最小周期。我的意思是我需要得到循环，这是图中最短的循环，并且每条边至少覆盖一次。最小路径 - 所有边至少有一次

我一直在寻找一些算法或一些理论背景，但只有我发现的东西是中国邮差算法。但是这个解决方案不适用于有向图。

任何人都可以帮助我吗？由于

编辑>>那图的所有边缘具有相同的成本 - 例如1

来源

2010-03-01 joseph

听起来像功课吗？ – 2010-03-01 21:16:08

我想到的第一件事是欧拉电路，但只是为了检查：每条边*至少*一次，或*正好*一次？ – ephemient 2010-03-01 21:16:22

不是作业，我至少需要一次，因为我没有保证，我会用eulerian循环来应用它。 – joseph 2010-03-01 21:21:07

看看这篇论文 - Directed Chinese Postman Problem。这是正确的问题分类，虽然（假设没有更多的限制）。

如果您刚刚阅读理论，请阅读this page（来自算法设计手册）。

密钥引号（下半年定向版本）：

最佳邮递员游可以通过添加适当的边缘与图G被构造成使它欧拉。具体而言，我们找到G中每对奇数顶点之间的最短路径。在G中的两个奇数顶点之间添加一条路径将它们都变成偶数度，从而使我们更接近欧拉图。寻找最佳的加入到G中的最短路径集合归结为在奇数度顶点上的图中确定最小权重的完美匹配，其中边（i，j）的权重是从i到最短路径的长度学家对于有向图，这可以使用二分匹配来解决，其中顶点根据它们是否具有更多的入边或出边来进行分区。一旦图形是欧拉，可以使用上述过程以线性时间提取实际周期。

来源

2010-03-01 21:18:28 Larry

谢谢，那正是我所需要的 – joseph 2010-03-01 21:31:27

我怀疑这是最佳的，但你可以做一个基于队列的搜索假设图会被保证有一个周期。每个队列条目将包含表示路径的节点列表。当您将某个元素从队列中取出时，请将所有可能的下一步添加到队列中，以确保您没有重新访问节点。如果最后一个节点与第一个节点相同，则找到最小周期。

来源

2010-03-01 21:16:59 recursive

你在找什么叫做“欧拉路径”。你可以谷歌找到足够的信息，基本是here 而关于算法，有一个名为弗勒的算法的算法，谷歌，或看看here

来源

2010-03-01 21:21:48 Maxym

区别在于，对于欧拉路径，您只想访问每个边缘一次。 – Larry 2010-03-01 21:22:39

是的，我刚刚注意到了，谢谢......嗯......图中有两种循环 - >要么wo访问每个顶点一次或每个边...那么它应该是“哈密顿路径” – Maxym 2010-03-01 21:28:34

“2009年7月，发表在“生物工程杂志”上的研究表明，一台细菌计算机可以用来解决简单的哈密顿路径问题（使用三个位置）“ from http://en.wikipedia.org/wiki/Hamiltonian_path_problem :)） – Maxym 2010-03-01 21:32:50

，其中的网络完全由有向边的特殊情况下，可以用多项式时间求解。我认为原始纸张Matching, Euler tours and the Chinese postman (1973) - 算法用于向图问题的清楚描述开始第115页（第28页的PDF）：

当所有的连通图的边缘的定向和图是对称的，有一个特别简单的和有吸引力的算法指定欧拉回路...

找到定向，对称，连接图形的欧拉回路G是首先找到的跨越树状该算法G.然后，在任何节点n，除了树木的根r，指定任何顺序的边缘指向一个只要树木的边缘在排序中是最后一个，就从n开始。对于根r，指定远离r的边的任何顺序。

该算法被van Aardenne-Ehrenfest和de Bruin用于列举了某个有向图[1]中的所有Euler巡回。

来源

2010-03-01 21:28:37

最小路径 - 所有边至少有一次

回答

相关问题