《人工智能原理》由会员分享，可在线阅读，更多相关《人工智能原理（56页珍藏版）》请在金锄头文库上搜索。
1、窗傍益龙亩皑驴睹刮竞脉淀伴息硝咬须登汗汤狈沼木埔蒲是暇却背渊秩囤人工智能原理人工智能原理人工智能原理第三章搜索推理技术均秽锋待希苟字笺腹梁故晃辐喀聚扣尘墩濒斤类设撑股映毅罪盔孰墓睛莎人工智能原理人工智能原理1从问题表示到问题的解决，有一个求解的从问题表示到问题的解决，有一个求解的过程。接下来要研究的是实现求解的过程，过程。接下来要研究的是实现求解的过程，采用的基本方法包括采用的基本方法包括搜索搜索和和推理推理。本章先介绍本章先介绍搜索技术搜索技术，将要讨论问题求解，将要讨论问题求解的搜索原理，包括一些早期的搜索技术或的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些用于解
2、决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原比较新的能够求解比较复杂问题的搜索原理，包括理，包括A*算法。算法。龄仑八辆渝舔半苑惮凄考馅蛇停派债蛮迂习柏唁麦低客苏犀獭钞振樟唐嗡人工智能原理人工智能原理23.1 3.1 图搜索策略图搜索策略可把图搜索策略看成一种在图中寻找路径可把图搜索策略看成一种在图中寻找路径的方法的方法图中的节点对应于状态，而连线对应于操图中的节点对应于状态，而连线对应于操作符。这些节点和连线作符。这些节点和连线(即状态与操作符即状态与操作符)又分别由产生式系统的数据库和规则来标又分别由产生式系统的数据库和规则来标记记初始节点和目标节点之间的路径。即求得
3、初始节点和目标节点之间的路径。即求得把一个数据库变换为另一数据库的规则序把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题列问题就等价于求得图中的一条路径问题授颠羚士再艺幸筷贴动梧沙辗痈卡昧蓖次怪爱旁夏邦喘夸魄油例助坛亚震人工智能原理人工智能原理3例子：从某王姓家族的四代中找王例子：从某王姓家族的四代中找王A的后代且其的后代且其寿命为寿命为X的人。的人。王王A：寿命：寿命47，有儿子王，有儿子王B1、王、王B3、王、王B2王王B1：寿命：寿命77，有儿子王，有儿子王C1、王、王C2王王B3：寿命：寿命52，有儿子王，有儿子王D1王王B2：寿命：寿命65，有儿子王，有儿子王
4、E1、王、王E2王王F1：寿命：寿命32 王王G1：寿命：寿命96王王C2：寿命：寿命87，有儿子王，有儿子王F1王王D1：寿命：寿命77，没有儿子，没有儿子王王E1：寿命：寿命57，有儿子王，有儿子王G1险卡岳咙贷堰氧掳汗烬身了溢戍膏疑铡池尘敲搭扮肚激筷蔡酬悬殆府讼问人工智能原理人工智能原理4 王王E2：寿命：寿命92，有儿子王，有儿子王H1 王王C1：寿命：寿命27，没有儿子，没有儿子王王H1：寿命：寿命51若若X=57，下面讨论一种可通用的图搜索策略求解，下面讨论一种可通用的图搜索策略求解此问题。此问题。如果是一个如果是一个N代的家族表中找其寿命为代的家族表中找其寿命为X的人，的人，我们
5、最可能用的我们最可能用的手工方法手工方法是从家族表的开始往下，是从家族表的开始往下，例中还要求所找的人是某人的后代，就比较复杂例中还要求所找的人是某人的后代，就比较复杂了。如果用了。如果用图图来表示，就很容易了。图中把姓氏来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后省去，每个成员的后代按例子中给出名字的先后顺序。图示为：顺序。图示为： 狄睦厉女眨纱雍帆磋疫魔轮铂募秧猾萨何茧掏肚买汛斥乌敞坪溅厨杭栏画人工智能原理人工智能原理5托塞扳峡迸毛亲万鳖亩偷瓶瘸琅湃谗戳道痊栓宴卑系孪钙鹤艇垦蘸绢黄雄人工智能原理人工智能原理6图搜索图搜索(GRAPHSEARCH)(GRAPHSE
6、ARCH)的一般过程如下：的一般过程如下：(1) 建立一个只含有建立一个只含有起始节点起始节点S的搜索图的搜索图G，把，把S放到一个叫做放到一个叫做OPEN的的未未扩展扩展节点表中（简称节点表中（简称OPEN表）。表）。(2) 建立一个叫做建立一个叫做CLOSED的的已扩展已扩展节点表（简称节点表（简称CLOSED表），其初表），其初始为空表。始为空表。(3) LOOP：若：若OPEN表是空表，则失败退出。表是空表，则失败退出。(4) 选择选择OPEN表上的第一个节点，把它从表上的第一个节点，把它从OPEN表移出并放进表移出并放进CLOSED表中。称此节点为节点表中。称此节点为节点n，它是，它
7、是CLOSED表中节点的编号。表中节点的编号。(5) 若若n为一目标节点，则有解并成功为一目标节点，则有解并成功退出退出，此解是追踪图，此解是追踪图G中沿着指针中沿着指针从从n到到S这条路径而得到的这条路径而得到的(指针将在第指针将在第7步中设置步中设置)。(6) 扩展节点扩展节点n，同时生成不是，同时生成不是n的祖先的那些后继节点的集合的祖先的那些后继节点的集合M。把。把M的的这些成员作为这些成员作为n的后继节点添入图的后继节点添入图G中。中。 (7) 对那些未曾在对那些未曾在G中出现过的中出现过的(既未曾在既未曾在OPEN表上或表上或CLOSED表上出表上出现过的现过的)M成员成员设置设置
8、一个通向一个通向n的指针。把的指针。把M的这些成员加进的这些成员加进OPEN表。表。对已经在对已经在OPEN或或CLOSED表上的每一个表上的每一个M成员，确定是否需要成员，确定是否需要更改更改通通到到n的指针方向。对已在的指针方向。对已在CLOSED表上的每个表上的每个M成员，确定是否需成员，确定是否需要更改图要更改图G中通向它的每个中通向它的每个后裔后裔节点的指针方向。节点的指针方向。(8) 按某一任意方式或按某个探试值，按某一任意方式或按某个探试值，重排重排OPEN表。表。 (9) GO LOOP。阶追僚瑚凳例菲排枉番段伐折靠务先涨汛勾表道良是接妄趁膏吗岿柬佐都人工智能原理人工智能原理7
9、图搜索算法中的几个重要名词图搜索算法中的几个重要名词 1 1OPENOPEN表表 2 2CLOSEDCLOSED表表 节点节点父节点父节点编号编号节点节点父节点父节点庶遍屏兑颐钻滨坑火情稳负政谢佣谐动赦局峙阎灭溯邢崎女狡哦舞凶朋奢人工智能原理人工智能原理83 3搜索图与搜索树搜索图与搜索树此过程生成一个明确的图此过程生成一个明确的图G(称为搜索图称为搜索图)和和一个一个G的子集的子集T(称为搜索树称为搜索树)，树，树T上的每个节点上的每个节点也在图也在图G中。搜索树是由第中。搜索树是由第7步中设置的指针来确步中设置的指针来确定的。定的。G中的每个节点中的每个节点(除除S外外)都有一个只指向都有
10、一个只指向G中一个父辈节点的指针，该父辈节点就定为树中中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。那个节点的唯一父辈节点。齐属横朵哟粘章墙肪态肃议汕再闻寅振霍昨刽琼涵晾记堆康缎阵阵厚沃治人工智能原理人工智能原理9峻骇层己差鹏冷郊囱练踪仙匀斋逝矗殃纤捕教番独枝玫汽透靛娩割遁未揉人工智能原理人工智能原理10图搜索方法的几点分析：图搜索方法的几点分析：图搜索过程的第图搜索过程的第8步对步对OPEN表上的节点进行表上的节点进行排序排序，以便，以便能够从中选出一个能够从中选出一个“最好最好”的节点作为第的节点作为第4步扩展用。这步扩展用。这种排序可以是种排序可以是任意任意的即盲目的
11、的即盲目的(属于盲目搜索属于盲目搜索)，也可以用，也可以用以后要讨论的各种以后要讨论的各种启发启发思想或其它准则为依据思想或其它准则为依据(属于启发属于启发式搜索式搜索)。每当被选作扩展的节点为目标节点时，这一过。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向点的这条成功路径，其办法是从目标节点按指针向S返回返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终失败告终(某些节点最终可能没有后继节点，
12、所以某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表表可能最后变成空表)。在失败终止的情况下，从起始节。在失败终止的情况下，从起始节点出发，一定达不到目标节点。点出发，一定达不到目标节点。铜硒勒迫撼语祖导砒世异承恩翠赏破氢摆烟蜜广哎竣迂议屏纤铲补蜗溜详人工智能原理人工智能原理113.2 3.2 盲目搜索盲目搜索盲目搜索：无需重新安排盲目搜索：无需重新安排OPEN表的搜索表的搜索盲目搜索又叫做无信息搜索，一般只适用盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。于求解比较简单的问题。宽度优先搜索宽度优先搜索深度优先搜索深度优先搜索等代价搜索等代价搜索叙捌发骏堆孜缆坡孙慷荡莹
13、嫌锋罚兄栋添诲鳞牢冬厕搅邪朴莱字主绒艳椰人工智能原理人工智能原理123.2.1 3.2.1 宽度优先搜索宽度优先搜索 回顾上一节的寻找寿命为回顾上一节的寻找寿命为X的人的例子，如果搜的人的例子，如果搜索时，从节点索时，从节点A开始，对他的三个儿子按从左至开始，对他的三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，右搜索，然后对他的所有孙子按从左至右搜索，依此下去。这种搜索方式就是宽度优先搜索。依此下去。这种搜索方式就是宽度优先搜索。宽度优先搜索宽度优先搜索(breadth-first search)的定义：的定义：如果搜索是以如果搜索是以接近接近起始节点的程度依次扩展节点起始节点的程
14、度依次扩展节点的，那么这种搜索就叫做宽度优先搜索的，那么这种搜索就叫做宽度优先搜索(breadth-first search)，如图，如图3.3所示。所示。绦臂阵阁饵斌盟埋斟漆审荧户垢测听耐赏榜秽腕嘲粟硅揪踏束鳖腮津甥型人工智能原理人工智能原理13从图可见，这从图可见，这种搜索是种搜索是逐层逐层进行的；在对进行的；在对下一层的任一下一层的任一节点进行搜索节点进行搜索之前，必须搜之前，必须搜索完本层的所索完本层的所有节点。有节点。 亥俊瑶雪馏臻绣泪盐隅综阶岭咬娜遍操虞苟彰论乳坠斌呸碑拨泌天疲店脾人工智能原理人工智能原理14上够斡篓沥朝希疮把因缘犬骚谱烃非斩吏乌丫纪澡诀担蒂蛮主胰营赦罪臼人工智能原
15、理人工智能原理15宽度优先搜索算法如下：宽度优先搜索算法如下： (1) 把起始节点放到把起始节点放到OPEN表中表中(如果该起始节点为一如果该起始节点为一目标节点，则求得一个解答目标节点，则求得一个解答)。(2) 如果如果OPEN是个空表，则没有解，失败退出；否是个空表，则没有解，失败退出；否则继续。则继续。(3) 把第一个节点把第一个节点(节点节点n)从从OPEN表移出，并把它放表移出，并把它放入入CLOSED扩展节点表中。扩展节点表中。(4) 扩展节点扩展节点n。如果没有后继节点，则转向上述第。如果没有后继节点，则转向上述第(2)步。步。(5) 把把n的所有后继节点放到的所有后继节点放到O
16、PEN表的表的末端末端，并提，并提供从这些后继节点回到供从这些后继节点回到n的指针。（队列模式）的指针。（队列模式） (6) 如果如果n的任一个后继节点是个目标节点，则找到一的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第个解答，成功退出；否则转向第(2)步。步。驯顺验纶埔幻舱前牺膨旷挞椿陨术贯必侦骑辫啡窃潍暖钙寒广声箩痴眩辙人工智能原理人工智能原理16毁纪入蛆株墅化埂丸腹瑟亮筑紧瓮园鸣罕熄湃锌诽边删哩楔锈俺饵嫩裸肺人工智能原理人工智能原理17宽度优先搜索方法分析：宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的宽度优先搜索是图搜索一般过程的特殊特殊情况，将图搜情况，将图
17、搜索一般过程中的第索一般过程中的第8步具体化为本算法中的第步具体化为本算法中的第6步，这步，这实际是将实际是将OPEN表作为表作为“先进先出先进先出”的队列进行操作。的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的目标节点的最短途径最短途径；这棵搜索树提供了所有存在的；这棵搜索树提供了所有存在的路径路径(如果没有路径存在，那么对有限图来说，我们就如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止说该法失败退出；对于无限图来说，则永远不会终止)。亦钢榷壳嗽剖拣毋砸联姆痢君总汁绞此逾俗厉抚呵
18、救搐靳嗡梁咱沟杠逛琳人工智能原理人工智能原理18例：把宽度优先搜索应用于八数码难题时所生成例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：目标棋局的问题： 搜索树上的所有节点都标记它们所对应的状态描搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格按顺时针方向移动空格)。图中最后一个节点是。图中最后一个节点是目标节点。目标节点。蚜返筷川权邢桌鸥橡读视眼抑客抑枷灿孵忙象巢斜汤彪栋渤告始闹届枯福人工智能原理人工智
19、能原理19图图 3.5 3.5 八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树 尉浪份武布禾剔杂刨笺墨豢殷盔听檬诅琅再纫坷调贸邱伸浑较霓暴羌猴哀人工智能原理人工智能原理203.2.2 3.2.2 深度优先搜索深度优先搜索另一种盲目另一种盲目(无信息无信息)搜索叫做深度优先搜索搜索叫做深度优先搜索(depth-first search)。首先扩展最新产生的节点。如下图首先扩展最新产生的节点。如下图许明褂萨祖疾置燕挥祸题赐昏撅熬褐涧脆踢全仿姓防诉滚揍农精挞赏蛾脏人工智能原理人工智能原理21图图 3.6 3.6 深度优先搜索示意图深度优先搜索示意图 图3.6深度优先搜索示意图逆阴罕周毡吐佑机斥
20、谦荚胺獭肘碍掌连彼藐困彰厦尽赴歪课冯钧腾犯负入人工智能原理人工智能原理22分析深度优先搜索示意图可看出，在深度优先搜分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的索中，我们首先扩展最新产生的(即最深的即最深的)节点。节点。深度相等的节点可以深度相等的节点可以任意任意排列。排列。斧今吱傲匆铀祝声饮剑觉帮呕挛块诵赦父彻彻陨仅客沙乒魏壳肪聪监纫至人工智能原理人工智能原理23我们定义节点的深度如下：我们定义节点的深度如下：(1) 起始节点起始节点(即根节点即根节点)的深度为的深度为0。(2) 任何其它节点的深度等于其父辈节点深任何其它节点的深度等于其父辈节点深度加上度加上1。首
21、先，扩展最深的节点的结果使得搜索沿着首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个去；只有当搜索到达一个没有后裔没有后裔的状态时，它的状态时，它才考虑另一条替代的路径。替代路径与前面已经才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后试过的路径不同之处仅仅在于改变最后n步，而步，而且保持且保持n尽可能小。尽可能小。箍蚤蔑录谎耳无鱼想掷退皋唯万劝亦牺丹乘属釜丰善抚屯虑缓碴倒着促爽人工智能原理人工智能原理24对于许多问题，其状态空间搜索树的深度可能为对于许多问题，其状态空间
22、搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的列的已知深度上限还要深。为了避免考虑太长的路径路径(防止搜索过程沿着无益的路径扩展下去防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度往往给出一个节点扩展的最大深度深度界限深度界限。任何节点如果达到了深度界限，那么都将把它们任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一用了深度界限的规定，所求得的解答路径并不一定
23、就是最短的路径。定就是最短的路径。晌疯鸟壤川窜貉懊肄惮怂课樟燥鹿污括悲杆企噎坏渡炮观潘轮脸淬驯臻玉人工智能原理人工智能原理25含有深度界限的深度优先搜索算法如下：含有深度界限的深度优先搜索算法如下：(1) 把起始节点把起始节点S放到未扩展节点放到未扩展节点OPEN表中。表中。如果此节点为一目标节点，则得到一个解。如果此节点为一目标节点，则得到一个解。(2) 如果如果OPEN为一空表，则失败退出。为一空表，则失败退出。(3) 把第一个节点把第一个节点(节点节点n)从从OPEN表移到表移到CLOSED表。表。(4) 如果节点如果节点n的深度等于最大深度，则转向的深度等于最大深度，则转向(2)。(5
24、) 扩展节点扩展节点n，产生其全部后裔，并把它们，产生其全部后裔，并把它们放入放入OPEN表的表的前头前头。如果没有后裔，则转向。如果没有后裔，则转向(2)。(6) 如果后继节点中有任一个为目标节点，如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向则求得一个解，成功退出；否则，转向(2)。枷贡抿度春赫栋夹屑秋涂讹娠毕饶诈荷赃妨的芦境简兵靠巨伐叠狡泡朽绣人工智能原理人工智能原理26算法演示图算法演示图 倚寐鸳皋轨量札技劲拎曙娟咋邦砌知碘纫坊烂野摇贯槐实荷盒眩点里材尘人工智能原理人工智能原理27例：按深度优先搜索生成的八数码难题搜索树，例：按深度优先搜索生成的八数码难题搜索树，
25、我们设置深度界限为我们设置深度界限为5 5。图图3.83.8绘出了搜索树，粗线条的路径表明含绘出了搜索树，粗线条的路径表明含有有5 5条应用规则的一个解。从图可见，深度优先条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。后两步有差别的那些路径，等等。奖兼哼继兜口蛀抨蝎唇昂源击茧邢脐价噎萍叔磅名室澳溢雁葡抬憨亮揭舌人工智能原理人
26、工智能原理28图图 3.8 3.8 八数码难题的深度优先搜索树八数码难题的深度优先搜索树 寿涣雌秆聊滑嚣砰愈鸳蜀疙躁彝揖课侯姬膏和啪翰焚豢胚屡茸办课量喷虱人工智能原理人工智能原理293.2.3 3.2.3 等代价搜索等代价搜索有些问题并不要求有应用算符序列为最少的解，有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代弧线上的有关代价以及随之而求得的具有最小代价的解答路径，与许多这样的广义准则相符合。价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从
27、起始宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做种推广了的宽度优先搜索算法叫做等代价搜索算等代价搜索算法。法。组饮晌频怂帕牵冉迷圆摇余行随锅针森纺涂甩炊水边嘎噎妖形糊粘淡许卒人工智能原理人工智能原理30有如下一些记号：有如下一些记号：起始节点记为起始节点记为S；从节点从节点i到它的后继节点到它的后继节点j的连接弧线代价记的连接弧线代价记为为c(i,j)；从起始节点从起始节点S到任一节点到任一节点i的路径代价记为的路径代价记为g(i)。在搜索树上，我们假设在搜索树上，我们假设g(i)也
28、是从起始节点也是从起始节点S到节到节点点i的的最少代价最少代价路径上的代价，因为它是唯一的路路径上的代价，因为它是唯一的路径；径；逆颂逊潜荫曹煎犬豢药殆职业劣氛航郭山宙袍妻蝶儡舜恰淹挣手弦融啸谆人工智能原理人工智能原理31等代价搜索算法等代价搜索算法等代价搜索方法以等代价搜索方法以g(i)的递增顺序扩展其节点，其算法：的递增顺序扩展其节点，其算法：(1) 把起始节点把起始节点S放到未扩展节点表放到未扩展节点表OPEN中。如果此中。如果此起始节点为一目标节点，则求得一个解起始节点为一目标节点，则求得一个解;否则令否则令g(S)=0。(2) 如果如果OPEN是个空表，则没有解而失败退出。是个空表，
29、则没有解而失败退出。(3) 从从OPEN表中选择一个节点表中选择一个节点i，使其，使其g(i)为最小。为最小。如果有几个节点都合格，那么就要选择一个目标节点作为如果有几个节点都合格，那么就要选择一个目标节点作为节点节点i(要是有目标节点的话要是有目标节点的话)；否则，就从中选一个作为节；否则，就从中选一个作为节点点i。把节点。把节点i从从OPEN表移至扩展节点表表移至扩展节点表CLOSED中。中。(4) 如果节点如果节点i为目标节点，则求得一个解。为目标节点，则求得一个解。(5) 扩展节点扩展节点i。如果没有后继节点，则转向第。如果没有后继节点，则转向第(2)步。步。(6) 对于节点对于节点i
30、的每个后继节点的每个后继节点j，计算，计算g(j)=g(i)+c(i,j)，并把所有后继节点，并把所有后继节点j放进放进OPEN表。提供回到节点表。提供回到节点i的指的指针。针。(7) 转向第转向第(2)步。步。辱棵淳对戏攀玄投哦直剃纠互攀调蜒曙巨咕垂鸭蒜敬侮厦仓稠琼喀拨箱荔人工智能原理人工智能原理32图图 3.9 3.9 等代价搜索算法框图等代价搜索算法框图 愧宵嫂状碘饺催吱荤书迅琉乖罕攻毛与宦陵滇抉僚帽体除危曹卑区桐秧专人工智能原理人工智能原理333.3 3.3 启发式搜索启发式搜索 盲目搜索的不足：效率低，耗费过多的计算空间盲目搜索的不足：效率低，耗费过多的计算空间与时间与时间 分析前面
31、介绍的宽度优先、深度优先搜索，分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法或等代价搜索算法,其主要的差别是其主要的差别是OPEN表中待表中待扩展节点的顺序问题。人们就试图找到一种方法扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择用于排列待扩展节点的顺序，即选择最有希望最有希望的的节点加以扩展，那么，搜索效率将会大为提高。节点加以扩展，那么，搜索效率将会大为提高。 启发信息启发信息：进行搜索技术一般需要某些有关：进行搜索技术一般需要某些有关具体问题领域具体问题领域的特性的，与具体问题求解过程有的特性的，与具体问题求解过程有关的，并可关的，并可指导指导搜索过程
32、朝着最有希望方向前进搜索过程朝着最有希望方向前进的控制信息，把此种信息叫做的控制信息，把此种信息叫做启发信息启发信息。 把利用启发信息的搜索方法叫做把利用启发信息的搜索方法叫做启发性搜索方法启发性搜索方法付木口市三俐啸咖岩掣凰补潍蜗宝艺衣犯善酵焦困攻居七菇湾需豆坪询抡人工智能原理人工智能原理343.3.1 3.3.1 启发式搜索策略启发式搜索策略启发信息按其用途可分为下列启发信息按其用途可分为下列3种：种：(1) 用于决定用于决定要扩展要扩展的下一个节点，以免像在宽度优的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。先或深度优先搜索中那样盲目地扩展。(2) 在扩展一个节点的过程中
33、，用于决定要在扩展一个节点的过程中，用于决定要生成生成哪一哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节个或哪几个后继节点，以免盲目地同时生成所有可能的节点。点。(3) 用于决定某些应该从搜索树中用于决定某些应该从搜索树中抛弃抛弃或修剪的节点。或修剪的节点。在本节中，只讨论利用上述第一种启发信息的状态空在本节中，只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择索总是选择“最有希望最有希望”的节点作为下一个被扩展的节点。的节点作为下一个被扩展的节点。这种搜索叫做这种搜索叫做有序搜索有序搜索(
34、ordered search)。叼此噎朗汾寓饼便味张性挟迫撑穴杀旭漳睁噬轨惮须滩桂内抚沃包铀菠仟人工智能原理人工智能原理353.3.2 3.3.2 估价函数估价函数用来估算节点希望程度的量度，叫做用来估算节点希望程度的量度，叫做估价函数估价函数(evaluation function)。估价函数的任务就是估计估价函数的任务就是估计OPEN表中各节点的重要程度。表中各节点的重要程度。一个节点的一个节点的“希望希望”(promise)有几种不同的定义方法。有几种不同的定义方法。在状态空间问题中，在状态空间问题中，一种方法一种方法是估算目标节点到此节点的是估算目标节点到此节点的距离；距离；另一种方法
35、另一种方法认为，解答路径包括被估价过的节点，认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量标准只能并计算全条路径的长度或难度。每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节考虑该问题中这个节点的某些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。点与目标节点进行比较，以决定相关特性。我们用符号我们用符号f来标记估价函数，用来标记估价函数，用f(n)表示节点表示节点n的估的估价函数值。暂时令价函数值。暂时令f为任意函数，为任意函数，以后我们将会提出以后我们将会提出f是从是从起始节点约束地通过节点起始节点约束地通过节点n而到达目
36、标节点的最小代价路而到达目标节点的最小代价路径上的一个估算代价。径上的一个估算代价。 一般形式：一般形式：f(n)=g(n)+h(n)，g(n)是从是从s0到到n的实际代价，的实际代价，h(n)是从节点是从节点n到目标节点到目标节点sg的估计代价。的估计代价。都歼烬卿较迫躯吻优樊酶肄啊拧炼乡赦氖恕辣队鞘粹樊糯衫歹枉赁士磷猾人工智能原理人工智能原理363.3.3 3.3.3 有序搜索有序搜索 我们用估价函数我们用估价函数f来排列来排列GRAPHSEARCH第第8步中步中OPEN表上的节点。根据习惯，表上的节点。根据习惯，OPEN表上的节点按照它们表上的节点按照它们f函数函数值的递增顺序排列。根据
37、推测，某个具有低的估价值的节值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。应用某个算法点较有可能处在最佳路径上。应用某个算法(例如等代价例如等代价算法算法)选择选择OPEN表上具有最小表上具有最小f值的节点作为下一个要扩值的节点作为下一个要扩展的节点。这种搜索方法叫做展的节点。这种搜索方法叫做有序搜索有序搜索或或最佳优先搜索最佳优先搜索，而其算法就叫做而其算法就叫做有序搜索算法有序搜索算法或或最佳优先算法最佳优先算法。可见它总。可见它总是选择最有希望的节点作为下一个要扩展的节点。是选择最有希望的节点作为下一个要扩展的节点。有序搜索有序搜索(ordered sear
38、ch)又称为又称为最好优先搜索最好优先搜索(best-first search)。尼尔逊（尼尔逊（Nilsson）曾提出一个有序搜索的基本算法。估价）曾提出一个有序搜索的基本算法。估价函数函数f是这样确定的：一个节点希望程度越大，其是这样确定的：一个节点希望程度越大，其f值就越值就越小。被选为扩展的节点，是估价函数最小的节点。小。被选为扩展的节点，是估价函数最小的节点。隧萧辆汪住佐扇平星碌翘慑重埃僵椭瓜图跃说苗姜躁弧绰模处亩鼎择尖契人工智能原理人工智能原理37有序状态空间搜索算法如下：有序状态空间搜索算法如下：(1) 把起始节点把起始节点S放到放到OPEN表中，计算表中，计算f(S)并把其值与
39、节点并把其值与节点S联系起来。联系起来。(2) 如果如果OPEN是个空表，则失败退出，无解。是个空表，则失败退出，无解。(3) 从从OPEN表中选择一个表中选择一个f值最小的节点值最小的节点i。结果有几个节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点否则就选择其中任一个节点作为节点i。(4) 把节点把节点i从从OPEN表中移出，并把它放入表中移出，并把它放入CLOSED的扩展的扩展节点表中。节点表中。(5) 如果如果i是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个
40、解。呵睡斯啃谈宛丛胁饥正倾虏盅瘩筐躁匪研超拣帧捡监篡瑰偶沃颊中钒涤大人工智能原理人工智能原理38(6) 扩展节点扩展节点i，生成其全部后继节点。对于，生成其全部后继节点。对于i的每一个后继的每一个后继节点节点j：(a) 计算计算f(j)。(b) 如果如果j既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，则用估价函表中，则用估价函数数f把它添入把它添入OPEN表。从表。从j加一指向其父辈节点加一指向其父辈节点i的指针，以便一的指针，以便一旦找到目标节点时记住一个解答路径。旦找到目标节点时记住一个解答路径。(c) 如果如果j已在已在OPEN表上或表上或CLOSED表上，则比较刚刚对表
41、上，则比较刚刚对j计算计算过的过的f值和前面计算过的该节点在表中的值和前面计算过的该节点在表中的f值。如果值。如果新的新的f值较小值较小，则则(i) 以此新值取代旧值。以此新值取代旧值。(ii) 从从j指向指向i，而不是指向它的父辈节点。，而不是指向它的父辈节点。(iii) 如果节点如果节点j在在CLOSED表中，则把它移回表中，则把它移回OPEN表表(7) 转向转向(2)，即，即GO TO(2)。晋蔬叹吵拴爸抠医肯冗架佰祷抛寨巳邮拿八赠衫轻歧读审无帐沏眨湃窝河人工智能原理人工智能原理39注：注：步骤（步骤（6.c）是一般搜索图所需要的，该图中可能有一）是一般搜索图所需要的，该图中可能有一个以
42、上的父辈节点。具有最小估价函数个以上的父辈节点。具有最小估价函数f（j）的节点被）的节点被选作父辈节点。但是，由于搜索树，它最多只有一个选作父辈节点。但是，由于搜索树，它最多只有一个父辈节点，所以步骤（父辈节点，所以步骤（6.c）可以略去。值得提出的是，）可以略去。值得提出的是，即使搜索空间是一般的搜索图，其显示子搜索图总是即使搜索空间是一般的搜索图，其显示子搜索图总是一棵树，因为节点一棵树，因为节点j从来没有同时记录过一个以上的父从来没有同时记录过一个以上的父辈节点。辈节点。抠塌承机七丙崩材党咋郡盟翼窿孕帆肠机泊涵阮郴蕾粟职恢瞥读炊澈郴抱人工智能原理人工智能原理40图图3 310 10 有序
43、搜索算法框图有序搜索算法框图 明狱爆槛侦抡执焙淀辩岗鹏赠佯叠部希衔蹄骑夷设唾况缝倒够殷傀勃凰哮人工智能原理人工智能原理41宽度优先搜索、深度优先搜索和等代价搜索统统宽度优先搜索、深度优先搜索和等代价搜索统统是有序搜索技术的特例。对于宽度优先搜索，我是有序搜索技术的特例。对于宽度优先搜索，我们选择们选择f(i)作为节点作为节点i的深度。对于等代价搜索，的深度。对于等代价搜索，f(i)是从起始节点至节点是从起始节点至节点i这段路径的代价。这段路径的代价。有序搜索的有效性直接有序搜索的有效性直接取决于取决于f的选择的选择，如果，如果选择的选择的f不合适，有序搜索就可能失去一个最好的不合适，有序搜索就
44、可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量解甚至全部的解。如果没有适用的准确的希望量度，那么度，那么f的选择将涉及两个方面的内容：一方面的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。保证有一个最优的解或任意解。 昼副陛橡蒲怠零借唆怠疲皱茨菌暗境福郸窃敦策扁早稻僧伟迂批衔策活蚜人工智能原理人工智能原理42根据解答类型选择估价函数根据解答类型选择估价函数1.解空间中存在几个不同代价的解题路径解空间中存在几个不同代价的解题路径2.虽然存在几条路径，但是搜索的代价超过虽然存在几条路径，
45、但是搜索的代价超过时空限制，为此要找最佳（和最优差异程时空限制，为此要找最佳（和最优差异程度比较小）度比较小）3.不考虑解答的最优化，或许仅仅存在一个不考虑解答的最优化，或许仅仅存在一个答案，或所有解等价答案，或所有解等价松礁淑阐犁羞辫艾革寓没饵藩衙撮乡去累绩帅池摧究拼韵漫宛汕好舱遭演人工智能原理人工智能原理43有序搜索例子有序搜索例子下面让我们再次用八数码难题的例子来说明过程下面让我们再次用八数码难题的例子来说明过程GRAPHSEARCH是如何应用估价函数排列节点是如何应用估价函数排列节点的。举例说明如下：的。举例说明如下：我们采用了简单的估价函数我们采用了简单的估价函数 f(n)=d(n)
46、+W(n) 其中：其中：d(n)是搜索树中节点是搜索树中节点n的深度；的深度；W(n)用用来计算对应于节点来计算对应于节点n的数据库中错放的棋子个数。的数据库中错放的棋子个数。橙添序雏他翼嗅凰鳞派乔警帆颅成塑仓淑讼敢双汐浴渡砷苔湛厌舱摄窥痈人工智能原理人工智能原理44因此，起始节点棋局因此，起始节点棋局2 8 31 6 47 5的的f值等于值等于0+4=4。 悍头痹矽愧臀确贡栅镁誊随忘爽倚电褂厌壶廓拌束锹差剿温轮跑啤磨臆初人工智能原理人工智能原理45八数码难题的有序搜索树八数码难题的有序搜索树图中表示出利用这个估价图中表示出利用这个估价函数把函数把GRAPHSEARCH应用于八数码难题的结果。
47、应用于八数码难题的结果。图中圆圈内的数字表示该图中圆圈内的数字表示该节点的节点的f值。值。涯鸭雅亿咬带譬搂晒垣叭吹聂地涨善慢场衫静喇靠己停惫甭锐角黑嚣构颂人工智能原理人工智能原理46从图可见，这里所求得的解答路径和用其它搜索从图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应方法找到的解答路径相同。不过，估价函数的应用用显著地减少显著地减少了被扩展的节点数了被扩展的节点数(如果我们只用如果我们只用估价函数估价函数f(n)=d(n)，那么我们就得到宽度优先搜，那么我们就得到宽度优先搜索过程索过程)。正确地选择估价函数对确定搜索结果具有决定性正确地选择估价函数对确定
48、搜索结果具有决定性的作用。使用不能识别某些节点真实希望的估价的作用。使用不能识别某些节点真实希望的估价函数会形成函数会形成非非最小代价路径；而使用一个过多地最小代价路径；而使用一个过多地估计了全部节点希望的估价函数估计了全部节点希望的估价函数(就像宽度优先就像宽度优先搜索方法得到的估价函数一样搜索方法得到的估价函数一样)又会扩展又会扩展过多过多的的节点节点育酣吭浴赡机卒赌择星烷贿按倒懒古绥辟滁灵盆台褐熟噎怠燕东特膊垒腔人工智能原理人工智能原理473.3.4 A3.3.4 A* *算法算法A*算法的估价函数：算法的估价函数：让我们描述一个特别的估价函数，这个估价函让我们描述一个特别的估价函数，这
49、个估价函数数f使得在使得在任意节点任意节点上其函数值上其函数值f(n)能能估算估算出从节出从节点点S到节点到节点n的最小代价路径的代价与从节点的最小代价路径的代价与从节点n到到某一目标节点的最小代价路径的代价之总和，也某一目标节点的最小代价路径的代价之总和，也就是说就是说f(n)是约束是约束通过节点通过节点n的一条的一条最小代价最小代价路径路径的代价的一个估计。因此，的代价的一个估计。因此，OPEN表上具有最小表上具有最小f值的那个节点就是所估计的加有最少严格约束条值的那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。件的节点，而且下一步要扩展这个节点是合适的。
50、钓憾淘基粒尹渤渴评兰阜脾趋友愿觉飞彰簧辰页旗胁惭奋扫辜蝉竟呻疏辈人工智能原理人工智能原理48在正式讨论在正式讨论A*算法之前，先介绍几个记号。令算法之前，先介绍几个记号。令k(ni，nj)表示任意两个节点表示任意两个节点ni和和nj之间最小代价路之间最小代价路径的径的实际代价实际代价(对于两节点间没有通路的节点，对于两节点间没有通路的节点，函数函数k没有定义没有定义)。于是，从节点。于是，从节点n到某个具体的到某个具体的目标节点目标节点ti，某一条最小代价路径的代价可由，某一条最小代价路径的代价可由k(n,ti)给出。给出。令令h*(n)表示整个目标节点表示整个目标节点集合集合ti上所有上所有
51、k(n,ti)中最小的一个，因此，中最小的一个，因此，h*(n)就是从就是从n到目到目标节点最小代价路径的代价，而且从标节点最小代价路径的代价，而且从n到目标节到目标节点能够获得点能够获得h*(n)的任一路径就是一条从的任一路径就是一条从n到某个到某个目标节点的最佳路径目标节点的最佳路径(对于任何不能到达目标节对于任何不能到达目标节点的节点点的节点n，函数，函数h*没有定义没有定义)。庶羡海惮韩立淑钙遗己然属茎哎霞嫂杜碉渴喊醚循薛冠狈蘸凌婆减捍蔼禁人工智能原理人工智能原理49通常我们感兴趣的是想知道从已知起始节点通常我们感兴趣的是想知道从已知起始节点S到到任意节点任意节点n的一条最佳路径的代价
52、的一条最佳路径的代价k(S,n)。为此，。为此，引进一个新函数引进一个新函数g*，这将使我们的记号得到某些，这将使我们的记号得到某些简化简化。对所有从。对所有从S开始可达到开始可达到n的路径来说，函数的路径来说，函数g*定义为定义为g*(n)=k(S,n)其次，我们定义函数其次，我们定义函数f*，使得在任一节点，使得在任一节点n上其函上其函数值数值f*(n)就是从节点就是从节点S到节点到节点n的一条最佳路径的的一条最佳路径的实际代价实际代价加上从节点加上从节点n到某目标节点的一条到某目标节点的一条最佳最佳路径的代价之和，即路径的代价之和，即 f*(n)=g*(n)+ h*(n)侣一让吧弹溪烈苯
53、星籽灸善戌畔伐杜厄氏根纵瓜导姿贞寅口措权趟埋研龚人工智能原理人工智能原理50因而因而f*(n)值就是从值就是从S开始约束通过节点开始约束通过节点n的一条最佳路径的一条最佳路径的代价，而的代价，而f*(S)=h*(S)是一条从是一条从S到某个目标节点中间无到某个目标节点中间无约束的一条最佳路径的代价。约束的一条最佳路径的代价。我们希望估价函数我们希望估价函数f是是f*的一个估计，此估计可由下式给的一个估计，此估计可由下式给出：出：f(n)=g(n)+h(n)其中：其中：g是是g*的估计；的估计；h是是h*的估计。的估计。对于对于g(n)来说，一个明显的选择就是搜索树中从来说，一个明显的选择就是搜
54、索树中从S到到n这段路这段路径的代价，这一代价可以由从径的代价，这一代价可以由从n到到S寻找指针时，把所遇寻找指针时，把所遇到的各段弧线的代价加起来给出到的各段弧线的代价加起来给出(这条路径就是到目前为这条路径就是到目前为止用搜索算法找到的从止用搜索算法找到的从S到到n的最小代价路径的最小代价路径)。这个定义。这个定义包含了包含了g(n)g*(n)。对于对于h*(n)的估计的估计h(n)，它依赖于有关问题的领域的启发信息。，它依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数这种信息可能与八数码难题中的函数W(n)所用的那种信所用的那种信息相似。我们把息相似。我们把h叫做叫做启发
55、函数启发函数。捌载以瞅谰简孤览墟傻视慌贺乡庐彦骇蛔坡战乙戈面伊杯豹遥捞从脊瘟抗人工智能原理人工智能原理51A A算法和算法和A*A*算法的定义算法的定义 定义定义1 在在GRAPHSEARCH过程中，如果第过程中，如果第8步的步的重排重排OPEN表是依据表是依据f(x)=g(x)+h(x)进行的，则称该过程为进行的，则称该过程为A算法算法定义定义2 在在A算法中，如果对所有的算法中，如果对所有的x，h(x)h*(x)成立成立,则称则称h(x)为为h*(x)的下界，它表示某种偏于保守的估计。的下界，它表示某种偏于保守的估计。定义定义3 采用采用h*(x)的下界的下界h(x)为启发函数的为启发函数
56、的A算法，称为算法，称为A*算算法。当法。当h=0时，时，A*算法就变为有序搜索算法。算法就变为有序搜索算法。A*算法是一种有序搜索算法，其特点在于对估价函数的算法是一种有序搜索算法，其特点在于对估价函数的定义定义上。对于一般的有序搜索，总是选择上。对于一般的有序搜索，总是选择f值最小的节点作值最小的节点作为扩展节点。因此，为扩展节点。因此，f是根据需要找到一条最小代价路径的是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点观点来估算节点的，所以，可考虑每个节点n的估价函数值的估价函数值为两个分量：从起始节点到节点为两个分量：从起始节点到节点n的代价以及从节点的代价以及从节
57、点n到达到达目标节点的代价。目标节点的代价。碟掀坪樊驼挣赘新工俭麓稼贸憨梦挤雁泣昼蚊舟览受忠抒粮柠峪杀悦癌矢人工智能原理人工智能原理52A*算法算法(1) 把把S放入放入OPEN表，记表，记f=h，令，令CLOSED为空表。为空表。(2) 重复下列过程，直至找到目标节点止。若重复下列过程，直至找到目标节点止。若OPEN为为空表，则宣告失败。空表，则宣告失败。(3) 选取选取OPEN表中未设置过的具有最小表中未设置过的具有最小f值的节点为最值的节点为最佳节点佳节点BESTNODE，并把它放入，并把它放入CLOSED表。表。(4) 若若BESTNODE为一目标节点，则成功求得一解。为一目标节点，则
58、成功求得一解。(5) 若若BESTNODE不是目标节点，则扩展之，产生后不是目标节点，则扩展之，产生后继节点继节点SUCCSSOR。恒埠甜课圾燥淆烛规篱拨腆眼疥雅掘直锄柒蓄贱重堡缔袱倒属烦撞俩内甚人工智能原理人工智能原理53(6) 对每个对每个SUCCSSOR进行下列过程：进行下列过程： (a) 建立从建立从SUCCSSOR返回返回BESTNODE的指针。的指针。 (b) 计算计算g(SUC)=g(BES)+g(BES, SUC)。 (c) 如果如果SUCCSSOROPEN，则称此节点为，则称此节点为OLD，并把它添至，并把它添至BESTNODE的后继节点表中。的后继节点表中。 (d) 比较新
59、旧路径代价。如果比较新旧路径代价。如果g(SUC)g(OLD),则则重新确定重新确定OLD的父辈节点为的父辈节点为BESTNODE，记下较小，记下较小代价代价g(OLD),并修正并修正f(OLD)值。值。 (e) 若至若至OLD节点的代价较低或一样，则停止扩节点的代价较低或一样，则停止扩展节点展节点 (f) 若若SUCCSSOR不在不在CLOSE表中，则看其是否表中，则看其是否在在CLOSED表中。表中。 (g) 若若SUCCSSOR在在CLOSE表中，则转向表中，则转向c。 (h) 若若SUCCSSOR既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，则把它放入表中，则把它放入O
60、PEN表中，并添入表中，并添入BESTNODE后裔表，然后转向后裔表，然后转向(7) (i) 计算计算f值。值。(7) GO LOOP痞于浴家召陋超殃锣祈韩阀罪置轰尖鸡褒兑蔚挖涧扩瞅巨阮鳖伤翼桑兵捍人工智能原理人工智能原理54A*算算法法框框图图昏悉答声章齿犀婶溪百诚氏乐盗渝冯浆限鸡窝编葬威舒剁锅锗搓醇捎袒渤人工智能原理人工智能原理55双向搜索双向搜索 双向搜索指从初始状态开始的正向搜索到从目标双向搜索指从初始状态开始的正向搜索到从目标状态开始的逆向搜索同时进行，直至这两条路径状态开始的逆向搜索同时进行，直至这两条路径在中途某处相交为止，正向推理是规则左边的状在中途某处相交为止，正向推理是规则左边的状态与现有状态相匹配，而右边的状态用于生成新态与现有状态相匹配，而右边的状态用于生成新的节点，直至达到目标节点为止。的节点，直至达到目标节点为止。米劝诧纤辛经较砸褪塘冲叶深隆编叛爹货碘怀截佳始帝伸趴丧惰膛母筷拉人工智能原理人工智能原理56
