《人工智能》搜索技术

1、第四章 搜索技术状态空间法问题归约法博弈树搜索局部搜索Howtofindthebestpath in game?迷宫问题题s-ssssss-s-s-ss-s-s-ssssssss-s-s-s-sS0Sg搜索的挑挑战组组合爆炸炸魔方问题题博弈问题题皇后问题题行商问题题排课问题题（调度度问题）背包问题题数码问题题1238456712384567（目标状态）（初始状状态）八数码难难题（8-puzzleproblem）426183574.1状状态图图概念状态图的的概念状态图(状态空空间图)实际上上是一类类问题的的抽象表表示。许多智力力问题(八数码码问题、梵塔问问题、旅旅行商问问题、八八皇后问问题、农夫

2、过河河问题等)。实际问题题（如路路径规划划、定理理证明、演绎推推理、机机器人行行动规划划等）都都可以归归结为在在某一状状态图中中寻找目目标或路路径的问问题。农夫过河河问题有一个农农夫带一一条狼、一只羊羊和一棵棵白菜过过河。如如果没有有农夫看看管，则则狼要吃吃羊，羊羊要吃白白菜。但但是船很很小，只只够农夫夫带一样样东西过过河。问问农夫该该如何解解此难题题？农夫过河河问题状态空间间法表示示以向量（人，狼狼，羊，菜）表表示状态态，其中中每个变变元可取取0或1，取0表示在在左岸（出发点点），取取1表示示在右岸岸初态是：（0，0，0，0）终态是：（1，1，1，1）非法中间间状态有有：（0，0，1，1），

3、（0，1，1，0），（0，1，1，1），（1，1，0，0），（1，0，0，1），（1，0，0，0）。（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）4.2状状态空空间法问题的状态空间间表示(状状态图表表示)状态空间间的三元元组(S,O,G)表示示.S:初始始状态集集合;O:操操作集集合;G:目标标状态集集合状态空间间的搜索索策略(状态图图搜索)广度优先先搜索, 深度度优先搜搜索,启发式搜搜索

4、状态空间间表示的的概念例如下棋棋、迷宫宫及各种种游戏。OriginalStateMiddleStateGoalState三数码难难题123123123312312312初始棋局局目标棋局局1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难难题的宽宽度优先先搜索树树13456123845671238456712384567123845671238456723242526271236782212384

5、567123845671238456712384567123845671238456712384567141516171819202112384567状态图搜搜索图搜索是指在状状态图中中寻找目目标或路路径的搜搜索。所谓搜索，顾名思思义，就就是从初初始节点点出发，沿着与与之相连连的边试试探地前前进，寻寻找目标标节点的的过程(也可以以反向进进行)。问题状态图搜索解解是由初初始状态态到目标标状态的的路径状态图搜搜索相相关问题题状态选择择解的性质质：存在在、分布布、质量量搜索策略略图搜索策策略图搜索控控制策略略一种在状状态图中中寻找路路径的方方法。图中每个节点点对应一一个状态态，每条条连线对对应一个个

6、操作符符。图搜索涉涉及两个个主要数数据结构构：open表closed表OPEN 表OPEN表是一种动动态数据据结构，专门登登记当前前待考查查（待访访问）的的节点，也叫未未扩展节节点表。节点父节点编号OPEN表open表中，每每个节点点信息还还包括指指向父节节点的返返回指针针（即父父节点地地址）CLOSED表表Closed表表是一种种动态数数据结构构，记录录访问过过的节点点，也叫叫已扩展展节点表表 ，其其初始为为空表。编号节点父节点编号CLOSED表表开始把S放入OPEN表OPEN表为空表表？把第一个节节点(n)从OPEN表移至CLOSED表n为目标节节点吗？把n的后继节节点放入入OPEN表的末

7、端端，提供供返回节节点n的指针修改指针针方向重排OPEN表失败成功图搜索过过程框图图是是否否搜索策略略即体现现在这里里按搜索轨轨迹分类类图式搜索索：搜索过过程中，搜索路路径允许许形成回回路。树式搜索索：搜索过过程中，搜索路路径不允允许形成成回路。线式搜索索：扩展节节点每次次只扩展展一个节节点。SGSG搜索树的的概念一个可以以搜索出出某个可可行解的的问题，如“农农夫、白白菜、羊羊、狼”和“八八数码难难题”等等，虽然然从表面面上看上上去和“树”这这种结构构无关，但是整整个搜索索过程中中的可能能试探点点所行成成的搜索索空间总总可以对对应到一一颗搜索树上去。将各类形形式上不不同的搜搜索问题题抽象并并统

