人工智能产生式系统的搜索策略.ppt

第三章 产生式系统的搜索策略 3 1状态空间搜索概述3 2回溯策略3 3图搜索策略3 4盲目的图搜索过程3 5启发式图搜索过程 有两种基本方式 盲目搜索的方法 启发式搜索 求任一解路 backtracking HillClimbing Breadth first Depth first BeamSearch Best first 求最佳解路 BritishMuseum BranchandBound DynamicProgramming A 求与或图 AO Minimax Alpha betaPruning HeuristicPruning 图3 1搜索空间 在人工智能中 问题求解的基本方法有搜索法 归约法 归结法 推理法 约束满足法及规划等 而状态空间搜索则是问题求解的主要方法之一 3 1状态空间搜索概述 3 1 1图的概念图是节点及连接它们的弧的集合 含两个集合 节点和弧 由方向性的弧连接的图是有向图 节点深度的表示 dn 1 dn 1路径 N个有序的节点序列中 若每对节点都表示一条弧 则称该序列为图中长度为N的一条路径 路径耗散值 令C ni nj 为节点ni到节点nj这段路径 或弧线 的耗散值 一条路径的耗散值等于连接这条路径各个节点间所有弧线耗散值的总和 路径耗散值可按如下的递归公式计算 C ni t C ni nj C nj t 节点的扩展 后裔节点的操作符 规则 作用到节点 对应于某一状态描述 上 生成出其所有的后继节点 新状态 并给出了解弧线的耗散值 相当于使用规则的代价 这个过程叫做扩展一个节点 3 1 2问题状态空间的图描述 问题的状态空间描述中 图是最直观的 属于显式描述 图的节点表示问题的状态 图的弧表示状态之间的关系 也就是求解问题的步骤 初始状态对应于实际问题的已知信息 是图中的根节点 问题的状态空间图描述中 寻找从一种状态转换为另一种状态的某个操作算子序列就等价于在一个图中寻找从一种状态到另一种状态的一条路径 3 1 3将问题求解定义为状态空间搜索 搜索成为一种求解问题的一般机制 它构成了AI系统的一种框架 其状态空间法构成了AI方法的基础 其结构与问题的求解结构相对应 状态空间法将一个问题形式地定义为用一个三元组中的操作将某个给定的状态转换为所要求的状态 状态空间法将一个待定问题的求解过程定义为若干算子与搜索的有机结合体 一个算子则定义了问题空间的一个操作 搜索是考察一个问题的一般技术 其目的在于要找出从当前状态到某个目标状态的一条路径或某些目标状态的一组路径 为提供对问题的形式描述 需要定义和规定 定义一状态空间 它包含一个问题相关对象的各种可能的排列 对空间的定义不必枚举其状态空间中的所有状态 规定一个或多个属于该空间的初始状态 该状态用以描述问题求解过程开始时的状态 规定一个或多个属于该空间的目标状态 该状态用以描述问题的解 规定一组规则 它们描述可使用的操作或算子 将非形式的问题描述转换成状态空间形式描述后 便可利用状态空间的搜索方法 应用这一组规则和相应的控制策略 在问题状态的空间内进行搜索 直到找出从一开始状态到一目标状态的某条路径或某些目标状态的一组路径 3 1 4搜索的基本概念 在状态空间中 问题的求解就是搜索 即搜索某个状态空间以求得由操作算子序列组成的一个解答的过程 它对应于将一个隐式图的足够大的一部分变为显式并包含目的节点的过程 这种搜索过程是状态空间问题求解的主要基础 搜索的基本问题是 1 有解 搜索过程是否一定能找到一个解 2 终止 搜索过程是否能终止运行或是否会陷入一个死循环 3 最佳解 当搜索过程找到解时 找到的是否是最佳解 4 代价 搜索过程的时间与空间复杂性如何 搜索过程的要点是 从初始或目的状态出发 并将它作为当前状态 扫描操作算子集合 将适用于当前状态的一些操作算子作用在其上而得到新的状态 并建立与父母节点的连接指针 检查所生成的新状态是否满足结束状态 如果满足 则得解 并可沿着有关指针从结束状态反向到达开始状态 给出一解答路径 否则 将这新状态作为当前状态 返回第 2 步再进行搜索 3 1 5搜索的策略 通常搜索策略的任务是确定如何选择选取操作算子的公式 有两种基本方式 盲目搜索和启发式搜索 无信息搜索和有信息搜索 所谓盲目搜索是指在不具有对特定问题的任何有关信息的条件下 按固定的步骤 依次或随机调用操作算子 进行搜索 它能很快地运用一个操作算子 而启发式搜索则是考虑特定问题领域可应用的知识 动态地确定调用操作算子的步骤 优先选取较合适的操作算子 尽量减少不必要的搜索 以求尽快地到达结束状态 提高搜索效率 盲目搜索中 由于没有可参考的信息 因此只要能匹配的操作算子都须运用 这会搜索出更多的状态 生成较大的状态空间显示图启发式搜索中 如果具有较多的甚至完整的启发信息 那么只须运用少量的操作算子 生成较小的状态空间显示图 便可将搜索引向一个解答 但是每使用一个操作算子要做更多的计算与判断 启发式搜索一般要优于盲目搜索 但不可过于追求更多的甚至完整的启发信息 应综合考虑 尽量使搜索系统的总开销较小 下图可说明这个问题 图3 2 搜索系统的开销 3 2回溯策略 回溯策略是一种系统地尝试状态空间中各种不同路径的技术 带回溯策略的搜索是从初始状态出发 不停地 试探地寻找路径直到它到达目的或 不可解节点 死胡同 如它遇到不可解节点就回溯到路径中最近的父节点上 查看该节点是否还有其他的子节点未被扩展 如有 则沿这些子节点继续搜索 如果找到目标 就成功退出搜索 返回解题路径 可以看出 这种求解过程呈现出递归过程的性质 求解过程在每个节点上的检查遵循着递归方式 递归过程示例 阶乘函数的递归 intfactorial intn if n 1 return1 else returnn factorial n 1 只要初始值大于零 这个函数就能够终止 停止的位置称为基线条件 basecase 基线条件是递归程序的最底层位置 在此位置时没有必要再进行操作 可以直接返回一个结果 所有递归程序都必须至少拥有一个基线条件 而且必须确保它们最终会达到某个基线条件 否则 程序将永远运行下去 直到程序缺少内存或者栈空间 一些符号的含义 变量 DATA 当前状态 RULES 规则集合序列表 R 当前调用规则 RDATA 新生成的状态 PATH 当前解路径表 常量 NIL 空表 FAIL 回溯点标记 LOOP 循环标号 谓词 TERM DATA DEADEND DATA NULL RULES 函数 APPRULES求可应用的规则表 FIRST从表中取表头的一个元素 TAIL除去表头的一个元素后得到新表 GEN调用规则生成新状态 CONS在表头插入新元素 构造新表 递归过程BACKTRACK DATA ifTERM DATA returnNIL 当DATA满足终止条件时 TERM DATA 为真即找到目标 此时 过程返回空表NIL ifDEADEND DATA renturnFAIL当已知DATA不在解的路径上时 DEADEND DATA 为真 即该状态不合法 必须回溯RULES APPRULES DATA 可应用的规则表 LOOP ifNULL RULES returnFAIL 如果已经没有了可应用的规则 则回答FAIL 必须回溯 R FIRST RULES 选出头条 最好的 可应用规则 RULES TAIL RULES 把刚才选出的规则从规则表中删除 减少可应用规则表的长度 RDATA GEN R DATA 把R作用于当前状态 PATH BACKTRACK RDATA 对新状态递归调用本过程ifPATH FAIL goLOOP 如果递归失败 则用另一条规则returnCONS R PATH 否则把R加在规则表中 向上传递成功的规则表 过程返回解路径规则表 或局部解路径子表 举例 综合数据库 DATA L 表 L元素用 ij 表示 i j的值域为 1 2 3 4 即L表的元素表示棋子所在的行和列 图3 3中状态分别记为 12243143 13213442 1121 1122 112331 四皇后问题 在一个4 4的国际象棋棋盘上 一次一个地摆布四枚皇后棋子 摆好后要满足每行 每列和对角线上只允许出现一枚棋子 即棋子间不能相互俘获 图3 3 棋盘的几种状态 共16个规则 每条规则Rij表示满足前提条件下 在ij处放一个棋子 当规则序列以R11 R12 R13 R14 R21 R44这种固定的排序方式调用BACKTRACK时 四皇后问题的搜索示意图如3 4所示 共回溯22次 主过程结束时返回规则表 R12 R24 R31 R43 规则集 图3 4 四皇后问题的固定排序搜索树 作业1 当规则序列以R11 R21 R31 R41 R12 R22 R32 R44这种固定排序方式调用BACKTRACK函数时 画出四皇后问题的搜索树 并标出所有回溯的先后顺序 如果要利用问题有关信息对规则进行动态排序 则可定义一个对角线函数Maxdiag i j 该函数可计算棋盘上ij单元的最长的对角线长度 通过比较不同单元的Maxdiag i j 函数值来决定Rij的排序 如Maxdiag i k Maxdiag i j 则为 Rik Rij 即对角线短的单元 相应的规则排在前头 若相同 则维持原顺序 按此知识排列的序列为R12 R13 R11 R14 R21 R24 R22 R23 R31 R34 R32 R33 R42 R43 R41 R44 3 3 4 4 这样搜索示意图如图所示 只回溯2次找到目标 图3 5 四皇后问题的动态排序搜索树 对于可能出现重复状态且搜索深度无限的问题 必须设置深度范围限制及防止出现重复状态引起的死循环这两个回溯点 改进的算法如下BACKTRACK1 DATALIST 1 DATAFIRST DATALIST 2 ifMEMBER DATA TAIL DATALIST returnFAIL回老路退回 3 ifTERM DATA returnNIL到达目标 成功返回 4 ifDEADEND DATA returnFAIL到达不合理状态 退回 5 ifLENGTH DATALIST BOUND returnFAIL已到深度限制 退回 6 RULESAPPRULES DATA 得出可应用的规则集 7 LOOP ifNULL RULES returnFAIL进入死胡同 退回 8 RFIRST RULES 取出第一条可应用规则 9 RULESTAIL RULES 10 RDATAGEN R DATA 运用规则 生成新状态 11 RDATALISTCONS RDATA DATALIST 12 PATHBACKTRACK1 RDATALIST 递归 13 ifPATH FAIL goLOOP 14 returnCONS R PATH 在递归过程中 如当前状态S未达到目的的要求 就对它的第一个子状态Schild1递归调用回溯过程 如果在以Schild1为根的子图中未找到目的 就对它的兄弟子状态Schild2递归调用回溯过程 像这样重复进行直到某个子状态的后裔是目的状态或者所有的子状态都搜索完为止 如S的子状态中没有一个能达到目的 便回溯到S的父状态 算法开始对S的兄弟状态进行搜索 算法以这种方式搜索直到找到目的状态或遍历了所有的状态空间为止 图3 6一个状态空间中应用回溯搜索的示意图 3 3图搜索策略 一般的图搜索算法 1 G G0 G0 s Open s G表示图 s为初始节点 设置Open表 最初只含初始节点 放待扩展的节点 2 Closed 设置Closed表 起始设置为空表 放已扩展完的节点 3 LOOP IFOpen THENEXIT FAIL 4 n FIRST Open REMOVE n Open ADD n Closed 称n为当前节点 在产生式系统中 如果控制系统保留了所有的规则应用后生成并连接起来的状态记录图 则称控制系统使用了图搜索策略 它的实质是实现从一个隐含图中 生成出一部分确实含有一个目标节点的显式表示子图的搜索过程 5 IFGOAL n THENEXIT SUCCESS 由n返回到s的路径上的指针 可给出解路径 6 EXPAND n mi G ADD mi G 对于子节点集 mi 中不包含n的先辈节点 7 标记和修改指针 对于出现多路径的情况 根据耗散值选择最好的解路 此时 mi mj mk ml lADD mj Open 并标记mj连接到n的指针 mj表示Open和Closed中未出现过的子节点 l计算是否要修改mk ml到n的指针 mk表示已出现在Open中的子节点 ml表示已出现在Closed中的子节点 l计算是否要修改ml到其后继节点的指针 8 对Open中的节点按某种原则重新排序 9 GOLOOP 图3 7 扩展节点6和节点1得到的搜索图 实心圆点表示在Closed中 已扩展过的节点 空心圆点表示在Open中 待扩展点 先设下一步轮到要扩展节点6 并设生成两个子节点 其中有一个4 mk 已在Open中 那么原先路径 s 3 2 4 耗散值为5 设每段为单位耗散 新路径 s 6 4 耗散值为4 所以节点4的解路指针应修正 2 6 如图 a 所示 接着设下一循环要扩展节点1 若节点1只生成一个子节点2 ml 比较耗散值 显然要修改节点2的指针 3 1 由此又会引起节点4指针的修改 如图 b 所示 3 4盲目的图搜索过程 3 4 1宽度优先搜索宽度优先搜索法是按图3 所示的次序搜索状态的 即 由S0生成状态1 2 然后扩展状态1 生成状态3 4 5 接着扩展状态2 生成状态6 7 8 该层扩展完后 再进入下一层 对状态3进行扩展 如此一层一层地扩展下去 直到搜索到目的状态 如果目的状态存在 图3 8宽度优先搜索法中状态的搜索次序 open表包含了已经生成出来但其子状态未被搜索的状态 open表中状态的排列次序就是搜索的次序 closed表记录了已被生成扩展过的状态 宽度优先搜索过程 Procedurebreadth first searchBeginOpen start closed 初始化Whileopen doBegin从Open表中删除第一个状态 称之为n 将n放入closed表中 ifn 目的状态thenreturn success else生成n的所有子状态 从n的子状态中删除已在Open或closed表中出现的状态 避免循环搜索 将n的其余子状态 按生成的次序加入到Open表的后端 End End 如图3 9所示 通过搬动积木块 希望从初始状态到达一个目的状态 即三块积木堆叠在一起 积木A在顶部 B在中间 C在底部 该问题的操作算子为MOVE X Y 即把积木X搬到Y 积木或桌面 上面 如 搬动积木A到桌面上 表示为MOVE A Table 但该算子有三个先决条件 1 被搬动的积木顶部必须为空 2 如Y是积木 不是桌面 则积木Y的顶部也必须为空 3 同一状态下 应用操作算子的次数不得多于一次 可从open表和closed表加以检查 图3 9 积木问题 图3 10 积木问题宽度优先搜索树 各节点是以产生和扩展的先后次序编下标的 当搜索到S10目的状态时 过程便结束 此时 closed表包含S0至S5 而open表包含S6至S10 由于宽度优先搜索总是在生成扩展完N层的节点之后才转向N 1层的 所以它总能找到最短的解题路径 如果有解 3 4 2深度优先搜索 搜索从初始状态S0出发 沿一个方向一直扩展下去 如状态1 2 3 直到达到一定的深度 这里假设3层 如未找到目的状态或无法再扩展下去 便回溯到另一条路径 状态4 继续搜索 若还没有找到目的状态或无法再扩展时 再回溯到另一条路径 状态5 6 搜索 图3 11 深度优先搜索法中状态的搜索次序 Proceduredepth first searchBeginOpen start closed d 深度限制值 初始化WhileOpen doBegin从Open表中删除第一个状态 称之为n 将n放入closed表中 ifn 目的状态thenreturn success elseifn的深度 dthencontinue 回溯else生成n的所有子状态 从n的子状态中删除已在Open或closed表中出现的状态 避免循环搜索 将n的其余子状态 按生成的次序加入到Open表的前端 End End 深度优先搜索过程 例 订票问题 一名顾客希望订一张美国航空公司从纽约到洛杉矶的飞机票 如果没有从纽约到洛杉矶的直达航班 航班表如下所示 但他坚持要乘座美国航空公司的航班 问如何为其订票 纽约 芝加哥1000英里 芝加哥 丹佛1000英里 纽约 多伦多800英里 纽约 丹佛1900英里 多伦多 卡尔加里1500英里 多伦多 洛杉矶1800英里 多伦多 芝加哥500英里 休斯顿 洛杉矶1500英里 丹佛 洛杉矶1000英里 丹佛 休斯顿1500英里 丹佛 欧本纳1000英里 图3 12 订票问题深度优先的搜索树 解为纽约 芝加哥 丹佛 洛杉矶3000英里 可见非最理想的解 最理想的解是纽约 多伦多 洛杉矶2600英里 3 5启发式图搜索过程 利用所处理问题的启发信息引导搜索 被成为启发式搜索 它可以达到减少搜索范围 降低问题复杂度的目的 3 5 1启发式图搜索算法A基本思想 如果即考虑从起始节点到节点n的路径费用 又考虑从节点n到达目标节点的费用 即定义一个评价函数f 对当前的搜索状态进行评估 找出一个最有希望的节点来扩展 其形式为 f n g n h n n为被评价的节点 用此函数来排列OPEN表节点顺序的图搜索算法称为A算法 几个函数说明 g n 表示从s到n的最短路径的耗散值 h n 表示从n到目标节点g的最短路径的耗散值f n g n h n 表示从S出发 通过节点n到目标节点g的最短路径的耗散值 而f n g n 和h n 则分别表示了对f n g n h n 3个函数值的估计值 是一种预测 A算法就是利用这种预测 来达到有效搜索的目的 g n 可根据搜索历史情况对g n 作出估计 显然有g n g n h n 则依赖于启发信息 通常称为启发函数 是要对未来扩展的方向作出估计 算法A 1 OPEN s f s g s h s 2 LOOP IFOPEN THENEXIT FAIL 3 n FIRST OPEN 4 IFGOAL n THENEXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSED 6 EXPAND n mi 把mi作为n的后继节点添入G 并计算f n mi g n mi h mi ADD mj OPEN IFf n mk f mk THENf mk f n mk IFf n ml f ml THENf ml f n ml ADD ml OPEN 7 OPEN中的节点按f值从小到大排序 8 GOLOOP 算法的说明 A算法由一般的图搜索算法改变而成 算法第7步每次按照f n 值的大小对OPEN表中的元素进行排序 f n 值小的节点排在前面 而f n 值大的节点则放在OPEN表的后面 这样每次扩展节点时 都是选择当前f n 值最小的节点来优先扩展 A算法是按f n 递增的顺序来排列OPEN表中节点的 因而优先扩展f n 值小的节点 体现了好的优先搜索的思想 所以算法A是一个好的优先搜索策略 扩展n后新生成的子节点m1 mj m2 mk m3 ml 分别其计算评价函数值 f m1 g m1 h m1 f n m2 g n m2 h m2 f n m3 g n m3 h m3 按第6步比较不同路径的耗散值并进行相应的指针修正 搜索示意图 好的优先搜索策略在八数码问题中的应用过程 设评价函数f n 形式如下 f n d n W n 其中d n 代表节点的深度 取g n d n 表示讨论单位耗散的情况 取h n W n 表示以 不在位 的将牌个数作为启发函数的度量 这时f n 可估计出通向目标节点的希望程度 图3 13表示使用这种评价函数时的搜索树 图中括弧中的数表示该节点的评价函数值 根据目标节点L返回到s的指针 可得解路径 s 4 B 5 E 5 I 5 K 5 L 5 OPEN和CLOSED表的元素排列如下 OPEN表 初始化 s 4 第一循环结束 B 4 A 6 C 6 第二循环结束 D 5 E 5 A 6 C 6 F 6 第三循环结束 E 5 A 6 C 6 F 6 G 6 H 7 第四循环结束 I 5 A 6 C 6 F 6 G 6 H 7 J 7 第五循环结束 K 5 A 6 C 6 F 6 G 6 H 7 J 7 第六循环结束 L 5 A 6 C 6 F 6 G 6 H 7 J 7 M 7 第七循环结束在第4步成功退出 CLOSED表 s 4 s 4 B 4 s 4 B 4 D 5 s 4 B 4 D 5 E 5 s 4 B 4 D 5 E 5 I 5 s 4 B 4 D 5 E 5 I 5 K 5 3 5 2 爬山法 过程 Hill climbing1 n s s为初始节点2 LOOP IFGOAL n THENEXIT SUCCESS 3 EXPAND n mi 计算h mi nextn m minh mi 的节点 4 IFh n h nextn THENEXIT FAIL 5 n nextn 6 GOLOOP 显然如果将山顶作为目标 h n 就表示山顶与当前位置的高度之差 则算法总是力图登向山顶 在单峰的情况下 必能到达山峰 3 5 3 分支限界法 分支限界法是优先扩展当前具有最小耗散值分支路径的叶节点n 其评价函数为f n g n 其思想是 建立一个局部路径 或分支 的队列表 每次都选耗散值最小的那个分支上的叶节点来扩展 直到生成出含有目标节点的路径为止 过程Branch Bound1 QUEUE s s g s 0 2 LOOP IFQUEUE THENEXIT FAIL 3 PATH FIRST QUEUE n LAST PATH 4 IFGOAL n THENEXIT SUCCESS 5 EXPAND n mi 计算g mi g n mi REMOVE s n QUEUE ADD s mi QUEUE 6 QUEUE中局部路径g值最小者排在前面 7 GOLOOP 例 八城市地图网问题 应用该算法求解图3 14的最短路径问题 其搜索图如图3 15所示 图3 14 八城市地图网示意图 图3 15 分支限界搜索图 求解过程中QUEUE的结果 初始 s 0 1 A 3 D 4 2 D 4 B 7 D 8 3 E 6 B 7 D 8 A 9 4 B 7 D 8 A 9 F 10 B 11 5 D 8 A 9 F 10 B 11 C 11 E 12 6 A 9 E 10 F 10 B 11 C 11 E 12 7 E 10 F 10 B 11 C 11 E 12 B 13 8 F 10 B 11 C 11 E 12 B 13 F 14 B 15 9 B 11 C 11 E 12 t 13 B 13 F 14 B 15 10 C 11 E 12 t 13 B 13 F 14 A 15 B 15 C 15 11 E 12 t 13 B 13 F 14 A 15 B 15 C 15 12 t 13 B 13 F 14 D 14 A 15 B 15 C 15 F 16 13 结束 3 5 4 动态规划法 动态规划法实际上就是对分支限界的改进 从图3 15看出 第2循环扩展A 3 后生成的D 8 节点 D 4 已在QUEUE上 和第3循环扩展D 4 之后生成的A 9 节点 A 3 已在QUEUE上 都是多余的分支 因为由s D到达目标的路径显然要比s A D到达的路径要好 因此删去类似s A D或s D A这样一些多余的路径将会大大提高搜索效率 动态规划原理指出 求s t的最佳路径时 对某个中间节点I 只要考虑s到I中具有最小耗散值这一条局部路径就可以 其余s到I的路径是多余的 具有动态规划原理的分支限界算法 过程Dynamic Programming1 QUEUE s s g s 0 2 LOOP IFQUEUE THENEXIT FAIL 3 PATH FIRST QUEUE n LAST PATH 4 IFGOAL n THENEXIT SUCCESS 5 EXPAND n mi 计算g mi g n mi REMOVE s n QUEUE ADD s mi QUEUE 6 QUEUE中有多条到达某一公共节点的路径 则只保留耗散值最小的那条路径 其余删去 并重新排序 g值最小者排在前面 7 GOLOOP 图3 16 动态规划原理的搜索树 3 5 5 最佳图搜索算法A 在算法A中 当h n h n 时 我们把这个算法称为A 算法 A 算法具有如下的性质 完备性 如果问题有解 则算法一定能找到解 定理1 2 可采纳性 如果问题有解 则算法一定能找到最佳解 即算法总能找到一条从S到目标节点的最佳路径 定理3 最优性 对两个算法A 算法A1和A2 若对所有非目标节点均有h1 n h2 n h n 则算法A1展开的节点数目至少和A2一样多 启发函数和A 算法的关系 定理4 通过对这几条性质的证明 定理 可得到几个有助于理解A 算法的结论 A 算法结束前 OPEN表中必存在f n f S 的节点 n是在最佳路径上的节点 引理2 2 OPEN表上任一具有f n f S 的节点n 最终都将被A 选作扩展的节点 推论2 1 A 选作扩展的任一节点 有f n f S 推论3 1 例 使用启发函数h n 给定各节点的h值 的A 算法 比不使用h n h n 0 的A 算法 求得最佳路径时扩展的节点数要少 图3 17 启发函数h n 的效果比较 h n 0时OPEN和CLOSED表的元素排列如下 S 0 A 4 B 5 C 6 B 5 C 6 D 7 E 7 F 7 C 6 D 7 E 7 F 7 H 7 I 7 D 7 E 7 F 7 H 7 I 7 J 7 K 7 E 7 F 7 H 7 I 7 J 7 K 7 t1 11 t2 11 F 7 H 7 I 7 J 7 K 7 t1 11 t2 11 t3 11 H 7 I 7 J 7 K 7 t1 11 t2 11 t3 11 t4 11 I 7 J 7 K 7 t1 11 t2 11 t3 11 t4 11 t5 11 J 7 K 7 t1 11 t2 11 t3 11 t4 11 t5 11 t6 11 K 7 t7 8 t6 9 t1 11 t2 11 t3 11 t4 11 t5 11 t7 8 t6 9 t8 10 t1 11 t2 11 t3 11 t4 11 t5 11 S 0 S 0 A 4 S 0 A 4 B 5 S 0 A 4 B 5 C 6 S 0 A 4 B 5 C 6 D 7 S 0 A 4 B 5 C 6 D 7 E 7 S 0 A 4 B 5 C 6 D 7 E 7 F 7 S 0 A 4 B 5 C 6 D 7 E 7 F 7 H 7 S 0 A 4 B 5 C 6 D 7 E 7 F 7 H 7 I 7 S 0 A 4 B 5 C 6 D 7 E 7 F 7 H 7 I 7 J 7 S 0 A 4 B 5 C 6 D 7 E 7 F 7 H 7 I 7 J 7 K 7 h n 不为0时 OPEN和CLOSED表的元素排列如下 S 7 C 8 A 9 B 9 J 8 A 9 B 9 K 9 I 10 t7 8 A 9 B 9 K 9 t6 9 I 10 S 7 S 7 C 8 S 7 C 8 J 8 图3 18 A 算法多次扩展同一节点搜索图的例子 下面的表格列出了调用算法A 过程时OPEN和CLOSED表的状态 从CLOSED表看出 在修改ml类节点指针的过程中 节点A B C重复扩展 次数分别为8 4 2 共扩展16次节点 步 一个启发函数 如果对所有节点ni和nj nj是ni的子节点 都有h ni h nj 节点间的估计值 C ni nj 实际值 或h ni C ni nj h nj 且h ti 0 则称启发h函数满足单调限制条件 在满足单调限制的A 算法 1 扩展了节点n 就找到了到达节点n的最佳路径 有g n g n 定理5 2 评价函数f值是非递减的 即f ni f nj 定理6 由于扩展后 即是最佳路径 因此不必进行指针纠正操作 故改善了A 效率 从图3 18的例子可见 因h不满足单调限制条件 在扩展节点n时 有可能还没有找到到达n的最佳路径 因此该节点还会再次被放入OPEN表中 为了使A 算法少进行重复扩展 可作如下改进 如果我们扩展的顺序不以f排列 而以g的大小排列 就得到修正的A 算法 修正过程的A 算法 OPEN s f s g s h s h s fm 0 LOOP IFOPEN THENEXIT FAIL NEST ni f ni fm NEST给出了OPEN表中满足f fm的节点集合 fm为处理过的节点中最大的f值 IFNEST THENn n min gi ELSEn FIRST OPEN fm f n NEST不空时 取其中g的最小者作为当前节点 否则取OPEN的第一个为当前节点 4 8同过程A 修正后的情况如下表所示 由OPEN和CLOSED中的状态看出 修正后的算法减少了重复扩展的次数 即在扩展期间 同一个节点就不会被扩展多次了 一般情况下 它比A 算法扩展节点的次数要少或相等 A 算法应用举例 1 八数码问题1 定义评价函数为f n d n w n h n w n 定义为 不在位 的将牌个数 尽管我们不能确切知道h n 但根据 不在位 将牌个数的估计 就能得出至少需要移动w n 步才能达到目标 显然有h n w n h n 图3 13 2 定义评价函数为f n d n p n p n 定义为每个将牌与其目标位置之间最短距离的总和 同样由于至少需要p n 步才能达到目标 因此 也满足h n h n 可见 这两种情况都是A 算法 图3 19给出了h n p n 的搜索图 并标出了相应的启发函数值 由解路可给出g n 和h n 的值 由此可得最佳路径上的节点有f g h 5 下表为不同启发函数 应用A 算法求最佳解时所扩展和生成的节点数 可见函数p n 比w n 更好 减少了搜索次数 这里在第3层中用w n 时有两个状态的f n 相同 而用p n 就没有相同f n 的状态了 可见 启发式函数选取的好坏 直接影响到搜索的效果 2 M C问题 missionaryandcannibal 有N个传教士和N个野人来到河边准备渡河 河岸有一条船 每次至多可供k人乘渡 问传教士为了安全起见 应如何规划摆渡方案 使得任何时刻 河两岸以及船上的野人数目总是不超过传教士数目 当传教士和野人共存时 即求解传教士和野人从左岸全部摆渡到右岸的过程中 在共存的情况下任何时候满足M C 在摆渡过程中M C k 设N 5 k 3 则给定的问题可以用图3 20表示 图中L和R表示左岸和右岸 B 1或0分别表示有船或无船 约束条件是 两岸或船上M C 且船的容量M C 3 综合数据库 用三元组表示 即 ML CL BL 其中 0 ML CL 5 BL 0or1 问题被简化为 5 5 1 0 0 0 规则集合 由摆渡操作组成 它有两种操作 Pmc 从左岸划到右岸 和qmc 从右岸划到左岸 每次摆渡操作 船上人数的合理的组合数乘以2 就是规则数 规则形式如 if ML CL BL 1 then ML 1 CL BL 1 P10操作 if ML CL BL 1 then ML CL 1 BL 1 P01操作 if ML CL BL 1 then ML 1 CL 1 BL 1 P11操作 if ML CL BL 1 then ML 2 CL BL 1 P20操作 P30 P21 P02 P03 if ML CL BL 0 then ML 1 CL BL 1 q10操作 if ML CL BL 0 then ML CL 1 BL 1 q01操作 if ML CL BL 0 then ML 1