如何在无向加权图中找到最长（最重）的轨迹？
我有一张美国空间地图，用权重（距离）连接城市。我想找到这张地图上最长（最重）的路径。
- 每条边被访问 0 或 1 次，
- 每个节点可以被访问 [0, inf) 次。
不要求所有节点或边都需要被访问。
方法和序言资源建议就可以了。
I have a US spatial map connecting cities with weights (distances). I'd like to find the longest (most weighted) trail in this map.
- each edge is visited 0 or 1 times
- each node can be visited [0, inf) times.
There's NO requirement that all the nodes or the edges need to be visited.
Method and prolog resources suggestions would be fine.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不知道我是否正确，但你可以尝试以下操作：
你可以检查该图是否是欧拉图。如果是这样，您的问题是找到欧拉电路，这可以在多项式时间内完成。
否则你就会遇到问题，因为如果我没有错的话，你必须找到最大（可能诱导的）欧拉子图，这是 NP 难的。
当然，一切都假设所有权重都是非负的。
I do not know whether I am correct but you could try the following:
You can check if the graph is Eulerian. If so your problem is to find the euler circuit, which can done in polynomial time.
Otherwise you have a problem, because if I am not wrong you have to find the maximum (possibly induced) Eulerian sub-graph, which is NP-hard.
Of course, everything is assuming that all weights are non-negative.