【人工智能_人工智能原理与应用】第五章状态空间搜索

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