8、一成成为搜索索树的形形式，为为算法的的设计与与分析带带来巨大大的方便便。（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）由于搜索索具有探探索性，所以要要提高搜搜索效率率(尽快快地找到到目标节节点)，或要找找最佳路径径(最佳解解)就必必须注意意搜索策策略。对于状态态图搜索索，已经经提出了了许多策策略，它它们大体体可分为为盲目搜索索（blandsearch)和启发式搜搜索（heuristic s

9、earch）两两大类。盲目搜索索是无向导导搜索。启发式搜搜索是有向导导搜索，即利用用启发信信息（函函数）引引导去寻寻找问题题解。搜索策略略分类盲目搜索索盲目搜索索又叫做无无信息搜搜索，一一般只适适用于求求解比较较简单的的问题。种类：宽度优先先搜索深度优先先搜索等代价搜搜索图搜索策策略宽度优先先深度优先先启发式搜搜索一种在图图中寻找找路径的的方法。宽度优先先搜索策策略优先搜索索状态空空间中离离初始状状态近的的节点(状态特点:具具有完备备性,占占用空空间搜索算法法数据结构构:OPEN表:先进先出出队列,存放待扩扩展的节节点.节点(状状态)父父节点点编号(返回指指针)CLOSED表表 :存存放已已被

10、扩展展过的节节点.编号节节点父父节节点编号号开始把S放入OPEN表OPEN表为空表表？把第一个个节点(n)从OPEN表移至CLOSED表是否有后后继节点点为目标节节点？扩展n，把n的后继节节点放入入OPEN表的末端，提供返返回节点点n的指针失败成功宽度优先先算法框框图是否是否 算法否宽度优先先搜索算算法Step1:把把初始节节点S0放入OPEN表中;Step2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN表表中第一一个节点点N放入入CLOSED表中中,并并标以以顺序号号n;Step4:若若目标节节点Sg=N, 则搜搜索成功功,结束束.Step5:若若N不可可扩展,

11、则转转Step2;Step6:扩扩展展N,将将生成成的一组组子节点点配上指指向N的的指针后后,放入OPEN表表尾部, 转Step2;例子八数码难难题（8-puzzleproblem）1238456712384567（目标状态）（初始状状态）规定：将牌移入入空格的的顺序为为：从空空格左边边开始顺顺时针旋旋转。不不许斜向向移动，也不返返回先辈辈节点。从图可见见，要扩扩展26个节点，共生成成26个节点之之后才求求得解（目标节节点）。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671

12、123845671238456712384567123845672345图八数码难难题的宽度优先先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567宽度优先先搜索(Breadth-First Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(1)CLOSED=()6789101112131415宽度优先先搜索(Breadth-Fi

13、rst Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(2,3)CLOSED=(1)6789101112131415宽度优先先搜索(Breadth-First Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(3,4,5)CLOSED=(1,2)6789101112131415宽度优先先搜索(Breadth-First Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(4,5,10,11)CLOSED=(1,2,3 )6789101112131415宽度优先先搜索(Breadth-First Strategy)新的

14、节点点被插入入到栈OPEN的后部12345OPEN=(5,10,11,6,7)CLOSED=(1,2,3,4)6789101112131415宽度优先先搜索(Breadth-First Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(10,11,6,7,8,9)CLOSED=(1,2,3,4,5)6789101112131415宽度优先先搜索(Breadth-First Strategy)新的节点点被插入入到栈OPEN的后部12345OPEN=(11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10)6789101112131415深度优先先搜索

15、策策略新节点优优先扩展展,直直到达到到一定的的深度限限制.若若找不到到目标或或无法在在扩展时时,回溯溯到另一一节点继继续扩展展.特点:需需要深深度限制制,需需要回溯溯控制, 省空空间探索算法法:数据结构构:OPEN表:后进先出出队列,存放待待扩展的的节点.CLOSED表表 :存存放已已被扩展展过的节节点.除扩展后后的子节节点应放放入到OPEN表的首首部以外外,与宽宽度优先先算法一一样.深度优先先算法框框图 算法开始把S放入OPEN表OPEN表为空表表？把第一个个节点(n)从OPEN表移至CLOSED表是否有后后继节点点为目标节节点？扩展n，把n的后继节节点放入入OPEN表的前端，提供返返回节点

16、点n的指针失败成功是否是否深度优先先搜索算算法Step1:把把初始节节点S0放入OPEN表中;Step2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN中中第一个个节点N放入CLOSED表表中中,并并标以顺顺序号n;Step4:若若目标节节点Sg=N, 则搜搜索成功功,结束束.Step5:若若N不可可扩展, 则转转Step2;Step6:扩扩展展N,将将生成成的一组组子节点点配上指指向N的的指针后后,放入OPEN表表首部, 转Step2;深度优先先搜索(Depth-FirstStrategy)新的节点点被插入入到栈OPEN的前部12345OPEN= (1)CLOSED

17、=()6789101112131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部12345OPEN = (2, 3)CLOSED=(1 )6789101112131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部12345OPEN = (4, 5, 3)CLOSED=(1,2)6789101112131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部12345CLOSED=(1,2,4)67OPEN =(6,7,5,3)89101112131415Depth-FirstStrategy新的节点点被插

18、入入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6 )OPEN =(7, 5, 3)12131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6,7)OPEN =(5, 3)12131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7)OPEN =(8,9,3)12131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部1234567891011CLOSED=

19、(1,2,4,5,6,7,8)OPEN =(9, 3)12131415Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7, 8,9)OPEN =(3)Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9,3)OPEN =(10,11)Depth-FirstStrategy新的节点点被插入入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8,9,3,

20、10)12131415OPEN =(12,13,11)代价树搜搜索代价树：搜索树树中每条条连接弧弧线上的的有关代代价,表示时间间、距离离等花费费。代价树搜搜索（等等代价搜搜索）：是宽度优优先搜索索的一种种推广，不是沿沿着等长长度路径径断层进进行扩展展，而是是沿着等等代价路路径断层层进行扩扩展。*若所有有连接弧弧线具有有相等代代价，则则简化为为宽度优优先搜索索算法。算法使用用符号c(i,j)：把从节点点i到其后继继节点j的连接弧弧线代价价记为c(i,j)g(i)：把从起始始节点S到任一节节点i的路径代代价记为为g(i).在搜索树树（非循环环路径）上，假设设g(i)是从起始始节点S到节点i的最少路

