? 状态空间的一些基本概念
1) 很多问题的求解过程都可以看作是一个搜索过程。问题及其求解过
程可以用状态空间表示法来表示。
2) 状态空间用“状态”和“算符”来表示问题。
状态
状态用以描述问题在求解过程中不同时刻的状态，一般用一个向量表示：
SK=(Sk0,Sk1,…)
算符
使问题从一个状态转变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。 状态空间
由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。
3) 采用状态空间求解问题，可以用下面的一个三元组表示：
(S,F,G)
其中S是问题初始状态的集合；F是算符的集合；G是目标状态的集合。
采用状态空间表示方法，首先要把问题的一切状态都表示出来，其次要定义一组算符。
问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解
就是从初始状态到目标状态所采用算符的序列。使用算符最少的解称为最优解。
对任何一个状态，可使用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取决于搜索策略。 ? OPEN表和CLOSE表
OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。
CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所有可适用的算符对该节点进行操作，生成一组子节点
? 搜索的一般过程
1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G； 2. 检查OPEN表是否为空，若为空则问题无解，退出；
3. 把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n； 4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出； 5. 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点
记做集合M，并把这些子节点作为节点n的子节点加入G中； 6. 针对M中子节点的不同情况，分别进行如下处理：
1) 对于那些未曾在G中出现过的M成员设置一个指向父节点（即
节点n）的指针，并把它们放入OPEN表；（不在OPEN表） 2) 对于那些先前已经在G中出现过的M成员，确定是否需要修改
它指向父节点的指针；（在OPEN表中）
3) 对于那些先前已在G中出现并且已经扩展了的M成员，确定是
否需要修改其后继节点指向父节点的指针；（在CLOSE表中）
7. 按某种搜索策略对OPEN表中的节点进行排序； 8. 转第2步。 ? 一些说明
? 一个节点经一个算符操作后一般只生成一个子节点。但适用于一个
节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。
? 一个新生成的节点，它可能是第一次被生成的节点，也可能是先前
已作为其它节点的子节点被生成过，当前又作为另一个节点的子节点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。
? 在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。
该解是由从初始节点到该目标节点路径上的算符构成。
? 如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展
的节点，则搜索失败。
? 通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。
由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。根据搜索树可给出问题的解。 ? ? 盲目搜索
? 广度优先搜索
广度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索； ? 基本思想
从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。
? OPEN表中节点总是按进入的先后顺序排列，先进入的节点排在
前面，后进入的排在后面。
? 广度优先搜索过程
1) 把初始节点S0放入OPEN表。
2) 如果OPEN表为空，则问题无解，退出。
3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。 4) 考察节点n是否为目标节点。若是，则求得了问题的解，退
出。
5) 若节点n不可扩展，则转第2步。
6) 扩展节点n，将其子节点放入OPEN表的尾部，并为每一个
子节点都配置指向父节点的指针，然后转第2步。
? 广度优先搜索的本质是，以初始节点为根节点，在状态空间图中
按照广度优先的原则，生成一棵搜索树
? 优点：总可以得到解，且是路径最短的解。缺点：盲目、效率低。 ? 重排九宫的广度优先搜索
2S02 8 31 47 6 541 2 8 3 1 47 6 53 782 31 8 47 6 59 2 8 31 4 7 6 5111252 8 31 6 47 5136 8 32 1 47 6 5148 32 1 47 6 5228 3 2 1 4 7 6 5238 1 32 47 6 524 2 8 3 7 1 4 6 51510 2 31 8 47 6 5161 2 3 8 47 6 525261 2 38 47 6 52 32 8 2 8 3 1 8 4 1 4 3 1 4 5 7 6 5 7 6 57 61718 2 3 41 8 7 6 52 81 4 37 6 51192 8 31 4 57 6 2 8 3 2 8 3 1 6 4 1 6 47 67 52021 2 8 3 2 8 36 41 6 1 7 5 7 5 4 2 8 37 1 4 6 52 8 37 4 6 1 5 2 8 3 7 1 46 5Sg
? 深度优先搜索----考有界深度优先搜索的可能性很大
深度优先搜索按照“后扩展出的节点先被考察”的原则进行搜索； ? 深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将
节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。 ? 深度优先搜索过程
1) 把初始节点S0放入OPEN表。
2) 如果OPEN表为空，则问题无解，退出。
3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。 4) 考察节点n是否为目标节点。若是，则求得了问题的解，退
出。
5) 若节点n不可扩展，则转第2步。
6) 扩展节点n，将其子节点放入OPEN表的首部，并为每一个
子节点都配置指向父节点的指针，然后转第2步。 ? 深度优先搜索的本质：以初始节点为根节点，在状态空间图
中按照深度优先的原则，生成一棵搜索树。 ? 重排九宫的深度优先搜索
? 有界深度优先搜索： 2 8 31 67 5 42 8 3 1 47 6 5S02 8 31 47 6 5122 31 8 47 6 5 2 8 31 4 7 6 5 2 8 3 1 6 47 62 8 31 6 47 53 2 8 3 1 6 47 54 2 8 31 6 7 5 452 8 1 6 3 7 5 42 81 6 37 5 4...