algorithm - 使用预言机在多项式时间内找到汉密尔顿路径

Question

假设您有一个预言机，可以（在多项式时间内）确定某个图中是否存在汉密尔顿路径。（提醒：汉密尔顿路径问题在 NPC 中）。

描述如何使用预言机在多项式时间内在图中找到一条汉密尔顿路径。

有任何想法吗？

Answer 1

哈密​​顿路径恰好访问每个顶点一次。

如果你有一个预言机，你可以测试依次删除每条边。如果预言机说还有一条路径，则保持删除边缘，否则恢复边缘并尝试下一个。

一旦你通过了所有的边缘，剩下的就是哈密顿路径。

Answer 2

如果图中有 n - 1 条边，我们就完成了（它必须是一条链。否则，没有哈密顿路径）。

否则，我们可以删除一些边。让我们遍历所有边。如果图中仍有一条没有固定边的路径，我们可以删除它并继续前进。

该解决方案需要 O (m^2) 次预言机查询，因此它可以在多项式时间内工作。