在有向循环图中查找哈密顿路径
我想知道是否有一种算法可以找到有向加权图中的最长循环路径（我认为这是找到最大哈密顿子图的问题）。
我需要从一个顶点开始并返回到同一顶点，其中遍历了最可能的节点。
谢谢
i want to know if there is an algorithm to find the longest cyclic path in a directed weighted graph (i think this i a problem of finding the largest Hamiltonian sub-graph).
I need to start from one vertex and return to the same vertex, whit the most possible nodes traversed.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
该问题是最优欧拉电路问题的特例，其中所有边权重均为 1；原问题是NP完全问题。此外，这个问题可以用来解决哈密顿图问题（当且仅当最优电路遍历所有节点时存在哈密顿环），因此即使有特殊情况的限制，它仍然是NP完全的。任何精确解（除非 P = NP）都需要指数时间。您可能会发现本文很有帮助；它描述了针对该问题的多项式时间近似算法，以及针对图的次数最多为 4 的情况的多项式时间算法：
This problem is a special case of the optimal euler circuit problem where all edge weights are 1; the original problem is NP-complete. Moreover, this problem can be used to solve the Hamiltonian Graph problem (a Hamiltonian cycle exists if and only if the optimal circuit traverses all nodes), so it remains NP-complete even with the special case restriction. Any exact solution will (unless P = NP) require exponential time. You may find this paper helpful; it describes a polynomial-time approximation algorithm for this problem, as well as a polynomial-time algorithm for cases where the graph has at most degree 4:
希尔伯特曲线给出了一个很好的近似。
A good approximation gives the Hilbert Curve.