21、路径上的的代价。等代价搜搜索方法法以g(i)的递增顺顺序扩展展其节点点。开始把S放入OPEN表OPEN表为空表表？把具有最最小g(i)值的节点点i从OPEN表移至CLOSED表是否有后后继节点点为目标节节点？失败成功等代价搜搜索算法法框图是否是否令g(s)=0S是否目标标节点？是成功否开始把S放入OPEN表OPEN表为空表表？把具有最最小g(i)值的节点点i从OPEN表移至CLOSED表是否有后后继节点点为目标节节点？失败成功是是否令g(s)=0S是否目标标节点？是成功开始把S放入OPEN表OPEN表为空表表？把具有最最小g(i)值的节点点i从OPEN表移至CLOSED表是否有后后继节点点为目

22、标节节点？失败成功是是否令g(s)=0S是否目标标节点？是成功扩展i，计算其其后继节节点j的g(j)，并把后后继节点点放入OPEN表开始把S放入OPEN表OPEN表为空表表？把具有最最小g(i)值的节点点i从OPEN表移至CLOSED表是否有后后继节点点为目标节节点？失败成功是是否令g(s)=0S是否目标标节点？是成功等代价搜搜索算法法（1）把把起始始节点放到未未扩展节节点表OPEN中。如如果此起起始节点点为一目目标节点点，则求求得一个个解；否否则令g（S）=0。（2）如如果OPEN是个空空表，则则没有解解而失败败退出。（3）从从OPEN表表中选选择一个个节点i，使其其g（i）为最最小。如如果

23、有几几个节点点都合格格，那么么就要选选择一个个目标节节点作为为节点i（要要是有目目标节点点的话）；否则则，就从从中选一一个作为为节点i。把节节点i从从OPEN表移移至扩展展节点表表CLOSED中。（4）如如果节节点i为为目标节节点，则则求得一一个解。（5）扩扩展节节点i。如果没没有后继继节点，则转向向第（2）步。（6）对对于节节点i的的每个后后继节点点j，计计算g（j）=g（i）+c（i,j），并把所有有后继节节点j放放进OPEN表表。提供供回到节节点i的的指针。（7）转转向第第（2）步。宽度优先d = 1d = 2d = 3d = 4宽度优先搜索：沿着等长度路径断层进行扩展g1g2g3g4等

