《人工智能》搜索技术1课件

第四章搜索技术状态空间法问题归约法博弈树搜索局部搜索1编辑pptHowtofindthebestpathingame?2编辑ppt迷宫问题s-----ssssss-----s-----s-----ss-----s-----s-----ssssssss-----s-----s-----s-----sS0Sg3编辑ppt搜索的挑战—组合爆炸魔方问题博弈问题皇后问题行商问题排课问题（调度问题）背包问题…………4编辑ppt数码问题1238456712384567（目标状态）（初始状态）八数码难题（8-puzzleproblem）426183575编辑ppt4.1状态图概念状态图的概念状态图(状态空间图)实际上是一类问题的抽象表示。许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。6编辑ppt农夫过河问题

有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？7编辑ppt农夫过河问题状态空间法表示以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸初态是：（0，0，0，0）终态是：（1，1，1，1）非法中间状态有：（0，0，1，1），（0，1，1，0），（0，1，1，1），

（1，1，0，0），（1，0，0，1），（1，0，0，0）。

8编辑ppt（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）9编辑ppt4.2状态空间法问题的状态空间表示(状态图表示)状态空间的三元组(S,O,G)表示.S:初始状态集合;O:操作集合;G:目标状态集合状态空间的搜索策略(状态图搜索)广度优先搜索,深度优先搜索,启发式搜索10编辑ppt状态空间表示的概念例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState11编辑ppt三数码难题123123123312312312初始棋局目标棋局12编辑ppt1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456713编辑ppt状态图搜索图搜索是指在状态图中寻找目标或路径的搜索。所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径14编辑ppt状态图搜索—相关问题状态选择解的性质：存在、分布、质量搜索策略15编辑ppt图搜索策略图搜索控制策略

一种在状态图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。图搜索涉及两个主要数据结构： open表closed表16编辑pptOPEN表

OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表。节点父节点编号OPEN表open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）17编辑pptCLOSED表

Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表，其初始为空表。

编号节点父节点编号CLOSED表18编辑ppt开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索过程框图是是否否搜索策略即体现在这里19编辑ppt按搜索轨迹分类图式搜索：搜索过程中，搜索路径允许形成回路。树式搜索：搜索过程中，搜索路径不允许形成回路。线式搜索：扩展节点每次只扩展一个节点。SGSG20编辑ppt搜索树的概念一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。

21编辑ppt（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）22编辑ppt由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（blandsearch)和启发式搜索（heuristicsearch）两大类。盲目搜索是无向导搜索。启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。

搜索策略分类23编辑ppt盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。种类：宽度优先搜索深度优先搜索等代价搜索24编辑ppt图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的方法。25编辑ppt宽度优先搜索策略优先搜索状态空间中离初始状态近的节点(状态特点:具有完备性,占用空间搜索算法数据结构:OPEN表:先进先出队列,存放待扩展的节点.

节点(状态)父节点编号(返回指针)CLOSED表:存放已被扩展过的节点.

编号节点父节点编号26编辑ppt开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功

宽度优先算法框图是否是否算法否27编辑ppt宽度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN表中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后, 放入OPEN表尾部,转Step2;28编辑ppt

例子

八数码难题（8-puzzleproblem）

1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。29编辑ppt1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图八数码难题的宽度优先搜索树1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456730编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(1)CLOSED=()678910111213141531编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(2,3)CLOSED=(1)678910111213141532编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(3,4,5)CLOSED=(1,2)678910111213141533编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(4,5,10,11)CLOSED=(1,2,3)678910111213141534编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(5,10,11,6,7)CLOSED=(1,2,3,4)678910111213141535编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(10,11,6,7,8,9)CLOSED=(1,2,3,4,5)678910111213141536编辑ppt宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10)678910111213141537编辑ppt深度优先搜索策略新节点优先扩展,直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.特点:需要深度限制,需要回溯控制,省空间探索算法:数据结构:

OPEN表:后进先出队列,存放待扩展的节点. CLOSED表:存放已被扩展过的节点.除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.38编辑ppt深度优先算法框图算法开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的前端，提供返回节点n的指针失败成功是否是否39编辑ppt深度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后, 放入OPEN表首部,转Step2;40编辑ppt深度优先搜索(Depth-FirstStrategy)新的节点被插入到栈OPEN的前部12345OPEN=(1)CLOSED=()678910111213141541编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部12345OPEN=(2,3)CLOSED=(1)678910111213141542编辑pptDepth-FirstStrategy

