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

1、第四章 搜索技术形状空间法问题归约法博弈树搜索部分搜索.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 problem42618357.4.1 形状图概念形状图的概念 形状图(形状空间图)实践上是一类问题的笼统表示。许多智力问题(八数码问题、梵塔问题、游览商问题、八皇后问题、农夫过河问题等)。 实

2、践问题如途径规划、定理证明、演绎推理、机器人行动规划等都可以归结为在某一形状图中寻觅目的或途径的问题。.农夫过河问题 有一个农夫带一条狼、一只羊和一棵白菜过河。假设没有农夫看管，那么狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？ .农夫过河问题形状空间法表示以向量人，狼，羊，菜表示形状，其中每个变元可取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，10，0，0，01，0，1，01，1，0，

3、00，0，1，01，1，1，01，0，1，10，1，1，00，0，1，1人，狼，羊，菜0，0，0，11，1，0，10，1，0，1 1，1，1，1.4.2 形状空间法问题的形状空间表示(形状图表示) 形状空间的三元组(S, O, G)表示. S:初始形状集合; O: 操作集合; G:目的形状集合形状空间的搜索战略(形状图搜索)广度优先搜索, 深度优先搜索, 启发式搜索.形状空间表示的概念例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState.三数码难题123123123312312312初始棋局目的棋局.123845671238412384567412385

4、6712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567.形状图搜索图搜索是指在形状图中寻觅目的或途径的搜索。所谓搜索，顾名思义，就是从初始节点出发，沿着与

5、之相连的边试探地前进，寻觅目的节点的过程(也可以反向进展)。问题形状图搜索解解是由初始形状到目的形状的途径.形状图搜索相关问题形状选择解的性质：存在、分布、质量搜索战略.图搜索战略 图搜索控制战略一种在形状图中寻觅途径的方法。图中每个节点对应一个形状，每条连线对应一个操作符。图搜索涉及两个主要数据构造：open表 closed表.OPEN 表 OPEN表是一种动态数据构造，专门登记当前待调查待访问的节点，也叫未扩展节点表 。节点父节点编号OPEN表open表中，每个节点信息还包括指向父节点的前往指针即父节点地址.CLOSED 表 Closed表是一种动态数据构造，记录访问过的节点，也叫已扩展节

6、点表 ，其初始为空表。 编号节点父节点编号CLOSED表.开场把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目的节点吗？把n的后继节点放入OPEN表的末端，提供前往节点n的指针修正指针方向重排OPEN表失败胜利 图搜索过程框图是是否否搜索战略即表达在这里.按搜索轨迹分类图式搜索：搜索过程中，搜索途径允许构成回路。树式搜索：搜索过程中，搜索途径不允许构成回路。线式搜索：扩展节点每次只扩展一个节点。SGSG.搜索树的概念 一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼和“八数码难题等，虽然从外表上看上去和“树这种构造无关，但是整个搜索过程中的能够试

7、探点所行成的搜索空间总可以对应到一颗搜索树上去。将各类方式上不同的搜索问题笼统并一致成为搜索树的方式，为算法的设计与分析带来宏大的方便。 .1，0，0，10，0，0，01，0，1，01，1，0，00，0，1，01，1，1，01，0，1，10，1，1，00，0，1，1人，狼，羊，菜0，0，0，11，1，0，10，1，0，1 1，1，1，1.由于搜索具有探求性，所以要提高搜索效率(尽快地找到目的节点)，或要找最正确途径(最正确解)就必需留意搜索战略。对于形状图搜索，曾经提出了许多战略，它们大体可分为盲目搜索bland search)和启发式搜索heuristic search两大类。盲目搜索是无导

8、游搜索。启发式搜索是有导游搜索，即利用启发信息函数引导去寻觅问题解。搜索战略分类.盲目搜索盲目搜索又叫做无信息搜索，普通只适用于求解比较简单的问题。种类：宽度优先搜索深度优先搜索等代价搜索.图搜索战略宽度优先深度优先启发式搜索一种在图中寻觅途径的方法。.宽度优先搜索战略优先搜索形状空间中离初始形状近的节点(形状特点:具有完备性, 占用空间搜索算法 数据构造:OPEN表 : 先进先出队列,存放待扩展的节点. 节点(形状) 父节点编号(前往指针)CLOSED表 : 存放已被扩展过的节点.编号 节点 父节点编号.开场把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表

9、能否有后继节点为目的节点？扩展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;. 例子八数码难题8-puzzle problem 12

10、38456712384567目的形状初始形状规定：将牌移入空格的顺序为：从空格左边开场顺时针旋转。不许斜向挪动，也不前往先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解目的节点。.1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图 八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212

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

12、后部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)新的节点被插入到栈OPEN的后部12345OPEN= (5,10,11,6,7)CLOSED=(1,2,3,4 )6789101112131415.宽度优先搜索(Breadth-First Strategy)新的节点被插入到栈OPEN的后部