24、代价搜索等代价搜搜索：沿沿等代价路路径断层进行行扩展比较宽度度优先搜搜索与等等代价搜搜索ADBECFGS34445543搜索树（非循环路径）2SADBDEACEEBBFDFBFCEACGGCGFG33333222444444444444555555等代价搜搜索算法法SADBDAEEBBFBFCEACGGGFC34455525433478961011CEDFG4511121313134在每一步步,选选择具有有最低累累计权值值的点进进行扩展展启发式搜搜索盲目搜索索的问题题：“组合爆爆炸”利用问题题的某些些控制信信息(如如解的特特征)来来引导搜搜索.这这种控制制信息称称为搜索索的启发信息息.利用启发

25、发式信息息定义节节点的启发函数数h(n)特点:深深度优优先,效效率高高,无无回溯, 但不不能保证证得到最最佳解。探索算法法:全局择优优搜索(最好优优先搜索索),局部择优优搜索数据结构构：OPEN表表 、CLOSED表表启发信息息启发式搜搜索就是是利用启启发性信信息进行行制导的的搜索。启发性信信息就是是有利于于尽快找找到问题题之解的的信息。按其用途途划分，启发性性信息一一般可分分为以下下三类：(1)用于扩展展节点的的选择，即用于于决定应应先扩展展哪一个个节点，以免盲盲目扩展展。(2)用于生成成节点的的选择，即用于于决定应应生成哪哪些后续续节点，以免盲盲目地生生成过多多无用节节点。(3)用于删除除

26、节点的的选择，即用于于决定应应删除哪哪些无用用节点，以免造造成进一一步的时时空浪费费。重排OPEN表表，使搜搜索沿某某个被认认为最有有希望的的路径扩扩展。应用这种种排序过过程，需需要某些些估算节节点“希望”的量度度。用来估算算节点希希望程度度的量度度，叫做做估价函数数（evaluationfunction），有时时也叫作作启发函函数。一个节点点的“希希望”（promise）有有几种不不同的的定义方方法。在状态空空间问题题中，一一种方法法是估算算目标节节点到此此节点的的距离；估算全路路径的长长度或难难度（包包括此节节点）。我们用符符号f来来标记估估价函数数，用f（n）表示节点点n的估估价函数数值

27、。启发函数数如何定义义一个估估价（启启发）函函数呢？估价（启发）函数并并无固定定的模式式，需要要具体问问题具体体分析。通常可可以参考考的思路路有：（1）一一个节节点到目目标节点点的距离离或差异异的度量量；（2）一一个节点点处在最最佳路径径上的概概率；（3）或或者根据据经验的的主观打打分。启发函数数八数码难难题（8-puzzle）f1(T)= 恰好好正确地地处在目目标状态态的字码码数目:13247658f1= 4从实用角角度，计计算与目目标的距距离更有有实际意意义！f2= 413247658f2(T) =没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）12384765目标：f

28、3(T)= 不在在目标位位置的字字码距离离目标位位置水平平距离和和垂直距距离之和和。该函数给给出了一一个更好好的距离离评估f2= 1+1 +2+ 2=61324765812384765目标：启发式搜搜索算法法启发式搜搜索要用用启发函函数来导导航，其其搜索算算法就要要在状态态图一般般搜索算算法基础础上再增增加启发发函数值值的计算算与传播播过程，并且由由启发函函数值来来确定节节点的扩扩展顺序序。两种种策略:局部择优优搜索扩展节点点N后仅仅对N的的子节点点按启发发函数值值大小以以升序排排序，再再将它们们依次放放入OPEN表表的首部。全局择优优搜索在OPEN表中中保留所所有已生生成而未未考察的的节点，

29、并用启启发函数数h(x)对它它们全部部进行估估价，从从中选出出最优节节点进行行扩展，而不管管这个节节点出现现在搜索索树的什什么地方方。全局择优优搜索算算法Step1:把把初始节节点S0放入OPEN表中,计算h(S0);Step2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN中中第一个个节点N放入CLOSED表表中中,并并标以顺顺序编号号n;Step4:若若目标节节点Sg=N, 则搜搜索成功功,结束束.Step5:若若N不可可扩展, 则转转Step2;Step6:扩扩展展N,计计算每个个子节点点的函数数值h(x),将所有有子节点点配上指指向N的的返回指指针后放放入OP