新的节点被插入到栈OPEN的前部12345OPEN=(4,5,3)CLOSED=(1,2)678910111213141543编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部12345CLOSED=(1,2,4)67OPEN=(6,7,5,3)8910111213141544编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6)OPEN=(7,5,3)1213141545编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6,7)OPEN=(5,3)1213141546编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7

)OPEN=(8,9,3)1213141547编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8)OPEN=(9,3)1213141548编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9)OPEN=(3)49编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9,3)OPEN=(10,11)50编辑pptDepth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8,9,3,10)12131415OPEN=(12,13,11)51编辑ppt代价树搜索代价树：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。代价树搜索（等代价搜索）

：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。

*若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。52编辑ppt算法使用符号

c(i,j)：把从节点i到其后继节点j的连接弧线代价记为c(i,j)

g(i)：把从起始节点S到任一节点i的路径代价记为g(i).

在搜索树（非循环路径）上，假设g(i)是从起始节点S到节点i的最少路径上的代价。等代价搜索方法以g(i)的递增顺序扩展其节点。53编辑ppt开始把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表是否有后继节点为目标节点？失败成功是是否令g(s)=0S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是否令g(s)=0S是否目标节点？是成功54编辑ppt等代价搜索算法（1）把起始节点Ｓ放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g（S）=0。（2）如果OPEN是个空表，则没有解而失败退出。（3）从OPEN表中选择一个节点i，使其g（i）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点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）步。55编辑ppt宽度优先d=1d=2d=3d=4宽度优先搜索：沿着等长度路径断层进行扩展g1g2g3g4等代价搜索等代价搜索：沿等代价路径断层进行扩展比较宽度优先搜索与等代价搜索56编辑pptADBECFGS34445543搜索树（非循环路径）2SADBDEACEEBBFDFBFCEACGGCGFG3333322244444444444455555557编辑ppt等代价搜索算法SADBDAEEBBFBFCEACGGGFC34455525433478961011CEDFG4511121313134在每一步,选择具有最低累计权值的点进行扩展58编辑ppt启发式搜索盲目搜索的问题：“组合爆炸”利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息.利用启发式信息定义节点的启发函数h(n)特点:深度优先,效率高,无回溯,但不能保证得到最佳解。探索算法:全局择优搜索(最好优先搜索),局部择优搜索数据结构：OPEN表、CLOSED表59编辑ppt启发信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。60编辑ppt重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。应用这种排序过程，需要某些估算节点“希望”的量度。用来估算节点希望程度的量度，叫做估价函数（evaluationfunction），有时也叫作启发函数。一个节点的“希望”（promise）有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；估算全路径的长度或难度（包括此节点）。我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。启发函数61编辑ppt如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：（1）一个节点到目标节点的距离或差异的度量；（2）一个节点处在最佳路径上的概率；（3）或者根据经验的主观打分。

启发函数62编辑ppt八数码难题（8-puzzle）f1(T)=恰好正确地处在目标状态的字码数目:13247658f1=4从实用角度，计算与目标的距离更有实际意义！f2=413247658f2(T)=没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）12384765目标：63编辑pptf3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。该函数给出了一个更好的距离评估f2=1+1+2+2=61324765812384765目标：64编辑ppt启发式搜索算法

启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略:局部择优搜索扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。全局择优搜索在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。65编辑ppt全局择优搜索算法Step1:把初始节点S0放入OPEN表中,计算h(S0);Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,计算每个子节点的函数值h(x),将所有子节点配上指向N的返回指针后放入OPEN表中,再按函数值的升序重新排序OPEN表中的节点,转Step2;66编辑ppt全局择优搜索例子九宫重排问题,定义评价函数; h(n):目标格局与现格局(Sn)相比,位置不同的牌数.初始格局S0目标格局Sg28312314===>84765765

h(S0)=367编辑ppt局部择优搜索算法Step1:把初始节点S0放入OPEN表中,计算h(S0);Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,计算每个子节点的函数值h(x),并将所有子节点按函数值的升序排序后,配上指向N的返回指针放入OPEN表的首部,

转Step2;68编辑ppt局部搜索算法特点：

