用于解决无向加权图的中国邮递员问题的Dart包

如何以最短的路径遍历每条边并返回起点

img.png

将 chinese_postman: ^0.1.0 添加到 pubspec.yaml

import 'package:chinese_postman/chinese_postman.dart';

void main() {
  
  Postman p = Postman();
  
  // Repeating entries in the graph will not add duplicate edges. 
  // If the original graph contains duplicate edges,
  // add new vertices with a distance of 0 from other vertices.

  Map<int, Map<int, double>> graph = {
    1: {2: 6, 5: 10, 4: 10, 3: 10},
    2: {5: 7, 7: 16},
    3: {4: 10, 6: 7},
    4: {5: 1, 6: 5},
    5: {7: 7},
    6: {7: 13},
    //This will not change the result
    //since the edges are already above
    // 7: {2: 16, 5: 7, 6: 13}
  };

  List<int> tour = p.postmanTour(graph, startingVertex: 2);

  print(tour);
  print('total cost: ${p.cost()}');
}

输出如下

[2, 5, 7, 5, 4, 1, 3, 4, 6, 3, 6, 7, 2, 5, 1, 2]
total cost: 123.0

起点/终点顶点为2。

上面的列表显示了遍历每条边并返回顶点2的路径。

解决方案中的某些边是重复的。这是不可避免的。有关如何解决该问题的更详细解释如下。

中国邮递员问题

首先，图必须是连通的（任意两个顶点之间都应该存在路径）。

disconnected.png

connected.png

首先要做的是计算连接每个顶点的边数（称为顶点的“度”）。

如果度数为奇数，则该顶点称为“奇顶点”。

如果没有奇顶点，则存在一个最优解，其中没有边重复。这称为“欧拉路径”。

在连通图中，奇顶点的数量总是偶数。

对于上面连通的示例，奇顶点为2、3、6和7。我们必须将它们配对以最小化行驶距离。这将告诉我们哪些边需要重复。

只有3种匹配方式

1 – [2,3],[6,7]

2 – [2,6],[7,3]

3 – [2,7],[6,3]

但对于更多的顶点，数量会急剧增加。（对于16个奇顶点，将有超过200万种匹配方式。）因此，我们需要一种更有效的算法来找到最优匹配。该包使用了Edmonds的带花算法。

[Dart代码是从 simlu 和 mattkrick 的存储库翻译而来，这些存储库基于 此 Python实现。代码已被修改为查找最小成本匹配而不是最大成本匹配。]

注意：对于像上面这样的加权图，每条边的长度并不对应于所绘制直线的长度，因此两个奇顶点之间的最短路径可能不是一条直线。

例如，顶点2和7之间的最短距离不是长度为16的直线，而是从顶点2到5再到7，总长为14。

[此包使用 dijkstra 包来查找每对奇顶点之间的最短距离。]

每对奇顶点之间的总距离或成本为

[2,3],[6,7] = 16 + 13 = 29

[2,6],[7,3] = 13 + 18 = 31

[2,7],[6,3] = 14 + 7 = 21

所以我们选择第三种方案。我们需要重复2到7之间给出最短路径的边（重复2到5和5到7），并重复6到3。

现在重复的边使图成为欧拉图。 Hierholzer算法 用于查找遍历每条边的顺序，由红色数字显示。

eulerian.png

GitHub

查看 Github