1、第五章 状态空间搜索,第五章 状态空间搜索,问题归约法,博弈树搜索,Click to add title in here,1,2,3,第一节 状态空间搜索,S是状态集合，状态是某种事实的符号或数据，问题的初始状态是S的非空子集,1,一 问题的状态空间表示,起源于印度传说的梵塔问题是：有三根针和n个大小不同的盘片。开始盘片都是叠在第一根针上，从下到上按由大到小的顺序串叠。要求每次只移动最顶上的一个盘片到另一根针上，且大盘不得压在小盘上，直到把所有盘片移到第三根针上。以三圆盘为例，如图5-1所示。,例5-1 梵塔问题,图5-1 三盘片梵塔,用状态(i, j, k)表示最大盘片C在第i根针上，盘片B
2、在第j根针上，最小盘片A在第k根针上。如果同一根针有二片以上的盘片，则假设较大的在下面。如（1，1，2）表示C和B在第1根针上，且B在C的上面，而A在第2根针上。,用M（N，i, j）表示操作算子，即把盘片N从第I根针移到j根针上。如M（A，1，2）实现的操作是把盘片A从第1根针移到第2根针上，即使状态（1，1，1）变成状态（1，1，2）。而不允许接着进行M（B，1，2）操作，使状态（1，1，2）变为状态（1，2，2），因为这违反了小片必须在大片上的规则。,三盘片梵塔状态空间图,例5-2 传教士和野人问题,设有三个传教士和三个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在
3、任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？,问 题,问题解决,二 状态空间的穷搜索法,三 启发式搜索法,第二节 问题归约法,问题归约法是不同于状态空间法的另一种问题描述和求解的方法。归约法把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解：只有当这些子问题全部解决时，问题才算解决，问题 的解答由子问题的解答联合构成。,思想,一 问题归约描述,用一个三元组（S0,O,P）来描述,S0初始问题，即要求解的问题。P是本原问题集，其中的每一个问题是不证明的，自然成立的，如公理、已知事实等，或已证明过的。O是操作算了集
4、，通过一个操作算子把一个问题化成若干个子问题。,二 与或图表示,用与或图可以方便地把问题归约为子问题替换集合。例如，假设问题A既可通过问题C1与C2，也可通过问题C3,C4和C5，或者由单独求解问题C6来解决，如图5-10所示。图中节点表示要求解的问题或子问题。,三 AO*算法,AO*算法要能处理与图，它应找出一条路径，即从该图的开始结点出发到达代表解状态的一组结点。注意，可能需要到达多个解状态，因为一与弧的每条臂要引至它自身的结点。 在扩展搜索一与或图时，每步需做三件事；（1）遍历图，从初始结点开始，顺沿当前最短路径，积累在此路径上但未扩展的结点集。（2）从这些未扩展结点中选择一个并扩展之。
5、将其后继结点加入图中，计算每一后继结点的f值（只需计算h,不管g）。图5-14 AO*算法的运行。（3）改变最新扩展结点的f估值，以反映由其后继结点提供的新信息。将这种改变往后回传至整个图。在往后回攀图时，每到一结点就判断其后继路径中哪一条最有希望，并将它标 记为目前可能解图的一部分。这样可能引起目前最短路 的变动。,AO*算法描述,（1）设开始状态结点为INIT，G=INIT，计算h（INIT）。（2）在INIT标为SOLVED（成功）之前，或INIT的h值变得大于FUTILITY（失败）之前，重复下述过程： a跟踪始于INIT的已带标记的弧，挑选出现在此路径上但未扩展的结 点之一扩展，称新
6、挑选的结点NODE。 b生成NODE的后继结点，则对不是NODE祖先的每一后继结点（称 SUCCESSOR）应做下述事项： （i）把SUCCESSOR加到图G中。 （ii）如果SUCCESSOR是一目标结点，那么将其标记为SOLVED，并 赋0作为SUCCES-SOR的h值。 （iii）若SUCCESSOR不是目标结点，则计算它的h值。 c将最新发现的信息向图的上部回传，具体做法是：设S为一结点 集，它含有已作了SOLVED标记的结点，或包含其h值已经改变因而 需要回传至其父结点的那些结点。置S的初值为NODE。重复下述过 程，直至S为零。,（i）从S中挑选一个结点，该结点在G中的子孙均不在S
7、中出现（换句话说，保证对于每一正在处理的结点，是在处理其任一祖先之前来处理该结点的），称此结点为CURRENT并把它从S中去掉。（ii）计算始于CURRENT的每条弧的耗费。每条弧的耗费等于在该弧末端每一结点的h值之知和加上该弧身的耗费。从刚刚计算过的始于CURRENT的所有弧费中选出极小耗费作为CURRENT的新h值。（iii）把在上一步计算出来的带极小耗费的弧标记出始于CURRENT的最佳路径。（iv）如果穿过新的带标记弧与CURRENT连接的所有结点均标为SOLVEO，则把CURRENT标为SOLVED。图5-16 逆向传播（v）若CURRENT已标为SOLVED，或CURRENT的耗费
8、刚才已经改变，那么应把其新状态往回传至图。因此，要把CURRENT的所有祖先加到S 中。,第三节 博弈树搜索,这里讲的博弈是二人博弈,即由人对垒，轮流依次走步，每一方都知道对方已经走过的棋步和以后可能走的棋步，双方最终将有胜负之分或者为和局，这类博弈如一字棋、象棋、围棋等。,具体例子,用数字序列加上一个说明表示一个状态，其中数字表示不同堆中钱币的个数，说明表示下一步由谁来分，如（7，MAX）表示只有一个由七个钱币组成的堆。,一 极大极小过程,5-6表示了向前看两步,共四层的博弈树，用表示，MAX，用表示MIN，端结点上的数字表示它对应的做人函数的值。在MIN处用圆弧连接，0用以表示其子结点取估
9、值最小的格局。,下面假定由MAX选择走一步棋，MAX如何来选择一步好棋呢？极大极小过程就是一种方法，这种方法的思想是，对格局给 出一个估价函数，因此每具体局由做人函数数可得一值，值越大对的格局作为MAX要走的一步。,用一字棋来具体说明一下极大极小过程，不失一般，设只进行两层，即每方只走一步（实际上，多看一步增加大量的计算和存储）。 评价函数e（p）规定如下：1若格局P对任何一方都不是获胜的，则 e(p)=（所有空格都放上MAX的棋子之后，MAX的三个棋子所组成的行、列及对角线的总数）（所有空格都放上MIN的棋子后，MIN三个棋子所组成的行、列及对角线的总数）2若p是MAX获胜，则3若p是MIN
10、获胜，则,二 过程,前面讨论的极大极小过程先生成一棵博弈搜索树，然后再进行估值的倒推计算，将两个过程完全分离，这种分离是低效率的。重要原因是是否可以在博弈树生成的同时完成端结点的估值及倒推计算，以减少搜索的次数，这就是下面要讨论的过程。图5-20表示了值小于等于父结点的a值的情况，实际不当某个MIN结点的值不大于它先辈的MAX结点的值，则MAX结点就可以终止向下搜索 。同样当某个接点的 值大于等于它的前辈MIN接点的 值时，该MAX接点就可以终止向下搜索。,一般讲我们可把中止搜索，即剪技的规则表述如下,1.若任何MIN结点的值小于或等于任何它的先辈MAX结点的a值，则可中止该MIN结点以下的搜索，然后这个MIN结点的最终倒推值即为它已得到的值。该值与真正的极大极小的热能索结果的倒推值可能不相同，但是对开始结点而言，倒推值是相同的，使用它选择的步也是相同的。2若任何MAX结点的a值大于或等于它的MIN先辈结点的值，则可以中止该MAX结点以下的搜索，然后这个MAX结点处的倒推即为它已得到的a值。,
