概论用回溯法求解通俗哈密尔顿回路题目.doc

[概论]用回溯法求解通俗哈密尔顿回路题目
目 录
引言 ......................................... - 1 - 1 需求分析 ................................... - 2 -
............................ - 2 -
............................ - 2 -
............................ - 2 - 2 概要设计 .................................. - 4 -
.......................... - 4 -
............................ - 4 -
............................. - 12 -
......................... - 12 -
............................. - 13 - 3 详细设计 .................................. - 14 -
........................... - 14 -
........................... - 15 -
........................... - 15 -
............................. - 19 - 4 调试分析 .................................. - 20 -
................. - 20 -
................. - 22 - 5 总结 ...................................... - 23 - 参考文献 .................................... - 25 - 附录 ........................................ - 26 -
摘 要
回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法～该算法既带有系统性又带有跳跃性～它在包含问题的所有解的解空间树中～按照深度优先的策略～从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时～总是先判定该节点是否肯定不包含问题的解～如果肯定不包含～则跳过对以该节点为跟的子树的系统搜索～逐层向其祖先节点回溯。否则～进入该子树～继续按深度优先的策略进行探索。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法。回溯法可以用来求出问题的全部解～也可以在求出问题的一个解之后停止对问题的求解～即只求该问题是否有解。它适用于解一些组合数较大的问题。哈密尔顿回路路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径。本文主要讲的就是用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题～并用具体的算法来实现它。
关键词:回溯法 哈密尔顿回路 空间树
引言
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树[1]。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束 [2]。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
1 需求分析

在求解一些问题(如走迷宫、地图着色等问题)时，题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能的决策方案;由于没有固定、明确的数学解析方法，往往要采用搜索的做法，即从某一个初始状态出发，不断地向前(即下一个状态)搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点(如在缺乏全局及足够的前瞻信息的情况下进行搜索等)[