《人工智能》搜索技术.ppt

第四章 搜索技术状态空间法问题归约法博弈树搜索局部搜索How to find the best path in game?迷宫问题s-s s s s s s-s-s-ss-s-s-s s s s s s s s-s-s-s-s S0Sg搜索的挑战组合爆炸魔方问题博弈问题皇后问题行商问题排课问题（调度问题）背包问题 数码问题1238456712384567（目标状态）（初始状态）八数码难题（8-puzzle problem）426183574.1 状态图概念状态图的概念 状态图(状态空间图)实际上是一类问题的抽象表示。许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。农夫过河问题 有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？农夫过河问题状态空间法表示以向量（人，狼，羊，菜）表示状态，其中每个变元可取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）。（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:目标状态集合状态空间的搜索策略(状态图搜索)广度优先搜索,深度优先搜索,启发式搜索状态空间表示的概念例如下棋、迷宫及各种游戏。OriginalState三数码难题初始棋局目标棋局1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567状态图搜索n图搜索是指在状态图中寻找目标或路径的搜索。n所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径状态图搜索相关问题n状态选择n解的性质：存在、分布、质量n搜索策略图搜索策略 图搜索控制策略一种在状态图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。图搜索涉及两个主要数据结构：open表 closed表OPEN 表 OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表。节点节点父节点编号父节点编号OPEN表表open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）CLOSED 表表 Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表，其初始为空表。编号编号节点节点父节点编号父节点编号CLOSED表表开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功 图搜索过程框图图搜索过程框图是是是是否否否否搜索策略即搜索策略即体现在这里体现在这里按搜索轨迹分类图式搜索图式搜索：搜索过程中，搜索路径允许形成回路。树式搜索树式搜索：搜索过程中，搜索路径不允许形成回路。线式搜索线式搜索：扩展节点每次只扩展一个节点。SGSG搜索树的概念 一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。（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）由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（bland search)和启发式搜索（heuristic search）两大类。盲目搜索是无向导搜索。启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。搜索策略分类搜索策略分类盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。种类：宽度优先搜索深度优先搜索等代价搜索图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的方法。宽度优先搜索策略优先搜索状态空间中离初始状态近的节点(状态特点:具有完备性,占用空间搜索算法 数据结构:OPEN表:先进先出队列先进先出队列,存放待扩展的节点.节点(状态)父节点编号(返回指针)CLOSED表:存放已被扩展过的节点.编号 节点 父节点编号开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的末端末端，提供返回节点，提供返回节点n的指针的指针失败失败成功成功 宽度优先算法框图宽度优先算法框图是是否否是是否否v 算法否否宽度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN表中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入放入OPEN表尾部表尾部,转 Step2;例子例子八数码难题（八数码难题（8-puzzle problem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(1)CLOSED=()6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(2,3)CLOSED=(1)6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(3,4,5)CLOSED=(1,2)6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(4,5,10,11)CLOSED=(1,2,3)6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(5,10,11,6,7)CLOSED=(1,2,3,4)6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(10,11,6,7,8,9)CLOSED=(1,2,3,4,5)6789101112131415宽度优先搜索宽度优先搜索(Breadth-First Strategy)Breadth-First Strategy)新的节点被插入到栈OPEN的后部12345OPEN=(11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10)6789101112131415深度优先搜索策略新节点优先扩展,直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.特点:需要深度限制,需要回溯控制,省空间探索算法:数据结构:OPEN表:后进先出队列后进先出队列,存放待扩展的节点.CLOSED表:存放已被扩展过的节点.除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.深度优先算法框图深度优先算法框图v 算法开始开始把把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不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入放入OPEN表首部表首部,转 Step2;深度优先搜索深度优先搜索(Depth-First Strategy)Depth-First Strategy)新的节点被插入到栈OPEN的前部12345OPEN=(1)CLOSED=()6789101112131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部12345OPEN=(2,3)CLOSED=(1)6789101112131415Depth-First StrategyDepth-First Strategy 新的节点被插入到栈OPEN的前部12345OPEN=(4,5,3)CLOSED=(1,2)6789101112131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部12345CLOSED=(1,2,4)67OPEN=(6,7,5,3)89101112131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6)OPEN=(7,5,3)12131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6,7)OPEN=(5,3)12131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7)OPEN=(8,9,3)12131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8)OPEN=(9,3)12131415Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9)OPEN=(3)Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9,3)OPEN=(10,11)Depth-First StrategyDepth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8,9,3,10)12131415OPEN=(12,13,11)代价树搜索代价树：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。代价树搜索（等代价搜索）：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。*若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。算法使用符号n c(i,j)：把从节点把从节点i i到其后继节点到其后继节点j j的连接弧线代价记为的连接弧线代价记为c(i,j)c(i,j)n g(i)：把从起始节点把从起始节点S S到任一节点到任一节点i i的路径代价记为的路径代价记为g(i).g(i).n 在搜索树在搜索树（非循环路径）（非循环路径）上，假设上，假设g(i)g(i)是从起始节点是从起始节点S S到节点到节点i i的最少路径上的代价。的最少路径上的代价。n 等代价搜索方法以等代价搜索方法以g(i)g(i)的递增顺序扩展其节点。的递增顺序扩展其节点。开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功否否开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功扩展扩展i i，计算其后继节点，计算其后继节点j j的的g(j)g(j)，并，并把后继节点放入把后继节点放入OPENOPEN表表开始把把S S放入放入OPENOPEN表表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点是否有后继节点为目标节点？为目标节点？失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功等代价搜索算法（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）步。）步。宽度优先宽度优先d=1d=1d=2d=2d=3d=3d=4d=4宽度优先搜索：宽度优先搜索：宽度优先搜索：宽度优先搜索：沿着等长度沿着等长度路径断层进行扩展路径断层进行扩展g1g1g2g2g3g3g4g4等代价等代价搜索搜索等代价搜索：沿等代价搜索：沿等代价搜索：沿等代价搜索：沿等代价路径等代价路径断层进行扩展断层进行扩展比较宽度优先搜索与等代价搜索比较宽度优先搜索与等代价搜索A AD DB BE EC CF FG GS S3 34 44 44 45 55 54 43 3搜索树（非循环路径）2 2S SA AD DB BD DE EA AC CE EE EB BB BF FD DF FB BF FC CE EA AC CG GG GC CG GF FG G3 33 33 33 33 32 22 22 24 44 44 44 44 44 44 44 44 44 44 44 45 55 55 55 55 55 5等代价搜索算法等代价搜索算法S SA AD DB BD DA AE EE EB BB BF FB BF FC CE EA AC CG GG GG GF FC C3 34 44 45 55 55 52 25 54 43 33 34 47 78 89 96 610101111C CE ED DF FG G4 45 5111112121313131313134 4 在每一步,选择具有最低累计权值的点进行扩展启发式搜索盲目搜索的问题：“组合爆炸”利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息启发信息.利用启发式信息定义节点的启发函数启发函数 h(n)特点:深度优先,效率高,无回溯,但不能保证得到最佳解 。探索算法:全局择优搜索(最好优先搜索),局部择优搜索数据结构：OPEN表、CLOSED表 启发信息启发信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。应用这种排序过程，需要某些估算节点“希望”的量度。用来估算节点希望程度的量度，叫做估价函数（evaluation function），有时也叫作启发函数。一个节点的“希望”（promise）有几种不同 的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；估算全路径的长度或难度（包括此节点）。我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。启发函数启发函数如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：（1）一个节点到目标节点的距离或差异的度量；（2）一个节点处在最佳路径上的概率；（3）或者根据经验的主观打分。启发函数启发函数八数码难题（八数码难题（8-puzzle）f1(T)=恰好正确地处在目标状态的字码数目恰好正确地处在目标状态的字码数目:1 13 32 24 47 76 65 58 8f1f1=4=4从实用角度，计算与目标的距离更有实际意义！从实用角度，计算与目标的距离更有实际意义！f2f2=4=41 13 32 24 47 76 65 58 8f2(T)=没有处在目标状态的字码数目（相当于粗略地给出了当前状态与没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）目标的距离）1 2 3847 6 5目标：目标：f3(T)=不在目标位置的字码距离目标位置水平距离和垂直不在目标位置的字码距离目标位置水平距离和垂直距离之和。距离之和。该函数给出了一个更好的距离评估该函数给出了一个更好的距离评估f2f2=1+1+2+2=6=1+1+2+2=61 13 32 24 47 76 65 58 81 2 3847 6 5目标：目标：启发式搜索算法启发式搜索算法 启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略:局部择优搜索 扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。全局择优搜索 在OPEN表中保留所有已生成而未考察的节点，并用启发函数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的返回指针后放入OPEN表中,再按函数值按函数值的升序重新排序的升序重新排序OPEN表中的节点表中的节点,转 Step2;全局择优搜索例子九宫重排问题,定义评价函数;h(n):目标格局与现格局(Sn)相比,位置不同的牌数.初始格局S0 目标格局Sg 2 8 3 1 2 3 1 4 =8 4 7 6 5 7 6 5h(S0)=3局部择优搜索算法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;局部搜索算法局部搜索算法 特点：从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。优点：需要很少的内存经常能在很大或无限的状态空间中找到合理的解爬山法（爬山法（Hill climbing）n一种基本的局部启发式搜索方法n基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。（启发函数值越小离目标越近）n相当于深度优先算法+启发式搜索n线式搜索，不能回溯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)启发式搜索: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:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中,再按函数值的升序重新排序按函数值的升序重新排序OPEN表中的节点表中的节点,转 Step2;删除重复节点和修改返回指针.八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）A算法的应用算法的应用八数码难题:评价函数 简单的评价函数 h(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。初始棋局初始棋局f f值等于值等于0+4=40+4=4 12384567（初始状态）5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+31238456712 3845673+2 3+412384567123845673+3 3+4123845674+1813245671 23845675+05+2八数码难题的搜索树八数码难题的搜索树1238460+475启发式搜索: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*算法的特例.启发式搜索: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*算法中,只有对h值低估才能获得优化的搜索性能为什么A*算法低估h值举例：S SA AD DF FB BE EH HC CG GI I1 11 11 11 11 11 11 11 11 11 11 1红色值表示红色值表示真实的真实的剩余代价剩余代价3 32 21 12 21 13 32 21 13 32 21 15 54 44 43 32 2多估多估n在多估情况下：S SA AD DF F1+31+31+51+51+41+4B B2+22+2A AB BC C3+13+1C CG G4 4并不是优化路径并不是优化路径!为什么A*算法低估h值举例：3 32 2S SA AD DF FB BE EH HC CG GI I1 11 11 11 11 11 11 11 11 11 11 13 32 22 21 11 11 1红色值表示红色值表示真实的真实的剩余代价剩余代价n如果h被低估:S SA AD DF F1+11+11+21+21+31+31 10 00 02 23 31 12 21 1低估低估A AB B2+02+0C C3+03+0B BG G4 4G GC CD DE E E E3!3!2+12+1f1f1f2f2f3f3f4f4A*A*A*A*算法沿算法沿f f函数进行扩展函数进行扩展启发式搜索算法A*Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组子节点,对这组子节点作如下处 理后,放入OPEN表,按评价函数的升序重新排序按评价函数的升序重新排序 OPEN表表,转 Step2;删除重复节点和修改返回指针处理.八数码难题:nh1(T)0 启发函数为0注意注意:h3(T):h3(T)h2(T)h2(T)h1(T)h1(T)h2h2=4=41 13 32 24 47 76 65 58 8nh2(T)=没有处在目标状态的字码数目没有处在目标状态的字码数目h3h3=1+1+2+2=6=1+1+2+2=61 13 32 24 47 76 65 58 8nh3(T)=不在目标位置的字码距离目标位置水平距离和垂不在目标位置的字码距离目标位置水平距离和垂直距离之和。直距离之和。1 2 3847 6 5目标：目标：曼哈顿距离曼哈顿距离八数码难题举例2 8 32 8 31 6 41 6 47 7 5 52 8 32 8 31 6 41 6 4 7 5 7 52 8 32 8 31 1 4 47 7 6 56 52 8 32 8 31 6 41 6 47 5 7 5 2 8 32 8 3 6 4 6 41 7 51 7 52 8 32 8 3 1 4 1 47 7 6 56 52 2 3 31 1 8 8 4 47 7 6 56 52 8 32 8 31 4 1 4 7 7 6 56 52 8 32 8 31 6 1 6 7 5 7 5 4 4 8 3 8 32 2 6 4 6 41 7 51 7 52 8 32 8 36 6 4 41 7 51 7 5 8 3 8 32 2 1 4 1 47 7 6 56 52 8 32 8 37 7 1 4 1 4 6 56 5 2 3 2 31 1 8 8 4 47 7 6 56 52 8 32 8 31 4 1 4 5 57 7 6 6 2 8 32 8 31 1 6 67 5 7 5 4 42 3 2 3 1 1 8 8 4 47 7 6 56 52 8 2 8 1 4 1 4 3 37 7 6 56 52 8 2 8 1 6 31 6 37 5 7 5 4 4h1=0h1=00 01 11 11 12 22 22 22 22 23 33 33 33 33 33 33 33 33 33 3h2=h2=错误数目错误数目0+40+41+51+51+31+31+51+52+32+32+32+32+42+43+33+33+43+43+23+2NotNotselectedselectedh3=h3=曼哈顿距离曼哈顿距离0+50+51+61+61+41+41+61+62+52+52+32+32+52+5Robot navigationRobot navigationCost of one horizontal/vertical step=1Cost of one diagonal step=2 f(N)=g(N)+h(N),with h(N)=距离目标位置水平距离和垂直距离之和距离目标位置水平距离和垂直距离之和Robot NavigationRobot NavigationRobot NavigationRobot Navigation02115877347676328645233365244355465645f(N)=h(N),with h(N)=距离目标位置水平距离和垂直距离之距离目标位置水平距离和垂直距离之Robot NavigationRobot Navigation02115877347676328645233365244355465645f(N)=h(N),with h(N)=距离目标位置水平距离和垂直距离之距离目标位置水平距离和垂直距离之70Robot NavigationRobot Navigationf(N)=g(N)+h(N),with h(N)=距离目标位置水平距离和垂直距离之和距离目标位置水平距离和垂直距离之和021158773476763286452333652443554656457+06+16+18+17+07+26+17+26+18+17+28+37+2 6+36+3 5+45+4 4+54+5 3+63+6 2+78+3 7+47+4 6+55+66+3 5+62+7 3+84+75+6 4+73+84+7 3+83+8 2+92+93+102+93+82+91+101+10 0+11搜索算法小结树搜索-盲目搜索-广度优先搜索 -深度优先搜索-有界深度优先 -代价树搜索 -启发式搜索-全局择优搜索(最好优先)-局部择优搜索(爬山法)-A算法(基于:f(n)=g(n)+h(n)A*算法(最佳搜索:h(n)8 4 7 5 3 7 6 5请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？4.3 问题归约法问题归约的概念问题归约的描述:三元组(S0,O,P)表示.S0:初始问题;P:本原问题本原问题集合O:操作算子集;将问题化成若干子问题.问题归约的最终目标:原问题=本原问题状态空间法是问题归约法的特例.问题归约的与或图表示与或图表示AAC6C5C4C3C2C1C6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点)3连接弧节点的可解性判别AC6C5C4C3C2C1m1m2或节点与节点可解节点的判别条件 叶节点可解或节点可解当且仅当至少有一个子节点可解.与节点可解当且仅当所有子节点都可解.不可解节点的判别条件没有子节点的非终止节点或节点不可解当且仅当所有子节点不可解.与节点不可解当且仅当至少有一个子节点不可解.与或图的搜索AC6C5C4C3C2C1m1m2或节点与节点解图求解与或图问题就是在与或图中搜索解图(或解树)的问题.解图是原与或图的一个子图(与图)搜索策略:无信息搜索与启发式搜索搜索过程:标记初始节点为可解节点(成功)或不可解节点(失败)的过程.搜索算法:与或树的搜索算法1Step1:S0=OPEN表Step2:OPEN-N-CLOSED(n)Step3:如N可扩展:扩展N=OPEN标记可解节点=CLOSED 如初始节点可解,搜索成功,结束.删去OPEN中有可解先辈的节点.Step4:N不可扩展:标记不可解节点.如初始节点不可解,搜索失败,退出.删去OPEN中有不可解先辈的节点.To Step2.54At2t3t42t1B3问题归约的例子积分问题的与或树三阶梵塔问题的与或树几何定理证明的与或树4.4 博弈树搜索博弈树的概念博弈:下棋,打牌等一类竞争性智力活动.最简单的是“二人零和,全信息,非偶然”博弈.博弈树:描述博弈过程的与或树.特点:或与节点分层交替出现;搜索空间指数增长,只能前推几步 极大极小过程剪枝技术 (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)