搜索算法初步

《搜索算法初步》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索算法初步江苏省常州市第一中学林厚从一、概述搜索是程序设计中的一项重要技术。许多编程问题不能用公式推导、数学计算或者模拟等方法来寻找答案，这样的问题往往有一个庞大的问题状态空间，并且给出了一些约束条件，要求寻找“解空间”中的一个或多个解。对于这样的问题，我们需要在“状态空间树”中摸索，以某种方式或顺序来试探不同的“状态结点”，使得尽可能快的寻找到“目标结点”，或者是从“初始结点”到“目标结点”的一个路径。这也正好利用了计算机运算速度快的优点。1、状态和状态空间状态一般是指客观现场信息的描述，通常用T表示，而用T0表示初始状态、Tn表示目标状态。状态空

2、间是指所有合理状态的集合，可以表示成∑={T}。例1、分油问题[问题描述]有3个油瓶，容量分别为10斤、7斤、3斤。开始时，10斤的瓶子中装满了油，其余为空，现在通过在这3个瓶子中倒来倒去，将10斤油分成2个5斤的。请编程输出一种倒油的方案。[概念解释]用一个三元组T（x10,x7,x3）来表示一种状态，其中x10，x7，x3分别表示10斤瓶、7斤瓶、3斤瓶中的油量。初始状态：T0=（10，0，0）目标状态：Tn=（5，5，0）约束条件：x10+x7+x3=10,0≤x10≤10，0≤x7≤7，0≤x3≤3状态空间：所有满足上述约束条件的状态{T（x1

3、0,x7,x3）}，如T（3,7,0），T（4,4,2）状态总数：35种。2、产生式系统产生式系统由一个综合数据库、一组产生式规则和一个控制系统三个基本要素组成。其中，综合数据库是产生式系统所用的主要数据结构（常见的如：集合、数组、树、队列等）。它主要用来表示问题的状态（初始状态、目标状态、中间状态）及状态之间的关系，它不是固定不变的，在求解过程中，它的内容会越来越多，关系也会越来越复杂。产生式规则是对数据库进行操作的一系列规则。规则的一般形式就是：IF条件THEN操作。它实现了状态之间的转移和关联，一般也称为状态变化规则。控制策略规定了操作的顺序，即

4、在什么条件下用什么规则进行操作，什么条件下停止运行，它规定了问题求解的搜索策略和路线。控制策略一般分为不可撤回方式和可撤回方式（试探法、回溯法）两类。对于分油问题，有6种倒油的可能性（6条产生式规则），分别如下：①10斤的瓶子往7斤的瓶子里倒：条件是x10>0andx7<7操作是x10:=x10+x7-7;x7:=7;x3不变②10斤的瓶子往3斤的瓶子里倒：条件是x10>0andx3<3操作是x10:=x10+x3-3;x3:=3;x7不变③7斤的瓶子往3斤的瓶子里倒：略④7斤的瓶子往10斤的瓶子里倒：略⑤3斤的瓶子往7斤的瓶子里倒：略⑥3斤的瓶子往1

5、0斤的瓶子里倒：略3、搜索中的一些问题搜索的问题一般有两种情况：一种是给出初始结点，要求寻找到符合约束条件的目标结点；另一种是给出初始结点和目标结点，要求找到从初始结点到目标结点的一条路径。对于解的要求也不尽相同，有的问题要求出问题的最优解，有的则要求出较优解，而有的问题要找出问题的全部解。搜索问题中的数据结构一般要求表达要合理，要有助于计算机的处理；信息要完整，要能反应出状态的本质和状态之间的关系；还要节省存储空间，尽可能地提高搜索的速度。比如分油问题本来用一个三元组（x10,x7,x3）即可，但是为了输出方便，我们增加一个d,用来表示该结点的父结点

6、（由谁扩展来的），即变成一个四元组（x10,x7,x3,d）。另外还用到队列来实现控制策略，当然，不能忘记状态变化过程中的重复性检查，因为大多数情况下，出现重复状态是毫无意义的，会造成死循环和空间的浪费。二、广度优先搜索算法广度优先搜索是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一扩展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则扩展第二层结点……，如此依次扩展，检查下去，直至发现目标结点为止。如果扩展完所有结点，都没有发现目标

7、结点，则问题无解。在搜索的过程中，广度优先搜索对于结点是沿着深度的断层扩展的。如果要扩展第n+1层结点，必须先全部扩展完第n层结点。对于同一层结点来说，他们对于问题的解的价值是相同的。所以，这种搜索方法一定能保证找到最短的解序列。也就是说，第一个找到的目标结点，一定是应用产生式规则最少的。因此，广度优先搜索算法比较适合求最少步骤或者最短解序列的题目。在具体求解过程中，广度优先一般用到“队列”这种重要的数据结构。例2、奇怪的电梯[问题描述]有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤n)上有一个数字Ki(

8、0≤Ki≤n)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字Ki。当然