周 双，周云才 （长江大学计算机科学学院，湖北 荆州434023）

回溯法是基本的算法策略之一，它是通过对解不断试探测试来进行求解的方法。在问题规模不是太大的前提下，回溯法可以解决为数众多的组合数问题［1］。

1 回溯法描述

若问题Q可用回溯法求解，它一般能如下表述：对于已知由n元组 （x1，x2，…，xn）组成的一个状态空间E＝ ｛（x1，x2，…，xn）｜xi∈si，i＝1，2，…，n｝，给定关于n元组中的一个分量的一个约束集D，要求E中符合D的全部约束条件的所有n元组0。其中si是分量xi的定义域，且｜si｜有限，i＝1，2，…，n。称E中符合D的全部约束条件的任何一个n元组为问题Q的一个解。

解决问题Q可用穷举法，即对状态空间里的所有候选解进行带入验证，若满足约束则该候选解即是一个正解。这种方法需要对所有可能解进行探测，工作量非常大。

很多情况下约束集D具有完备性，即i元组 （x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束，意味着j（j＜i）元组 （x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束 （i＝1，2，…，n）［2］。可把n元组状态空间看成一棵高为n的带权有序树，从根结点出发深度搜索，一旦某结点违背约束条件则包含该结点的路径绝不会是正解，此时可剪掉该结点不再继续深入搜索。回溯法就是这样在深度搜索过程中利用约束条件进行枝剪来避免无效搜索的，显然比穷举法的效率要高很多。

2 C语言编程模式

一个状态空间如果其导出空间是一个树型显式空间，则称为树型状态空间。根据被搜索的状态空间是否为树型状态空间，回溯算法可分为2类：树型状态空间的回溯搜索称为基于树的回溯，其它状态空间的回溯搜索称为基于图的回溯［1］。……