30、EN表表中,再再按函数值值的升序序重新排排序OPEN表表中的节节点,转 Step2;全局择优优搜索例例子九宫重排排问题, 定义义评价函函数;h(n):目标标格局与与现格局局(Sn)相比比,位置置不同的的牌数.初始格局局S0目目标格局局Sg28312314=84765765h(S0)= 3局部择优优搜索算算法Step1:把把初始节节点S0放入OPEN表中,计算h(S0);Step2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN中中第一个个节点N放入CLOSED表表中中,并并标以顺顺序编号号n;Step4:若若目标节节点Sg=N, 则搜搜索成功功,结束束.Step5:若

31、若N不可可扩展, 则转转Step2;Step6:扩扩展展N,计计算每个个子节点点的函数数值h(x),并将所所有子节节点按函数值的的升序排排序后,配上指向向N的返返回指针针放入OPEN表的首首部,转 Step2;局部搜索索算法特点：从单独的的一个当当前状态态出发，通常只只移动到到与之相相邻的状状态，并并且不保保留解的的路径。优点：需要很少少的内存存经常能在在很大或或无限的的状态空空间中找找到合理理的解爬山法（Hillclimbing）一种基本本的局部部启发式式搜索方方法基本算法法：扩展展节点N后仅对对N的子子节点按按启发函函数值大大小以升升序排序序，再将将选择启启发函数数值最小的节节点放入OPE

32、N表表的首部。（启发函数数值越小小离目标标越近）相当于深深度优先先算法+启发式式搜索线式搜索索，不能回回溯向目标值值增加的的方向持持续移动动启发式搜搜索:A算法评价函数数f(x) =g(x)+ h(x)，表示通通过节点点x的估估计代价价值。nmSGg(n)g(m)h(n)h(m)比较f(n)和f(m)大小，决决定节点点搜索顺顺序，即即在OPEN表中的顺顺序启发式搜搜索:A算法评价函数数f(x) =g(x)+ h(x)当f(x) =g(x)时时，为宽度优优先搜索索当f(x) =1/g(x)时，为深度优优先搜索索当f(x) =h(x)时时，为全局优优先搜索索nmSGg(n)g(m)h(n)h(m)

33、启发式搜搜索:A算法评价函数数的一般般形式:f(n) =g(n)+ h(n)g(n):从S0到Sn的实实际代价价(搜索索的横向向因子)h(n):从N到目标标节点的的估计代代价,称称为启发函数数(搜索的的纵向因因子);特点:效效率高高,无无回溯,搜索算法法OPEN表: 存放放待扩展展的节点点.CLOSED表表 :存存放已已被扩展展过的节节点.启发式搜搜索:A算法Step1:把把附有计计算f(S0)初始节节点S0放入OPEN表中;Step2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN中中第一个个节点N放入CLOSED表表中,并标以顺顺序编号号n;Step4:若若目标节

34、节点Sg=N, 则搜搜索成功功,结束束.Step5:若若N不可可扩展, 则转转Step2;Step6:扩扩展展N,生生成一一组附有有f(x)的子子节点,作完以以下处理理后,将将余下子子节点配配上指向向N的返返回指针针后放入入OPEN表中中,再再按函数值值的升序序重新排排序OPEN表表中的节节点,转 Step2;删除重复复节点和和修改返返回指针针.八数码难难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）A算法的应应用八数码难难题:评价函数数简单的评评价函数数h(n)=d(n)+W(n)其中：d(n)是搜索索树中节节点n的的深度；W(n)用来来计算对对

35、应于节节点n的的数据库库中错放放的棋子子个数。初始棋局局f值等于0+4=412384567（初始状态）5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+312384567123845673+2 3+412384567123845673+3 3+4123845674+181324567123845675+05+2八数码难难题的搜搜索树1238460+475启发式搜搜索:A*算法法评价函数数的一般般形式:f(n) =g(n)+ h(n)且且h(n)=h*(n)g(n),h(n):定义同同A算法;h*(n)