13、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.深度优先搜索战略新节点优先扩展, 直到到达一定的深度限制.假设找不到目的或无法在扩展时,回溯到另一节点继续扩展.特点: 需求深度限制, 需求回溯控制, 省空间探求算法: 数据构造: OPEN表 : 后进先出队列,存放待扩展的节点. CLOSED表

14、: 存放已被扩展过的节点.除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.深度优先算法框图 算法开场把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不可扩展, 那

15、么转Step2;Step6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入OPEN表首部, 转 Step2;.深度优先搜索(Depth-First Strategy)新的节点被插入到栈OPEN的前部12345OPEN= (1)CLOSED=( )6789101112131415.Depth-First Strategy新的节点被插入到栈OPEN的前部12345OPEN = (2, 3)CLOSED=( 1 )6789101112131415.Depth-First Strategy 新的节点被插入到栈OPEN的前部12345OPEN = (4, 5, 3)CLOSED=( 1,2 )

16、6789101112131415.Depth-First Strategy新的节点被插入到栈OPEN的前部12345CLOSED=( 1,2,4 )67OPEN = (6,7, 5, 3)89101112131415.Depth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12131415.Depth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12131415.Depth-Fi

17、rst Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7 )OPEN = (8,9,3)12131415.Depth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12131415.Depth-First Strategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3).Depth-First Strategy新的

18、节点被插入到栈OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11).Depth-First Strategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12131415OPEN = (12,13,11).代价树搜索代价树：搜索树中每条衔接弧线上的有关代价,表示时间、间隔等破费。代价树搜索等代价搜索 ：是宽度优先搜索的一种推行，不是沿着等长度途径断层进展扩展，而是沿着等代价途径断层进展扩展。 *假设一切衔接弧线具有相等代价，那么简化为

19、宽度优先搜索算法。.算法运用符号 c(i,j)：把从节点i到其后继节点j的衔接弧线代价记为c(i,j) g(i)：把从起始节点S到任一节点i的途径代价记为g(i). 在搜索树非循环途径上，假设g(i)是从起始节点S到节点i的最少途径上的代价。 等代价搜索方法以g(i)的递增顺序扩展其节点。.开场把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表能否有后继节点为目的节点？失败胜利等代价搜索算法框图是否是否令g(s)=0S能否目的节点？是胜利否开场把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表能否有后继节点

20、为目的节点？失败胜利是是否令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能否目的节点？是胜利.等代价搜索算法1 把起始节点放到未扩展节点表OPEN中。假设此起始节点为一目的节点，那么求得一个解；否那么令gS=0。2 假设

21、OPEN是个空表，那么没有解而失败退出。3 从OPEN 表中选择一个节点i，使其gi为最小。假设有几个节点都合格，那么就要选择一个目的节点作为节点 i要是有目的节点的话；否那么，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。4 假设节点i为目的节点，那么求得一个解。5 扩展节点i。假设没有后继节点，那么转向第2步。6 对于节点i的每个后继节点j，计算gj=gi+ci,j，并把一切后继节点j放进OPEN表。提供回到节点i的指针。7 转向第2步。.宽度优先d = 1d = 2d = 3d = 4宽度优先搜索：沿着等长度途径断层进展扩展g1g2g3g4等代价搜索等代价搜索

22、：沿等代价途径断层进展扩展比较宽度优先搜索与等代价搜索.ADBECFGS34445543搜索树非循环途径2SADBDEACEEBBFDFBFCEACGGCGFG33333222444444444444555555.等代价搜索算法SADBDAEEBBFBFCEACGGGFC34455525433478961011CEDFG4511121313134 在每一步, 选择具有最低累计权值的点进展扩展.启发式搜索盲目搜索的问题： “组合爆炸利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息.利用启发式信息定义节点的启发函数 h(n)特点: 深度优先, 效率高, 无回溯, 但不

