3.5.1 试探算法基础

使用试探算法解题的基本步骤如下所示。

（1）针对所给问题，定义问题的解空间。

（2）确定易于搜索的解空间结构。

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

为了求得问题的正确解，试探算法会先委婉地试探某种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

假设存在一个可以用试探法求解的问题P，该问题表达为：对于已知的由n元组（y1，y2，…，yn）组成的一个状态空间E={（y1，y2，…，yn）∣yi∈Si，i=1，2，…，n}，给定关于n元组中一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中，Si是分量yi的定义域，且|Si|有限，i=1，2，…，n。E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最简单方法是使用枚举法，即对E中的所有n元组逐一检测是否满足D的全部约束条件，如果满足，则为问题P的一个解。但是这种方法的计算量非常大。

对于现实中的许多问题，所给定的约束集D具有完备性，即i元组（y1，y2，…，yi）满足D中仅涉及y1，y2，…，yj的所有约束，这意味着j（j＜i）元组（y1，y2，…，yj）一定也满足D中仅涉及y1，y2，…，yj的所有约束，i=1，2，…，n。换句话说，只要存在0≤j≤n−1，使得（y1，y2，…，yj）违反D中仅涉及y1，y2，…，yj的约束之一，则以（y1，y2，…，yj）为前缀的任何n元组（y1，y2，…，yj，yj+1，…，yn）一定也违反D中仅涉及y1，y2，…，yi的一个约束，n≥i＞j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（y1，y2，…，yj）违反D中仅涉及y1，y2，…，yj的一个约束，就可以肯定，以（y1，y2，…，yj）为前缀的任何n元组（y1，y2，…，yj，yj+1，…，yn）都不会是问题P的解，因而不必去搜索和检测它们。试探算法就是针对这类问题而推出的，比枚举算法的效率更高。