如何在图中找到哈密尔顿周期 [英] How to find Hamiltonian Cycle in a Graph

问题描述

我试图解决哈密尔顿周期问题。我能够找到所有顶点的路径，但无法完成周期。

有人可以提供一个算法来找到这个循环吗？

解决方案

确定一个图是否有哈密尔顿周期一个NP完全问题。这意味着我们可以检查给定路径是否为多项式时间内的哈密尔顿循环，但我们不知道任何能够找到的多项式时间算法。

可用于查找哈密尔顿循环的唯一算法是指数时间算法。其中一些是

• 蛮力搜索


• 动态编程


• 您可以在此处找到其他指数级但速度更快的算法

ul>


I am trying to solve the Hamiltonian Cycle problem. I am able to find a path with all the vertices, but unable to complete the cycle.

Can someone provide me with an algorithm to find the cycle?

解决方案

Determining if a graph has a Hamiltonian Cycle is a NP-complete problem. This means that we can check if a given path is a Hamiltonian cycle in polynomial time, but we don't know any polynomial time algorithms capable of finding it.

The only algorithms that can be used to find a Hamiltonian cycle are exponential time algorithms. Some of them are

• Brute force search
• Dynamic programming
• Other exponential but nevertheless faster algorithms that you can find here

这篇关于如何在图中找到哈密尔顿周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！