中国邮递员选择边的算法

Question

我有一个包含必须访问的边和可选边的图。这些边具有不同的权重，可以沿任意方向移动，并且可以根据需要多次移动。我正在尝试确定使总重量最小化的路线。在

据我所知，中国邮递员问题处理的是一个图，图的每一个边都必须至少访问一次。有人能告诉我上面描述的变量是否有一个“名称”，或者告诉我解决这类图的算法的方向吗？在

我正在尝试用Python编写一个解决方案，这样任何使用它的解决方案都会很好，否则我相信我将能够完成一个解决方案。在

我刚开始开发Python/使用算法等，如果上面的问题很明显，请原谅我！如有任何信息，我们将不胜感激。在

谢谢

亚当

Answer 1

你要解决的问题叫做农村邮递员问题，它是NP难的。搜索它会得到许多论文，其中大多数涉及启发式，例如：

• On the Rural Postman Problem: Tight Bounds and Efficient Heuristics Based on a New Formulation，2003年
• Efficient heuristics for the Rural Postman Problem，2005年