用回溯法求哈密顿通路

Hamiltonian path with backtracking Method

回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法,该算法可以用来求出问题的全部解,也可以在求出问题的一个解之后停止对问题的求解,即只求该问题是否有解。哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径。本文主要讲的就是用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题,并用具体的算法来实现它。

Backtracking is a depth-first strategy in accordance with the root node to start from the solution space tree search algorithm, which can be used to derive the full solution of the problem can also be obtained after a solution to stop the problem solving, that is, only whether the solvability of the problem. Hamiltonian path is to determine whether there is a map through all vertices once and only one path. This article stresses that the use of retrospective laws to solving an arbitrary figure whether there is a Hamiltonian path problem and the specific algorithm used to achieve it.