1、第四章 搜索技术n状态空间法n问题归约法n博弈树搜索n局部搜索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搜索的挑战组合爆炸n魔方问题n博弈问题n皇后问题n行商问题n排课问题（调度问题）n背包问题 数码问题1238456712384567（目标状态）（初始状态）八数码难题（8-puzzle problem）426183574.1 状态图概念n状态图的概念 状态图(状态空间图)实际上是一类问题的抽象表示。n许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇
2、后问题、农夫过河问题等)。n 实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。农夫过河问题n 有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？ 农夫过河问题状态空间法表示n以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸n初态是：（0，0，0，0）n终态是：（1，1，1，1）n非法中间状态有： （0，0，1，1），（0，1，1，0），（0，1，1，1）， （1，1，0，0），（1，0，0，1）
3、，（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 状态空间法n问题的状态空间表示(状态图表示) 状态空间的三元组(S, O, G)表示. S:初始状态集合; O: 操作集合; G:目标状态集合n状态空间的搜索策略(状态图搜索)广度优先搜索, 深度优先搜索, 启发式搜索状态空间表示的概念n例如下棋、迷宫及各种游戏。OriginalStateMid
4、dleStateGoalState三数码难题123123123312312312初始棋局目标棋局1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123
5、84567141516171819202112384567状态图搜索n图搜索是指在状态图中寻找目标或路径的搜索。n所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径状态图搜索相关问题n状态选择n解的性质：存在、分布、质量n搜索策略图搜索策略 n图搜索控制策略一种在状态图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。n图搜索涉及两个主要数据结构：open表 closed表OPEN 表n OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表 。节
6、点节点父节点编号父节点编号OPEN表表open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）CLOSED 表表n Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表 ，其初始为空表。 编号编号节点节点父节点编号父节点编号CLOSED表表开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功 图搜索过
7、程框图图搜索过程框图是是是是否否否否搜索策略即搜索策略即体现在这里体现在这里按搜索轨迹分类n图式搜索图式搜索：搜索过程中，搜索路径允许形成回路。n树式搜索树式搜索：搜索过程中，搜索路径不允许形成回路。n线式搜索线式搜索：扩展节点每次只扩展一个节点。SGSG搜索树的概念 n一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。n将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。 22178634582736451827163
8、452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119（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，
9、0，0，1）（1，1，0，1）（0，1，0，1） （1，1，1，1）n由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。n对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（bland search)和启发式搜索（heuristic search）两大类。n盲目搜索是无向导搜索。n启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。搜索策略分类搜索策略分类盲目搜索n盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。n种类：宽度优先搜索深度优先搜索等代价搜索图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的
10、方法。宽度优先搜索策略n优先搜索状态空间中离初始状态近的节点(状态n特点:具有完备性, 占用空间n搜索算法n 数据结构:OPEN表 : 先进先出队列先进先出队列,存放待扩展的节点. 节点(状态) 父节点编号(返回指针)CLOSED表 : 存放已被扩展过的节点.编号 节点 父节点编号开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的末端末端，提供返回节点，提供返回节点n的指针的指针失败失败成功成功 宽
11、度优先算法框图宽度优先算法框图是是否否是是否否v 算法否否宽度优先搜索算法nStep1: 把初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN表中第一个节点N放入CLOSED表 中, 并标以顺序号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入放入OPEN表尾部表尾部, 转 Step2;n 例子例子八数码难题（八数码难题（8-puzzle problem） 1238456712384567（目标状态）（初始
12、状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671
13、238456712 384567123845671238456712384567141516171819202112384567宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (1)CLOSED=( )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (2,3)CLOSED=(1 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (3,4,5)CLOSED=(1,2 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插
14、入到栈OPEN的后部12345OPEN= (4,5,10,11)CLOSED=(1,2,3 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (5,10,11,6,7)CLOSED=(1,2,3,4 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (10,11,6,7,8,9)CLOSED=(1,2,3,4,5 )6789101112131415宽度优先搜索宽度优先搜索(新的节点被插入到栈OPEN的后部12345OPEN= (11,6,7,8,9,12,13)CLO
15、SED=(1,2,3,4,5,10 )6789101112131415深度优先搜索策略n新节点优先扩展, 直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.n特点: 需要深度限制, 需要回溯控制, 省空间n探索算法: n数据结构: OPEN表 : 后进先出队列后进先出队列,存放待扩展的节点. CLOSED表 : 存放已被扩展过的节点.n除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.深度优先算法框图深度优先算法框图v 算法开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表
16、表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的前端前端，提供返回节点，提供返回节点n的指针的指针失败失败成功成功是是否否是是否否深度优先搜索算法nStep1: 把初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入放入OPEN表首部表首部,
17、 转 Step2;深度优先搜索深度优先搜索(新的节点被插入到栈OPEN的前部12345OPEN= (1)CLOSED=( )6789101112131415新的节点被插入到栈OPEN的前部12345OPEN = (2, 3)CLOSED=( 1 )6789101112131415 新的节点被插入到栈OPEN的前部12345OPEN = (4, 5, 3)CLOSED=( 1,2 )6789101112131415新的节点被插入到栈OPEN的前部12345CLOSED=( 1,2,4 )67OPEN = (6,7, 5, 3)89101112131415新的节点被插入到栈OPEN的前部12345
18、67891011CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7 )OPEN = (8,9,3)12131415新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12131415新的节点被插入到栈OPEN的前部123456789121011
19、131415CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3)新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11)新的节点被插入到栈OPEN的前部1234567891011CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12131415OPEN = (12,13,11)代价树搜索代价树：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。代价树搜索（等代价搜索） ：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行
20、扩展。 *若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。算法使用符号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放入
21、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是
22、否目标节点是否目标节点？是是成功扩展扩展i i，计算其后继节点，计算其后继节点j j的的g(j)g(j)，并，并把后继节点放入把后继节点放入OPENOPEN表表开始把把S S放入放入OPENOPEN表表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点是否有后继节点为目标节点？为目标节点？失败成功是是是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功等代价搜索算法n（1） 把起始节点放到未扩展节点表把起始节点放到未扩展节点表OPEN中。如果此起始节点为一中。如果此起始节点为一目标节点，则求得一个解；否则令目标节点，则求得一个解；否则令g（S
23、）=0。n（2） 如果如果OPEN是个空表，则没有解而失败退出。是个空表，则没有解而失败退出。n（3） 从从OPEN 表中选择一个节点表中选择一个节点i，使其，使其g（i）为最小。如果有几个节）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点点都合格，那么就要选择一个目标节点作为节点 i（要是有目标节点的（要是有目标节点的话）；否则，就从中选一个作为节点话）；否则，就从中选一个作为节点i。把节点。把节点i从从OPEN表移至扩展节点表移至扩展节点表表CLOSED中。中。n（4） 如果节点如果节点i为目标节点，则求得一个解。为目标节点，则求得一个解。n（5） 扩展节点扩展节点i。如果
24、没有后继节点，则转向第（。如果没有后继节点，则转向第（2）步。）步。n（6） 对于节点对于节点i的每个后继节点的每个后继节点j，计算，计算g（j）=g（i）+c（i,j），），并并把所有后继节点把所有后继节点j放进放进OPEN表。提供回到节点表。提供回到节点i的指针。的指针。n（7） 转向第（转向第（2）步。）步。沿着等长度沿着等长度路径断层进行扩展路径断层进行扩展等代价路径等代价路径断层进行扩展断层进行扩展比较宽度优先搜索与等代价搜索比较宽度优先搜索与等代价搜索搜索树（非循环路径）等代价搜索算法等代价搜索算法 在每一步, 选择具有最低累计权值的点进行扩展启发式搜索n盲目搜索的问题： “组合爆
25、炸”n利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息启发信息.n利用启发式信息定义节点的启发函数启发函数 h(n)n特点: 深度优先, 效率高, 无回溯, 但不能保证得到最佳解 。n探索算法:n全局择优搜索(最好优先搜索), 局部择优搜索n数据结构：OPEN表 、 CLOSED表 启发信息启发信息n启发式搜索就是利用启发性信息进行制导的搜索。n启发性信息就是有利于尽快找到问题之解的信息。n按其用途划分，启发性信息一般可分为以下三类： (1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。 (2)用于生成节点的选择，即用于决定应生成哪些后续节点，以
26、免盲目地生成过多无用节点。 (3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。n重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。n应用这种排序过程，需要某些估算节点“希望”的量度。n用来估算节点希望程度的量度，叫做估价函数（evaluation function），有时也叫作启发函数。n一个节点的“希望”（promise）有几种不同 的定义方法。 在状态空间问题中，一种方法是估算目标节点到此节点的距离；估算全路径的长度或难度（包括此节点）。n我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。启发函数启发函数n如何定义一个估价（启发）函数呢？估价
27、（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有： （1） 一个节点到目标节点的距离或差异的度量； （2）一个节点处在最佳路径上的概率； （3）或者根据经验的主观打分。启发函数启发函数八数码难题（八数码难题（8-puzzle）f1(T) = 恰好正确地处在目标状态的字码数目恰好正确地处在目标状态的字码数目:f2(T) =没有处在目标状态的字码数目（相当于粗略地给出了当前状态没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）与目标的距离）1 2 3847 6 5目标：目标：f3(T) = 不在目标位置的字码距离目标位置水平距离和垂直不在目标位置的字码距离目
28、标位置水平距离和垂直距离之和。距离之和。 该函数给出了一个更好的距离评估该函数给出了一个更好的距离评估1 2 3847 6 5目标：目标： 启发式搜索算法启发式搜索算法n n启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略: n局部择优搜索 扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。n全局择优搜索 在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。全局
29、择优搜索算法nStep1: 把初始节点S0放入OPEN表中,计算h(S0);nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序编号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N,计算每个子节点的函数值h(x),将所有子节点配上指向N的返回指针后放入OPEN表中, 再按函数值按函数值的升序重新排序的升序重新排序OPEN表中的节点表中的节点, 转 Step2;全局择优搜索例子n九宫重排问题, 定义评价函数; h(n):目标格局与现格局(
30、Sn)相比,位置不同的牌数. 初始格局S0 目标格局Sg 2 8 3 1 2 3 1 4 = 8 4 7 6 5 7 6 5h(S0) = 3局部择优搜索算法nStep1: 把初始节点S0放入OPEN表中,计算h(S0);nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序编号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N,计算每个子节点的函数值h(x),并将所有子节点按函数值的升序排序后函数值的升序排序后, 配上指向N的返回指针放入
31、OPEN表的首部, 转 Step2;局部搜索算法局部搜索算法n 特点： 从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。n优点：n需要很少的内存n经常能在很大或无限的状态空间中找到合理的解爬山法（爬山法（Hill climbing）n一种基本的局部启发式搜索方法n基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。（启发函数值越小离目标越近）n相当于深度优先算法+启发式搜索n线式搜索，不能回溯n向目标值增加的方向持续移动启发式搜索:A算法n评价函数 f(x) = g(x) + h(x)，表示通过节点x的估计
32、代价值。nmSGg(n)g(m)h(n)h(m)比较f(n)和f(m) 大小，决定节点搜索顺序，即在OPEN表中的顺序启发式搜索:A算法n评价函数 f(x) = g(x) + h(x) n当f(x) = g(x) 时，为宽度优先搜索n当f(x) = 1/g(x)时，为深度优先搜索n当f(x) = h(x) 时，为全局优先搜索nmSGg(n)g(m)h(n)h(m)启发式搜索:A算法n评价函数的一般形式 : f(n) = g(n) + h(n)g(n):从S0到Sn的实际代价(搜索的横向因子)h(n):从N到目标节点的估计代价,称为启发函数 (搜索的纵向因子);n特点: 效率高, 无回溯, n搜
33、索算法OPEN表 : 存放待扩展的节点. CLOSED表 : 存放已被扩展过的节点.启发式搜索:A算法nStep1: 把附有计算f(S0)初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表中, 并标以顺序编号n;nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中, 再按函数值的升序重新排序按函数值的升序重新排序OPEN表中的节点表
34、中的节点, 转 Step2;n删除重复节点和修改返回指针.八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）A算法的应用算法的应用八数码难题:评价函数 n简单的评价函数 h(n)=d(n)+W(n)n其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。 12384567（初始状态）5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+31238456712 3845673+2 3+41238456712384567
35、3+3 3+4123845674+1813245671 23845675+05+2八数码难题的搜索树八数码难题的搜索树1238460+475启发式搜索:A*算法n评价函数的一般形式:f(n) = g(n) + h(n) 且 h(n) = h*(n)g(n),h(n):定义同A算法;h*(n):从N到目标节点的最短路径; 称此时的A算法为A*算法.nA*算法的特征:nA*是可采纳的:只要最短路径存在,就一定能找出.n如果有 h1(n) = h2(n) = h*(n), 那么h2比h1展开更少的节点.n广度优先搜索是当h(n)=0时的A*算法的特例.启发式搜索:A*算法n评价函数 f(x) = g
36、(x) + h(x) ( 当h(n) = h*(n) )nSGg(n)=g*(n)h(n) = h*(n) A*算法要求保守估计： f(n) 0。n4)： h(n)=h*(n)为什么A*算法低估h值n在A*算法中，对所有的x存在h(x)h*(x)（低估)n在A*算法中,只有对h值低估才能获得优化的搜索性能为什么A*算法低估h值n举例：n在多估情况下：为什么A*算法低估h值n举例：n如果h被低估:启发式搜索算法A*nStep1: 把初始节点S0放入OPEN表中;nStep2: 若OPEN表为空,则搜索失败,退出.nStep3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n;
37、nStep4: 若目标节点Sg=N, 则搜索成功,结束.nStep5: 若N不可扩展, 则转Step2;nStep6: 扩展N, 生成一组子节点, 对这组子节点作如下处 理后, 放入OPEN表, 按评价函数的升序重新排序按评价函数的升序重新排序 OPEN表表, 转 Step2;n删除重复节点和修改返回指针处理.八数码难题:nh1(T) 0 启发函数为0nh2(T) =没有处在目标状态的字码数目没有处在目标状态的字码数目nh3(T) =不在目标位置的字码距离目标位置水平距离和垂不在目标位置的字码距离目标位置水平距离和垂直距离之和。直距离之和。1 2 3847 6 5目标：目标：曼哈顿距离曼哈顿距
38、离八数码难题举例曼哈顿距离曼哈顿距离Cost of one horizontal/vertical step = 1Cost of one diagonal step = 2 f(N) = g(N) + h(N), with h(N) =距离目标位置水平距离和垂直距离之和距离目标位置水平距离和垂直距离之和02115877347676328645233365244355465645f(N) = h(N), with h(N) =距离目标位置水平距离和垂直距离之距离目标位置水平距离和垂直距离之02115877347676328645233365244355465645f(N) = h(N), wi
39、th h(N) =距离目标位置水平距离和垂直距离之距离目标位置水平距离和垂直距离之70f(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+10 0+11搜索算法小结树搜索-
40、盲目搜索-广度优先搜索 -深度优先搜索-有界深度优先 -代价树搜索 -启发式搜索-全局择优搜索(最好优先) -局部择优搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳搜索: h(n) 8 4 7 5 3 7 6 5n请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？4.3 问题归约法n问题归约的概念n问题归约的描述: 三元组(S0, O, P)表示. S0:初始问题; P:本原问题本原问题集合O:操作算子集;将问题化成若干子问题.n问题归约的最终目标: 原问题 = 本原问题n状态空间法是问题归约法的特例.n问题归约的与或图表示与或图表示AAC6C5
41、C4C3C2C1C6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点)3连接弧节点的可解性判别AC6C5C4C3C2C1m1m2或节点与节点可解节点的判别条件 叶节点可解或节点可解当且仅当至少有一个子节点可解.与节点可解当且仅当所有子节点都可解.不可解节点的判别条件没有子节点的非终止节点或节点不可解当且仅当所有子节点不可解.与节点不可解当且仅当至少有一个子节点不可解.与或图的搜索AC6C5C4C3C2C1m1m2或节点与节点解图求解与或图问题就是在与或图中搜索解图(或解树)的问题.解图是原与或图的一个子图(与图)搜索策略:无信息搜索与启发式搜索搜索过程: 标记初始节点为可解节点(成
42、功)或不可解节点(失败)的过程.搜索算法: 与或树的搜索算法1Step1: S0 = OPEN表Step2: OPEN -N- CLOSED (n)Step3: 如N可扩展:扩展N=OPEN标记可解节点=CLOSED 如初始节点可解,搜索成功,结束.删去OPEN中有可解先辈的节点.Step4: N不可扩展:标记不可解节点.如初始节点不可解, 搜索失败,退出.删去OPEN中有不可解先辈的节点. To Step2.54At2t3t42t1B3问题归约的例子n积分问题的与或树n三阶梵塔问题的与或树n几何定理证明的与或树4.4 博弈树搜索n博弈树的概念n博弈:下棋, 打牌等一类竞争性智力活动.最简单的
43、是“二人零和,全信息,非偶然”博弈.n博弈树:描述博弈过程的与或树. 特点: 或与节点分层交替出现;n搜索空间指数增长,只能前推几步 n极大极小过程n剪枝技术 (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失败分币原则:每次要将一堆分为币数不等的两堆 . 胜负标准:交替分
44、钱币,谁不能再分谁输.分钱币游戏的博弈树结论: ? (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必胜 n钱币为8，9时，结论如何？n钱币为10 时，结论如何？n钱币为 x 时，结论如何？分钱币游戏思
45、考题极大极小过程BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 -1 1 R25-222-15倒推过程-剪枝技术BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 -2 5 7 R25 1MAX节点的下界 2MIN节点的上界25剪枝剪枝-剪枝技术nMAX节点的倒退值 : 取后继节点估值的最大值. MAX节点的倒推下界值.nMIN节点的倒退值 : 取后继节估值点的最小值. MIN节点的倒推上界值.n剪枝: 当MIN节点的值 祖先MAX节点的值时,不必展开MIN的其余子节点. n剪枝: 当MAX节点的值 祖先MIN节点的值时,不必展开MAX的其余子节点.
46、讨论n局部优先搜索与全局优先搜索的区别是什么?n什么是启发式搜索？A算法？A*算法？n博弈树有什么特点?n利用博弈树分析九枚分钱币游戏的可能结论?-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
47、)局部搜索法的特征1. 局部搜索的要素评价函数的确定初始解的确定N(x)的确定解更新的方法终止条件2. 特点：简单,高效,但不完备-局部最优解3. 改进方法:多起点、加入非确定性、 加入从局部最优解脱出的方法Nqueen问题的求解QQQQQQQQNqueen问题的求解(皇后 N,方案数):(4,2) (5,10) ( 6,4) (7,40) ( 8,92) ( 9,352) (10,724) Nqueen问题的求解最快的N皇后问题C Program ：传统的递归算法，但使用了C的位操作以极大地提高了运行速度。(较快的workstation上的结果。) Queens Number of solu
48、tions Time(secnds) 12 14200 1 13 73712 4 14 365596 28 15 2279184138 16 14772512993 Nqueen问题的求解Fuction queen_search(queen:array1.n of integer)Begin repeart Generate a random solution for queens; forall i,j where queeni or queenj is attached do if swap(queeni,queenj) reduces collisions then perform_sw
49、ap(queeni,queenj); until no collisions;endNqueen问题的求解Queens 10100100010000 100000500000Time0.1 0.1 2.3 37 1167 1010601 0 0 0 0 02 0 0 0 0 03 0 0 0 0 04 0 0 0 0 05 0 0 0 0 06 0 0 0 0 0123456q u e e n st i m e * 1 0可满足性判别问题(SAT)Satisfiability Problem SAT问题的定义 : 三元组(X,L,C) X:布尔变量的集合; L:文字的集合; C:子句的集合 例
50、如: C1 : A V B V -CC4 : -A V B V C C2 : AV -B V CC5 : -A V -B V -CC3 : A V B V CC6 : -A V -B V C 子句间是逻辑与的关系. 问C是否可满足?或是否存在使所有字句可满足的解? SAT问题是第一个被证明的NP-完全问题.Procedure SAT1.0() get-SAT-instance(); X0=select_an-initial_point();conflicts := compute_conflicts(x0);/* search*/k:=0; while conflicts != 0 do fo