23、能保证得到最正确解 。探求算法:全局择优搜索(最好优先搜索), 部分择优搜索数据构造：OPEN表 、 CLOSED表. 启发信息启发式搜索就是利用启发性信息进展制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息普通可分为以下三类： (1)用于扩展节点的选择，即用于决议应先扩展哪一个节点，以免盲目扩展。 (2)用于生成节点的选择，即用于决议应生成哪些后续节点，以免盲目地生成过多无用节点。 (3)用于删除节点的选择，即用于决议应删除哪些无用节点，以免呵斥进一步的时空浪费。.重排OPEN表，使搜索沿某个被以为最有希望的途径扩展。运用这种排序过程，需求某些估算节点“希望的

24、量度。用来估算节点希望程度的量度，叫做估价函数evaluation function，有时也叫作启发函数。一个节点的“希望promise有几种不同 的定义方法。 在形状空间问题中，一种方法是估算目的节点到此节点的间隔；估算全途径的长度或难度包括此节点。我们用符号f来标志估价函数，用fn表示节点n的估价函数值。启发函数.如何定义一个估价启发函数呢？估价启发函数并无固定的方式，需求详细问题详细分析。通常可以参考的思绪有： 1 一个节点到目的节点的间隔或差别的度量； 2一个节点处在最正确途径上的概率； 3或者根据阅历的客观打分。启发函数.八数码难题8-puzzlef1(T) = 恰好正确地处在目的形

25、状的字码数目:13247658f1= 4从适用角度，计算与目的的间隔更有实践意义！f2= 413247658f2(T) =没有处在目的形状的字码数目相当于粗略地给出了当前形状与目的的间隔12384765目的：.f3(T) = 不在目的位置的字码间隔目的位置程度间隔和垂直间隔之和。该函数给出了一个更好的间隔评价f2= 1 + 1 + 2 + 2 = 61324765812384765目的：. 启发式搜索算法 启发式搜索要用启发函数来导航，其搜索算法就要在形状图普通搜索算法根底上再添加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种战略: 部分择优搜索 扩展节点N后仅对N的子

26、节点按启发函数值大小以升序排序，再将它们依次放入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

27、(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,

28、那么搜索胜利,终了.Step5: 假设N不可扩展, 那么转Step2;Step6: 扩展N,计算每个子节点的函数值h(x),并将一切子节点按函数值的升序排序后, 配上指向N的前往指针放入OPEN表的首部, 转 Step2;.部分搜索算法 特点： 从单独的一个当前形状出发，通常只挪动到与之相邻的形状，并且不保管解的途径。优点：需求很少的内存经常能在很大或无限的形状空间中找到合理的解.爬山法Hill climbing一种根本的部分启发式搜索方法根本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。启发函数值越小离目的越近相当于深度优先算法

29、+启发式搜索线式搜索，不能回溯向目的值添加的方向继续挪动.启发式搜索: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

30、到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)的子节点,作

31、完以下处置后,将余下子节点配上指向N的前往指针后放入OPEN表中, 再按函数值的升序重新排序OPEN表中的节点, 转 Step2;删除反复节点和修正前往指针.八数码难题8-puzzle problem12384567目的形状12384567初始形状A算法的运用.八数码难题:评价函数 简单的评价函数 h(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。 初始棋局f值等于0+4=4 12384567初始形状.5723451238456712384567123845671+31+51+511238456712384567123845

32、672+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):从N到目的节点的最短途径; 称此时的A算法为A*算法.A*算法的特征:A*是可采用的:只需最短途径存在,就一定能找出.假设有 h1(n) = h2(n) = h*(n), 那么h2比h1展开更少的节点.广度优先搜索是当h(n)

33、=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值举例：SADFBEHCGI11111111111红色值表示真实的剩余代价3212132132154432多估在多估情况下：SADF1+31+51+4B2+2ABC3+1CG4并不是优化途径!.为什么A*算法

34、低估h值举例：32SADFBEHCGI11111111111322111红色值表示真实的剩余代价假设h被低估:SADF1+11+21+310023121低估AB2+0C3+0BG4GCDEE3 !2+1.f1f2f3f4A*A*算法沿f函数进展扩展.启发式搜索算法A*Step1: 把初始节点S0放入OPEN表中;Step2: 假设OPEN表为空,那么搜索失败,退出.Step3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n;Step4: 假设目的节点Sg=N, 那么搜索胜利,终了.Step5: 假设N不可扩展, 那么转Step2;Step6: 扩展N, 生成一组子节点,

35、对这组子节点作如下处 理后, 放入OPEN表, 按评价函数的升序重新排序 OPEN表, 转 Step2;删除反复节点和修正前往指针处置.八数码难题:h1(T) 0 启发函数为0留意: h3(T) h2(T) h1(T) h2= 413247658h2(T) =没有处在目的形状的字码数目h3= 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