36、:从从N到目目标节点点的最短短路径;称此时的的A算法法为A*算法法.A*算法法的特征征:A*是可可采纳的的:只要最短短路径存存在,就就一定能能找出.如果有h1(n)=h2(n)=h*(n), 那么么h2比比h1展展开更少少的节点点.广度优先先搜索是是当h(n)=0时的的A*算算法的特特例.启发式搜搜索:A*算法法评价函数数f(x) =g(x)+ h(x)( 当h(n) = h*(n) )nSGg(n)=g*(n)h(n) = h*(n)A*算法要求求保守估估计：f(n)0。4)：h(n)=h*(n)为什么A*算法法低估h值在A*算法中，对所有有的x存在h(x)h*(x)（低估)在A*算法中,只

37、有对h值低估估才能获获得优化化的搜索索性能为什么A*算法法低估h值举例：SADFBEHCGI11111111111红色值表示真实的剩余代价3212132132154432多估在多估情情况下：SADF1+31+51+4B2+2ABC3+1CG4并不是优化路径!为什么A*算法法低估h值举例：32SADFBEHCGI11111111111322111红色值表示真实的剩余代价如果h被被低估:SADF1+11+21+310023121低估AB2+0C3+0BG4GCDEE3 !2+1f1f2f3f4A*A*算法沿f函数进行扩展启发式搜搜索算法法A*Step1:把把初始节节点S0放入OPEN表中;Step

38、2:若若OPEN表为为空,则则搜索失失败,退退出.Step3:移移出OPEN中中第一个个节点N放入CLOSED表表中中,并并标以顺顺序号n;Step4:若若目标节节点Sg=N, 则搜搜索成功功,结束束.Step5:若若N不可可扩展, 则转转Step2;Step6:扩扩展展N,生生成一一组子节节点,对对这组组子节点点作如下下处理理后, 放入入OPEN表,按评价函函数的升升序重新新排序OPEN表,转 Step2;删除重复复节点和和修改返返回指针针处理.八数码难难题:h1(T) 0启发函数数为0注意:h3(T)h2(T)h1(T)h2= 413247658h2(T) =没有处在目标状态的字码数目h3

39、= 1 + 1 + 2 + 2 = 613247658h3(T) =不在目标位置的字码距离目标位置水平距离和垂直距离之和。12384765目标：曼哈顿距距离八数码难难题举例例2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 7 5 4 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 8 31 4 57 6 2 8 31

40、67 5 42 3 1 8 47 6 52 8 1 4 37 6 52 8 1 6 37 5 4h1 = 00111222223333333333h2 = 错误数目0+41+51+31+52+32+32+43+33+43+2Notselectedh3 =曼哈顿距离0+51+61+41+62+52+32+5RobotnavigationCost of onehorizontal/vertical step=1Cost of onediagonalstep =2f(N) =g(N)+ h(N), withh(N)=距离目标标位置水水平距离离和垂直直距离之之和RobotNavigationRobot

41、Navigation02115877347676328645233365244355465645f(N) =h(N),withh(N) =距离目标标位置水水平距离离和垂直直距离之之RobotNavigation02115877347676328645233365244355465645f(N) =h(N),withh(N) =距离目标标位置水水平距离离和垂直直距离之之70RobotNavigationf(N) =g(N)+h(N),with h(N)=距离目标标位置水水平距离离和垂直直距离之之和021158773476763286452333652443554656457+06+16+18+1

