您的当前位置是：第三章 确定性推理>>学习内容>>本章小结

本章所讨论了搜索与推理问题，搜索包括盲目搜索、启发式搜索和博弈树搜索。在应用盲目搜索进行求解的过程中，一般是“盲目”地穷举，即不运用特别信息。盲目搜索包括宽度优先搜索、深度优先搜索和等代价搜索等。其中，有界深度优先搜索在某种意义上讲，具有一定的启发性。从搜索效率看，一般来说，有界深度优先搜索较好，宽度优先搜索次之，深度优先搜索较差。不过，如果有解，宽度优先搜索搜索一定能够找到解。
启发式搜索主要讨论有序搜索（最好优先搜索）和最优搜索A*算法。与盲目搜索不同的是，启发式搜索运用启发信息，引用某些准则或经验来重排OPEN表中节点的顺序，使搜索沿着某个被认为最有希望的前沿区段扩展。正确选择估计函数，对于寻找最小代价路径或解树，至关重要。启发式搜索要比盲目搜索有效得多，因而应用较为普遍。
在二人零和、全信息、非偶然博弈中，博弈过程可以表示成与/或树的形式，在与/或树中与节点与或节点交替出现。博弈树搜索的可以为博弈树的根节点寻找最优方案。极大极小搜索过程是博弈树的最简单的搜索方法，这种方法可以看作是在有限深度内进行穷举，所以方法的效率低。α－β剪枝技术对极大极小过程的改进方法，该方法是一边生成博弈树，一边计算倒推值。对不影响倒退值计算的分枝提前减去，从而提高了搜索效率。
在求解问题时，可把问题表示为一个有待证明的问题或定理，然后用消解原理和消解反演过程来证明。在证明时，首先假设该定理的否定是正确的，接着证明由公理和假设的定理之否定所组成的集合是不成立的，即导致矛盾的结论－该定理的否定是不成立的，因而证明了该定理必定是成立的。这种通过证明定理的否定不成立的方法叫做反演证明。