graph - 在有向循环图中找到哈密顿路径

Question

我想知道是否有一种算法可以在有向加权图中找到最长的循环路径（我认为这是找到最大哈密顿子图的问题）。

我需要从一个顶点开始并返回到同一个顶点，遍历最可能的节点。

谢谢

Answer 1

这个问题是最优欧拉电路问题的一个特例，所有边的权重都为 1；原来的问题是NP完全的。此外，该问题可用于解决哈密顿图问题（当且仅当最优电路遍历所有节点时才存在哈密顿循环），因此即使有特殊情况限制，它仍然是 NP 完全的。任何精确解（除非 P = NP）都需要指数时间。您可能会发现本文很有帮助；它描述了针对该问题的多项式时间逼近算法，以及针对图最多为 4 次的情况的多项式时间算法：

乔，于。“最大连续成本的最优欧拉电路。” IEICE 翻译 基本原理 E90-A，编号。1 (2007): 274-280。

Answer 2

一个好的近似值给出了希尔伯特曲线。