42、7+07+26+17+26+18+17+28+37+26+36+35+45+44+54+53+63+62+78+37+47+46+55+66+35+62+73+84+75+64+73+84+73+83+82+92+93+102+93+82+91+101+100+11搜索算法法小结树搜索-盲目目搜索-广度优优先搜索索-深深度优先先搜索-有有界深度度优先-代代价树搜搜索-启启发式搜搜索-全局择择优搜索索(最好好优先)-局局部择优优搜索(爬山法法)-A算法( 基于于:f(n)=g(n)+h(n)A*算法法(最佳佳搜索: h(n)84753765请针对TSP问问题，提提出启发发式搜索索策略，并对搜搜索

43、效率率进行分分析？4.3问问题归归约法问题归约约的概念念问题归约约的描述述:三三元组(S0, O, P)表示.S0:初初始问题题;P:本原问题题集合O:操作作算子集集;将问问题化成成若干子子问题.问题归约约的最终终目标:原原问题= 本原原问题状态空间间法是问问题归约约法的特特例.问题归约约的与或或图表示示与或图表表示AAC6C5C4C3C2C1C6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点点)3连接弧弧节点的可可解性判判别AC6C5C4C3C2C1m1m2或节点与节点可解节点点的判别别条件叶节点可可解或节点可可解当且且仅当至至少有一一个子节节点可解解.与节点可可解当且且仅当所

44、所有子节节点都可可解.不可解节节点的判判别条件件没有子节节点的非非终止节节点或节点不不可解当当且仅当当所有子子节点不不可解.与节点不不可解当当且仅当当至少有有一个子子节点不不可解.与或图的的搜索AC6C5C4C3C2C1m1m2或节点与节点解图求解与或或图问题题就是在在与或图图中搜索索解图(或解树)的问题题.解图是原原与或图图的一个个子图(与图)搜索策略略:无信信息搜索索与启发发式搜索索搜索过程程:标标记初始始节点为为可解节节点(成成功)或或不可解解节点(失败)的过程程.搜索算法法:与或树的的搜索算算法1Step1:S0= OPEN表表Step2:OPEN-N-CLOSED(n)Step3:如

45、如N可可扩展:扩展N=OPEN标记可解解节点=CLOSED如初始节节点可解解,搜索索成功,结束.删去OPEN中中有可解解先辈的的节点.Step4:N不可可扩展:标记不可可解节点点.如初始始节点不不可解,搜索失败败,退出出.删去OPEN中中有不可可解先辈辈的节点点.ToStep2.54At2t3t42t1B3问题归约约的例子子积分问题题的与或或树三阶梵塔塔问题的的与或树树几何定理理证明的的与或树树4.4博博弈树树搜索博弈树的的概念博弈:下下棋,打打牌等等一类竞竞争性智智力活动动.最简简单的是是“二人零和和,全信信息,非非偶然”博弈.博弈树:描述博博弈过程程的与或或树.特点:或或与节节点分层层交替

46、出出现;搜索空间间指数增增长,只只能前推推几步极大极小小过程剪枝技术术(7,min)(6,1,max)(5,2,max)(4,3,max)(5,1,1,min)(4,2,1min)(3,2,2,min)(3,3,1,min)(4,1,1,1,max)(3,2,1,1,mix)(2,2,2,1,max)max失失败(3,1,1,1,1,min)(2,2,1,1,1,min)min失失败(2,1,1,1,1,1,max)max失失败分币原则则:每次次要将一一堆分为为币数不不等的两两堆.胜负标准准:交替替分钱币币,谁不不能再分分谁输.分钱币游游戏的博博弈树结论:?(7,min)(6,1,max)(5

47、,2,max)(4,3,max)(5,1,1,min)(4,2,1min)(3,2,2,min)(3,3,1,min)(4,1,1,1,max)(3,2,1,1,max)(2,2,2,1,max)max失败(3,1,1,1,1,min)(2,2,1,1,1,min)min失失败(2,1,1,1,1,1,max)max失失败.max可可解节节点min可解节点点分钱币游游戏的博博弈树结论:max必必胜钱币为8，9时时，结论论如何？钱币为10时时，结论如如何？钱币为x时时，结论论如何？分钱币游游戏思考考题极大极小小过程BAIHGFCQPONMLKIEDMAXMIN2813-257-11R25-222

48、-15倒推过程程-剪枝技术术BAIHGFCQPONMLKIEDMAXMIN2813-257R25 1MAX节点的下下界2MIN节点的上上界25剪枝剪枝-剪枝技术术MAX节点的倒退值:取后继节节点估值值的最大值.MAX节节点的倒推下界界值.MIN节点的倒退值:取后继节节估值点点的最小值.MIN节节点的倒推上界界值.剪枝:当MIN节点的值祖先MAX节点的值时,不必展开开MIN的其余子子节点.剪枝:当MAX节点的值祖先MIN节点的值时,不必展开开MAX的其余子子节点.讨论局部优先先搜索与与全局优优先搜索索的区别别是什么么?什么是启启发式搜搜索？A算法？A*算算法？博弈树有有什么特特点?利用博弈弈树分析析九枚分分钱币游游戏的可可能结论论?-4.5局局部搜搜索(LocalSearch)*通过在当当前解近近旁的搜搜索,不断改善善当前解解,最终搜索索到满足足要求的的最优解解或次优优解.一般过程程Step1:初始化. 求初初始解x0=当前