从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。优点：需要很少的内存经常能在很大或无限的状态空间中找到合理的解69编辑ppt爬山法（Hillclimbing）一种基本的局部启发式搜索方法基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。（启发函数值越小离目标越近）相当于深度优先算法+启发式搜索线式搜索，不能回溯向目标值增加的方向持续移动70编辑ppt启发式搜索:A算法评价函数f(x)=g(x)+h(x)，表示通过节点x的估计代价值。nmSGg(n)g(m)h(n)h(m)比较f(n)和f(m)大小，决定节点搜索顺序，即在OPEN表中的顺序71编辑ppt启发式搜索: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)72编辑ppt启发式搜索:A算法评价函数的一般形式:f(n)=g(n)+h(n) g(n):从S0到Sn的实际代价(搜索的横向因子) h(n):从N到目标节点的估计代价,称为启发函数(搜索的纵向因子);特点:效率高,无回溯,搜索算法OPEN表:存放待扩展的节点. CLOSED表:存放已被扩展过的节点.73编辑ppt启发式搜索:A算法Step1:把附有计算f(S0)初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表中, 并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中,再按函数值的升序重新排序OPEN表中的节点,转Step2;删除重复节点和修改返回指针.74编辑ppt八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）A算法的应用75编辑ppt八数码难题:评价函数简单的评价函数h(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。

初始棋局f值等于0+4=4

12384567（初始状态）76编辑ppt5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+312384567123845673+23+412384567123845673+3

3+4123845674+181324567123845675+05+2八数码难题的搜索树1238460+47577编辑ppt启发式搜索:A*算法评价函数的一般形式: f(n)=g(n)+h(n)且h(n)<=h*(n) g(n),h(n):定义同A算法; h*(n):从N到目标节点的最短路径;称此时的A算法为A*算法.A*算法的特征:A*是可采纳的:只要最短路径存在,就一定能找出.如果有h1(n)<=h2(n)<=h*(n),那么h2比h1展开更少的节点.广度优先搜索是当h(n)=0时的A*算法的特例. 78编辑ppt启发式搜索:A*算法评价函数f(x)=g(x)+h(x)(当h(n)<=h*(n))nSGg(n)=g*(n)h(n)<=h*(n)A*算法要求保守估计：f(n)<=f*(n)79编辑pptA*算法的定义定义1在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2在A算法中，如果对所有的x存在h(x)≤h*(x)（低估）,则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。80编辑ppt具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件1)搜索树上存在着从起始点到终了点的最优路径。2)问题域是有限的。3）所有结点的子结点的搜索代价值>0。4)：h(n)<=h*(n)81编辑ppt为什么A*算法低估h值在A*算法中，对所有的x存在h(x)≤h*(x)（低估)在A*算法中,只有对h值低估才能获得优化的搜索性能82编辑ppt为什么A*算法低估h值举例：SADFBEHCGI11111111111红色值表示真实的剩余代价3212132132154432多估在多估情况下：SADF1+31+51+4B2+2ABC3+1CG4并不是优化路径!83编辑ppt为什么A*算法低估h值举例：32SADFBEHCGI11111111111322111红色值表示真实的剩余代价如果h被低估:SADF1+11+21+310023121低估AB2+0C3+0BG4GCDEE3!2+184编辑pptf1f2f3f4A*A*算法沿f函数进行扩展85编辑ppt启发式搜索算法A*Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组子节点,对这组子节点作如下处 理后,放入OPEN表,按评价函数的升序重新排序 OPEN表,转Step2;删除重复节点和修改返回指针处理.86编辑ppt八数码难题:h1(T)0启发函数为0注意:h3(T)h2(T)h1(T)

h2=413247658h2(T)=没有处在目标状态的字码数目h3=1+1+2+2=613247658h3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。12384765目标：曼哈顿距离87编辑ppt八数码难题举例283164752831647528314765283164752836417528314765231847652831476528316754832641752836417583214765283714

65231847652831457628316754231847652814376528163754h1=00111222223333333333h2=错误数目0+41+51+31+52+32+32+43+33+43+2Notselectedh3=曼哈顿距离0+51+61+41+62+52+32+588编辑pptRobotnavigationCostofonehorizontal/verticalstep=1Costofonediagonalstep=2

f(N)=g(N)+h(N),withh(N)=距离目标位置水平距离和垂直距离之和89编辑pptRobotNavigation90编辑pptRobotNavigation02115877347676328645233365244355465645f(N)=h(N),withh(N)=距离目标位置水平距离和垂直距离之91编辑pptRobotNavigation02115877347676328645233365244355465645f(N)=h(N),withh(N)=距离目标位置水平距离和垂直距离之7092编辑pptRobotNavigationf(N)=g(N)+h(N),withh(N)=距离目标位置水平距离和垂直距离之和021158773476763286452333652443554656457+06+16+18+17+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+1193编辑ppt搜索算法小结树搜索-----盲目搜索----------广度优先搜索---深度优先搜索---有界深度优先---代价树搜索---启发式搜索-----全局择优搜索(最好优先)---局部择优搜索(爬山法)---A算法(基于:f(n)=g(n)+h(n)) A*算法(最佳搜索:h(n)<=h*(n))94编辑ppt复习什么是宽度优先、深度优先、代价树搜索？什么是启发信息、启发函数？什么是盲目搜索和启发式搜索？什么是A算法和A*算法？A*算法有什么特点？

