python - 某些边缘可选的中国 postman 算法

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年