36、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 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+5.Rob

37、ot navigationCost of one horizontal/vertical step = 1Cost of one diagonal step = 2 f(N) = g(N) + h(N), with h(N) =间隔目的位置程度间隔和垂直间隔之和.Robot Navigation.Robot Navigation02115877347676328645233365244355465645f(N) = h(N), with h(N) =间隔目的位置程度间隔和垂直间隔之.Robot Navigation02115877347676328645233365244355465645f(

38、N) = h(N), with h(N) =间隔目的位置程度间隔和垂直间隔之70.Robot Navigationf(N) = g(N)+h(N), with h(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+11.搜索算法小结树搜索-盲目搜

39、索-广度优先搜索 -深度优先搜索-有界深度优先 -代价树搜索 -启发式搜索-全局择优搜索(最好优先) -部分择优搜索(爬山法) -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:操作算子集;将问题化成假设干子问题.问题归约的最终目的: 原问题 = 本原问题形状空间法是问题归约法的特例.问题归约的与或图表示.与或图表示AAC6C5C4C3C2C1C

40、6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点)3衔接弧.节点的可解性判别AC6C5C4C3C2C1m1m2或节点与节点可解节点的判别条件 叶节点可解或节点可解当且仅当至少有一个子节点可解.与节点可解当且仅当一切子节点都可解.不可解节点的判别条件没有子节点的非终止节点或节点不可解当且仅当一切子节点不可解.与节点不可解当且仅当至少有一个子节点不可解.与或图的搜索AC6C5C4C3C2C1m1m2或节点与节点解图求解与或图问题就是在与或图中搜索解图(或解树)的问题.解图是原与或图的一个子图(与图)搜索战略:无信息搜索与启发式搜索搜索过程: 标志初始节点为可解节点(胜利)或不可解节点

41、(失败)的过程.搜索算法: .与或树的搜索算法1Step1: S0 = OPEN表Step2: OPEN -N- CLOSED (n)Step3: 如N可扩展:扩展N=OPEN标志可解节点=CLOSED 如初始节点可解,搜索胜利,终了.删去OPEN中有可解先辈的节点.Step4: N不可扩展:标志不可解节点.如初始节点不可解, 搜索失败,退出.删去OPEN中有不可解先辈的节点. To Step2.54At2t3t42t1B3.问题归约的例子积分问题的与或树三阶梵塔问题的与或树几何定理证明的与或树.4.4 博弈树搜索博弈树的概念博弈:下棋, 打牌等一类竞争性智力活动.最简单的是“二人零和,全信息

42、,非偶尔博弈.博弈树:描画博弈过程的与或树. 特点: 或与节点分层交替出现;搜索空间指数增长,只能前推几步 极大极小过程剪枝技术. (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失败分币原那么:每次要将一堆分为币数不等的两堆 . 胜负规范:交替分钱币,谁不能再分谁输.分钱

43、币游戏的博弈树结论: ?. (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必胜. 钱币为8，9时，结论如何？钱币为10 时，结论如何？钱币为 x 时，结论如何？分钱币游戏思索题.极大极小过程BAIHGF

44、CQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 -1 1 R25-222-15倒推过程.-剪枝技术BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 R25 1MAX节点的下界 2MIN节点的上界25剪枝剪枝.-剪枝技术MAX节点的倒退值 : 取后继节点估值的最大值. MAX节点的倒推下界值.MIN节点的倒退值 : 取后继节估值点的最小值. MIN节点的倒推上界值.剪枝: 当MIN节点的值 祖先MAX节点的值时,不用展开MIN的其他子节点. 剪枝: 当MAX节点的值 祖先MIN节点的值时,不用展开MAX的其他子节点. .讨论部分优先搜索与全局优先搜索

45、的区别是什么?什么是启发式搜索？A算法？A*算法？博弈树有什么特点?利用博弈树分析九枚分钱币游戏的能够结论?-.4.5 部分搜索(Local Search)*经过在当前解近旁的搜索,不断改善当前解,最终搜索到满足要求的最优解或次优解.普经过程Step1: 初始化. 求初始解x0=当前解x, k=1;Step2: 完善解. 在x的近旁N(x)中假设有更好解y, 那么 更新解x:=y, k:=k+1; To Step2 否那么,输出x, 停顿搜索.被用于大规模N-queen, SAT等问题的求解.部分搜索法初始解x0 x3x4x1x2x5N(x0)N(x1)N(x5).部分搜索法的特征部分搜索的要素评价函数确实定初始解确实定N(x)确实定解更新的方法终止条件特点：