95编辑ppt讨论判断：A*算法中1比目标节点远的节点都不会被展开；2比目标节点近的节点都会被展开；3解是唯一的；4搜索的时间复杂度是指数的。设评价函数为f(N)=g(N)+h(N),怎样才能保证搜索到最优解？设f12(N)=K1g(N)+K2h(N)，讨论K1,K2对搜索结果的影响？如何进一步提高搜索效率？（双向、多起点、非确定…)

96编辑ppt八数码难题（8-puzzleproblem）用A*算法搜索，给出搜索树。12384567（目标状态）12384567（初始状态）课堂练习97编辑ppt1试用A*算法（h(N)=距离目标位置水平距离和垂直距离之和）f(N)=g(N)+h(N)对下图进行搜索作业规定允许动作：左、上、右、下98编辑ppt99编辑ppt作业利用启发式搜索，找出以下问题的解，并说明是否是最优解？（可选） 21612348=>84753765请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？100编辑ppt4.3问题归约法问题归约的概念问题归约的描述:三元组(S0,O,P)表示. S0:初始问题;P:本原问题集合 O:操作算子集;将问题化成若干子问题.问题归约的最终目标:原问题==>本原问题状态空间法是问题归约法的特例.问题归约的与或图表示101编辑ppt与或图表示AAC6C5C4C3C2C1C6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点)3连接弧102编辑ppt节点的可解性判别AC6C5C4C3C2C1m1m2或节点与节点可解节点的判别条件

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

如初始节点可解,搜索成功,结束.删去OPEN中有可解先辈的节点.Step4:N不可扩展:标记不可解节点.如初始节点不可解,

搜索失败,退出.删去OPEN中有不可解先辈的节点.ToStep2.54At2t3t42t1B3105编辑ppt问题归约的例子积分问题的与或树三阶梵塔问题的与或树几何定理证明的与或树106编辑ppt4.4博弈树搜索博弈树的概念博弈:下棋,打牌等一类竞争性智力活动.最简单的是“二人零和,全信息,非偶然”博弈.博弈树:描述博弈过程的与或树.特点:或与节点分层交替出现;搜索空间指数增长,只能前推几步 极大极小过程剪枝技术107编辑ppt

(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失败分币原则:每次要将一堆分为币数不等的两堆.胜负标准:交替分钱币,谁不能再分谁输.分钱币游戏的博弈树结论:?108编辑ppt

(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,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必胜109编辑ppt

钱币为8，9时，结论如何？钱币为10时，结论如何？钱币为x时，结论如何？分钱币游戏思考题110编辑ppt极大极小过程BAIHGFCQPONMLKIEDMAXMIN2813-257-11R25-222-15倒推过程111编辑pptα-β剪枝技术BAIHGFCQPONMLKIEDMAXMIN2813-257R25≤1MAX节点的下界α≥2MIN节点的上界β≤2≥5α剪枝β剪枝112编辑pptα-β剪枝技术MAX节点的倒退值α:取后继节点估值的最大值.

MAX节点的倒推下界值.MIN节点的倒退值β:取后继节估值点的最小值.MIN节点的倒推上界值.α剪枝: 当MIN节点的β值≤祖先MAX节点的α值时,不必展开MIN的其余子节点.β剪枝:当MAX节点的α值≥祖先MIN节点的β值时,不必展开MAX的其余子节点.113编辑ppt讨论局部优先搜索与全局优先搜索的区别是什么?什么是启发式搜索？A算法？A*算法？博弈树有什么特点?利用博弈树分析九枚分钱币游戏的可能结论?---------------------------------------114编辑ppt4.5局部搜索(LocalSearch)*通过在当前解近旁的搜索,不断改善当前解,最终搜索到满足要求的最优解或次优解.一般过程 Step1:初始化.求初始解x0=>当前解x,k=1; Step2:完善解.在x的近旁N(x)中如果有更好解y, 则更新解x:=y,k:=k+1;ToStep2否则,输出x,停止搜索.被用于大规模N-queen,SAT等问题的求解.115编辑ppt局部搜索法初