第1讲 搜索问题

1、中国农业大学信息与电气工程学院2大纲v一、搜索问题表示一、搜索问题表示法法v二二、状态空间的搜索策略、状态空间的搜索策略。 盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题，且需要大量的时间空间作为基础。 启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。3搜索问题（续1）S0Sg问题全状态空间问题的搜索空间解路径概念1：状态空间表示法v状态空间表示法状态空间表示法 是用来表示问题及其搜索过程的一种方法。是人工智能中最基本的形式化方法，也是讨论问题求解技术的基础。 是用“状态”和“算符”来表示问题的一种方法。

2、 其中，“状态”用以描述问题求解过程中不同时刻的状况。“算符”表示对状态的操作，算符的每次使用就使问题由一种状态变换为另一种状态。 当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。概念1：状态空间表示法v 状态是描述问题求解过程中的任一时刻的数据结构，一般状态是描述问题求解过程中的任一时刻的数据结构，一般用一组变量的有序组合表示。用一组变量的有序组合表示。v 算符算符：引起状态中某些分量发生改变，从而使一个具体状：引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。态变化到另一个具体状态的作用。v 状态空间：由问题的全部状态及一切可用算符所构成的集状

3、态空间：由问题的全部状态及一切可用算符所构成的集合，称为问题的状态空间，一般用三元组表示：合，称为问题的状态空间，一般用三元组表示：v S是问题的初始状态集合；是问题的初始状态集合；F是算符的集合；是算符的集合；G是目标状态是目标状态的集合。的集合。),(10kkkSSS）GF,S,（6举例：梵塔问题的状态空间 举例：举例：二二阶梵塔问题。阶梵塔问题。 一号杆有一号杆有A A、B B两个金盘，两个金盘，A A小于小于B B。要求将。要求将ABAB移至三号杆，每次只可移动一个盘子，任何时移至三号杆，每次只可移动一个盘子，任何时刻刻B B不能在不能在A A上。上。 用二元组用二元组（S SA A，

4、S SB B）表示状态，表示状态，S SA A表示表示A A所在杆号，所在杆号，S SB B表示表示B B所在杆号，全部状态如下：所在杆号，全部状态如下： （1 1，1 1），（），（1 1，2 2），（），（1 1，3 3） （2 2，1 1），（），（2 2，2 2），（），（2 2，3 3） （3 3，1 1），（），（3 3，2 2），（），（3 3，3 3）7举例 梵塔问题的状态空间AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（

5、：（3，2）123S6：（：（3，1）AAAAABABBBBBBB8举例 梵塔问题的状态空间转换规则：转换规则：A A（i i，j j）表示金盘）表示金盘A A从第从第i i号杆移到号杆移到j j号杆号杆 B B（i i，j j）表示金盘）表示金盘B B从第从第i i号杆移到号杆移到j j号杆号杆 A A（1 1，2 2），），A A（1 1，3 3），）， A A（2 2，1 1） A A（2 2，3 3），），A A（3 3，1 1），）， A A（3 3，2 2） B B（1 1，2 2），），B B（1 1，3 3），）， B B（2 2，1 1） B B（2 2，3 3），），B B

6、（3 3，1 1），）， B B（3 3，2 2）初始状态初始状态（1 1，1 1），），目标状态目标状态（3 3，3 3）梵塔问题用状态图表示为梵塔问题用状态图表示为： (1,1),A(1,2),B(3,2),(3,3)9举例： 梵塔问题的状态空间1,12,13,12,33,31,33,21,22,2A(1,3)A(2,1)B(3,1)A(3,2)A(1,3)B(1,3)A(2,1)B(1,2)A(3,2)10思考：n（n3）阶梵塔问题v 假设金片假设金片PkPk从小片到大片按下标从小片到大片按下标k k顺序编号，即顺序编号，即k=1k=1，2 2，3 3，n n，n n阶梵塔问题状态空间可

7、用矢量表示为：阶梵塔问题状态空间可用矢量表示为： (P(P1 1, P, P2 2, P, P3 3, P, Pk k, P, Pn n) ) P Pk k表示第表示第k k个金片穿在编号为个金片穿在编号为P Pk k的宝石针上，的宝石针上， P Pk k=1=1，2 2，33v 初始状态初始状态 S S0 0=(1,1,1,1,1)=(1,1,1,1,1)v 目标状态目标状态 S Sg1g1 =(2,2,2,2,2) =(2,2,2,2,2) S Sg2g2 =(3,3,3,3,3) =(3,3,3,3,3)11n（n3）阶梵塔问题v n阶梵塔问题的操作集合表示为：阶梵塔问题的操作集合表示为

8、： F=RF=Rk k(i,j) | i,j=1,2,3(i,j) | i,j=1,2,3，k=1k=1，2 2，nnv 全部可能状态数为全部可能状态数为3n个，最佳解长度为个，最佳解长度为2n-1。v 三阶梵塔问题状态图三阶梵塔问题状态图S S0 0=(1,1,1)=(1,1,1)S Sg2g2=(3,3,3)=(3,3,3)S Sg1g1=(2,2,2)=(2,2,2)概念2：与或树（与或图）表示法v 分解：一分解：一个复杂的问题个复杂的问题P P常常可以分解为与之等价的一组常常可以分解为与之等价的一组子问题子问题P P1 1， P P2 2 ， P Pn n，当这些问题全部可解时，问题可

9、当这些问题全部可解时，问题可解；任何一个子问题无解时，都将导致原问题解；任何一个子问题无解时，都将导致原问题P P无解。即无解。即一个问题与一组子问题的一个问题与一组子问题的与等价与等价。v 等价变换：等价变换：一一个复杂的问题个复杂的问题P P常常可以分别归约为与之等常常可以分别归约为与之等价的一组子问题价的一组子问题P P1 1， P P2 2 ， P Pn n，其中任何一个子问题可其中任何一个子问题可解时，问题可解；全部子问题无解时，原问题解时，问题可解；全部子问题无解时，原问题P P无解。即无解。即一个问题与一组子问题的一个问题与一组子问题的或等价或等价。概念2：与或树（与或图）表示法

10、概念2：与或树（与或图）表示法v 与或图的几个概念与或图的几个概念 直接可解的问题称为直接可解的问题称为本原问题。本原问题。 本原问题对应的节点称为本原问题对应的节点称为终止节点。终止节点。 无子节点的节点称为无子节点的节点称为端节点。端节点。 子节点为与关系，则该节点为子节点为与关系，则该节点为与节点。与节点。 子节点为或关系，则该节点为子节点为或关系，则该节点为或节点。或节点。v 与或图一般表示问题的变换过程，就是从原问题出发，运与或图一般表示问题的变换过程，就是从原问题出发，运用某些规则不断的进行问题的用某些规则不断的进行问题的分解分解（得到（得到与分支与分支）和）和变换变换（得到（得到

11、或分支或分支），而得到一个与或图，与或图的节点一般），而得到一个与或图，与或图的节点一般代表问题，整个图就表示问题空间。代表问题，整个图就表示问题空间。二、状态空间的搜索策略v广度（广度）搜索策略广度（广度）搜索策略v深度搜索策略深度搜索策略v有界深度优先策略有界深度优先策略v代价代价树的广度优先策略树的广度优先策略v代价代价树的深度优先策略树的深度优先策略v启发式搜索启发式搜索vA*算法算法161.1 回溯策略v例：皇后问题例：皇后问题QQQQ17( )18( )Q(1,1)19( )QQ(1,1)(1,1) (2,3)20( )Q(1,1)(1,1) (2,3)21( )QQ(1,1)(1

12、,1) (2,3)(1,1) (2,4)22( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)23( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)24( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)25( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)26( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)27( )(1,1)(1,1) (2,3)(1

13、,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)28( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)29( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)Q(1,2) (2,4) (3,1) (4,3)30回溯搜索算法OPEN表表 CLOSED表表 OPEN表用于存放刚生成的节点，表用于存放刚生成的节点，CLOSED表用于存

14、放将要扩展或者已经扩展的节点。表用于存放将要扩展或者已经扩展的节点。状态节点父节点编号状态节点父节点31一般回溯搜索算法1.把初始节点把初始节点S0放入放入OPEN表，并建立目前只包含表，并建立目前只包含S0的图，记的图，记为为G;2.检查检查OPEN表是否为空，若为空则问题无解，退出表是否为空，若为空则问题无解，退出;3.把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表，并记该节点表，并记该节点为节点为节点n;4. 考察节点考察节点n是否为目标节点，若是，则求得了问题的解，退是否为目标节点，若是，则求得了问题的解，退出出;5.扩展节点扩展节点n，生成一组子节点。把其中不

15、是节点，生成一组子节点。把其中不是节点n先辈的那些先辈的那些子节点记作集合子节点记作集合M，并把这些子节点作为节点，并把这些子节点作为节点n的子节点加入的子节点加入G中中;6.针对针对M中子节点的不同情况，分别进行如下处理：中子节点的不同情况，分别进行如下处理：32一般回溯搜索算法（续）v 6.1 对于那些未曾在对于那些未曾在G中出现过的中出现过的M成员设置一个指向成员设置一个指向父节点（即节点父节点（即节点n）的指针，并把它们放入）的指针，并把它们放入OPEN表。表。v 6.2 对于那些先前已经在对于那些先前已经在G中出现过的中出现过的M成员，确定是成员，确定是否需要修改它指向父节点的指针。

16、否需要修改它指向父节点的指针。v 6.3 对于那些先前已经在对于那些先前已经在G中出现并且已经扩展了的中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。成员，确定是否需要修改其后继节点指向父节点的指针。v 7. 按某种搜索策略对按某种搜索策略对OPEN表中的节点进行排序。表中的节点进行排序。v 8. 转第转第2步。步。思考题1：v如何理解状态空间的一般搜索过程？如何理解状态空间的一般搜索过程？34存在问题及解决办法v解决办法：解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题351.2 图搜索策略v问题的引出问题的引出 回溯

17、搜索：只保留从初始状态到当前状态的一条路径。 图搜索：保留所有已经搜索过的路径。36一些基本概念v节点深度：节点深度：根节点深度根节点深度=0其它节点深度其它节点深度=父节点深度父节点深度+1012337一些基本概念（续1）v路径路径设一节点序列为设一节点序列为(n0, n1,nk)，对于，对于i=1,k，若节点，若节点ni-1具有一个后继节点具有一个后继节点ni，则，则该序列称为从该序列称为从n0到到nk的路径。的路径。v路径的耗散值路径的耗散值一条路径的耗散值等于连接这条路径各节点间所一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用有耗散值的总和。用C(ni, nj)表示从表示

18、从ni到到nj的路的路径的耗散值。径的耗散值。38一些基本概念（续1）v扩展一个节点扩展一个节点生成该节点的所有后继节点，并给出它们之间生成该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为的耗散值。这一过程称为“扩展一个节点扩展一个节点”。39401.3 无信息图搜索过程v广度优先搜索广度优先搜索v深度优先搜索深度优先搜索广度优先搜索4142深度优先搜索1, 把初始节点把初始节点S0放入放入OPEN表表;2, 如果如果OPEN表为空，则问题无解，退出表为空，则问题无解，退出;3, 把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表表;4,

19、 考察节点考察节点n是否为目标节点，若是，则求得了问题的解，退是否为目标节点，若是，则求得了问题的解，退出出;5, 若节点若节点n不可扩展，则转第不可扩展，则转第2步步;6, 扩展节点扩展节点n，将其子节点放入到，将其子节点放入到OPEN表的首部，并为其表的首部，并为其配置指向父节点的指针，然后转第配置指向父节点的指针，然后转第2步步;4344有界深度优先搜索1, 把初始节点把初始节点S0放入放入OPEN表中，置表中，置S0的深度的深度d(S0)=0;2, 如果如果OPEN表为空，则问题无解，退出表为空，则问题无解，退出;3, 把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取

20、出放入）取出放入CLOSED表表;4, 考察节点考察节点n是否为目标节点，若是，则求得了问题的解，退是否为目标节点，若是，则求得了问题的解，退出出;5, 如果节点如果节点n的深度的深度d(节点节点n)=dm，则转第，则转第2步；步；6, 若节点若节点n不可扩展，则转第不可扩展，则转第2步步;7, 扩展节点扩展节点n，将其子节点放入到，将其子节点放入到OPEN表的首部，并为其表的首部，并为其配置指向父节点的指针，然后转第配置指向父节点的指针，然后转第2步步;4546代价树（图）v在上面的讨论中，都没有考虑搜索的代价问题，在上面的讨论中，都没有考虑搜索的代价问题，当时假设图中各边的代价都相同，且都

21、为一个单当时假设图中各边的代价都相同，且都为一个单位量。位量。v边上标有代价（或费用）的树（图）称为代价树边上标有代价（或费用）的树（图）称为代价树（图）。（图）。v在代价树中，若用在代价树中，若用g(x)表示从初始节点表示从初始节点S0到节到节点点x的代价，用的代价，用c(x1,x2)表示从父节点表示从父节点x1到节点到节点x2的代价，则有：的代价，则有：vg(x2)=g(x1) + c(x1,x2)广度优先搜索4748广度优先搜索广度优先搜索1, 把初始节点S0放入OPEN表;2, 如果OPEN表为空，则问题无解，退出;3, 把OPEN表的第一个节点（记为节点n） 取出放入CLOSED表中

22、;4, 考察节点n是否为目标节点，若是，则求得了问题的解，退出;5, 若节点n不可扩展，则转第2步;6, 扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置父节点的指针，然后转第2步。49代价树代价树的广度优先搜索的广度优先搜索1, 把初始节点S0放入OPEN表，令g(S0)=0;2, 如果OPEN表为空，则问题无解，退出;3, 把OPEN表的第一个节点（记为节点n） 取出放入CLOSED表中;4, 考察节点n是否为目标节点，若是，则求得了问题的解，退出;5, 若节点n不可扩展，则转第2步;6, 扩展节点n，将其子节点放入OPEN表中，并为其配置父节点的指针；计算各子节点的代价

23、，并按各节点的代价对OPEN表中的全部节点进行排序（按从小到大的顺序），然后转第2步。举例：交通图举例：交通图A A城是出发地，城是出发地，E E是目的地，数字表示两城是目的地，数字表示两城之间交通费用。求之间交通费用。求A A到到E E的的最小费用最小费用的旅行路线的旅行路线。50广度优先搜索代价树的深度优先搜索5253代价树的深度优先搜索1, 把初始节点把初始节点S0放入放入OPEN表表;2, 如果如果OPEN表为空，则问题无解，退出表为空，则问题无解，退出;3, 把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表表;4, 考察节点考察节点n是

24、否为目标节点，若是，则求得了问题的解，退是否为目标节点，若是，则求得了问题的解，退出出;5, 若节点若节点n不可扩展，则转第不可扩展，则转第2步步;6, 扩展节点扩展节点n，将其子节点按边代价从小到大的顺序放到，将其子节点按边代价从小到大的顺序放到OPEN表的首部，并为各子节点配置指向父节点的指针，表的首部，并为各子节点配置指向父节点的指针，然后转第然后转第2步步;举例：交通图举例：交通图A A城是出发地，城是出发地，E E是目的地，数字表示两城是目的地，数字表示两城之间交通费用。求之间交通费用。求A A到到E E的的最小费用最小费用的旅行路线的旅行路线。54广度优先搜索1010101056深

25、度优先搜索的性质v一般不能保证找到最优解一般不能保证找到最优解v当深度限制不合理时，可能找不到解，可以将算当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制法改为可变深度限制v最坏情况时，搜索空间等同于穷举最坏情况时，搜索空间等同于穷举v与回溯法的差别：图搜索与回溯法的差别：图搜索v是一个通用的与问题无关的方法是一个通用的与问题无关的方法57渐进式深度优先搜索方法v属于有界深度搜索的一种。属于有界深度搜索的一种。v目的目的 解决广度优先方法的空间问题和回溯方法不能找到最优解的问题。v思想思想首先给回溯法一个比较小的深度限制，然后逐渐首先给回溯法一个比较小的深度限制，然后逐渐增加深度限

26、制，直到找到解或找遍所以分支为止。增加深度限制，直到找到解或找遍所以分支为止。581.4 启发式图搜索v利用知识来引导搜索，达到减少搜索范围，降低利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。问题复杂度的目的。v启发信息的强度启发信息的强度 强：降低搜索工作量，但可能导致找不到最 优解 弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解59希望：v引入启发知识，在保证找到最佳解的情况下，引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。尽可能减少搜索范围，提高搜索效率。60基本思想v定义一个评价函数定义一个评价函数f，对当前的搜索状态进

27、行评估，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。找出一个最有希望的节点来扩展。611，启发式搜索算法A（A算法）v评价函数评价函数f(x)的格式：的格式：f(x) = g(x) + h(x) g (x)：从初始节点S0到节点x的实际付出的代价 h(x)：从节点x到目标节点Sg的最优路径估计的代价 f(x)表示从初始节点S0经过节点x到目标节点Sg的代价估计值。62局部择优搜索1, 把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0);2, 如果如果OPEN表为空，则问题无解，退出表为空，则问题无解，退出;3, 把把OPEN表的第一个节点（记为节点表的第一个节点（记

28、为节点n）取出放入）取出放入CLOSED表表;4, 考察节点考察节点n是否为目标节点，若是，则求得了问题的解，退是否为目标节点，若是，则求得了问题的解，退出出;5, 若节点若节点n不可扩展，则转第不可扩展，则转第2步步;6, 扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，计算每个子节点的估价值，并按估价值从小到大的顺序依次放到并按估价值从小到大的顺序依次放到OPEN表的首部，为表的首部，为每个子节点配置指向父节点的指针，然后转第每个子节点配置指向父节点的指针，然后转第2步。步。63局部择优搜索与深度优先搜索的关系v深度优先搜索、代价树的深度优先搜索以及局深度优先搜索

29、、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的。部择优搜索都是以子节点作为考察范围的。v若令若令f(x)g(x)，则局部择优搜索就成为代，则局部择优搜索就成为代价树的深度优先搜索；若令价树的深度优先搜索；若令f(x)d(x)(这里这里d(x)表示节点表示节点x的深度），则局部择优搜索就的深度），则局部择优搜索就成为深度优先搜索。所以深度优先搜索和代价成为深度优先搜索。所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个树的深度优先搜索可看作局部择优搜索的两个特例。特例。64全局择优搜索1, 把初始节点把初始节点S0放入放入OPEN表，计算表，计算f(S0);2, 如

30、果如果OPEN表为空，则问题无解，退出表为空，则问题无解，退出;3, 把把OPEN表的第一个节点（记为节点表的第一个节点（记为节点n）取出放入）取出放入CLOSED表表;4, 考察节点考察节点n是否为目标节点，若是，则求得了问题的解，退出是否为目标节点，若是，则求得了问题的解，退出;5, 若节点若节点n不可扩展，则转第不可扩展，则转第2步步;6, 扩展节点扩展节点n，用估价函数，用估价函数f(x)计算每个子节点的估价值，并为每个子节计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送入点配置指向父节点的指针，把这些子节点都送入OPEN表中，然后对表中，然后对OPEN表中

31、的全部节点按估价值从小到大的顺序进行排序表中的全部节点按估价值从小到大的顺序进行排序7, 转第转第2步。步。65全局择优搜索与广度优先搜索的关系v在全局择优搜索中，若令在全局择优搜索中，若令f(x)g(x)，则全局，则全局择优搜索就成为代价树的广度优先搜索；若令择优搜索就成为代价树的广度优先搜索；若令f(x)d(x)(这里这里d(x)表示节点表示节点x的深度），则的深度），则全局择优搜索就成为广度优先搜索。所以广度优全局择优搜索就成为广度优先搜索。所以广度优先搜索和代价树的广度优先搜索可看作全局择优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例。搜索的两个特例。作业题v用用C+，完成

32、，完成12皇后问题的求解。要求显示每皇后问题的求解。要求显示每种求解的皇后位置坐标。提供代码和结果。种求解的皇后位置坐标。提供代码和结果。中国农业大学信息与电气工程学院2 最佳图搜索算法A*（A*算法）69702 最佳图搜索算法A*（A*算法）v 如果使一般搜索过程满足如下条件，则它成为如果使一般搜索过程满足如下条件，则它成为A*算法：算法：v 1. 把把OPEN表中的节点按估价函数：表中的节点按估价函数：v f(x)=g(x)+h(x) 的值从小到大进行排序（一般搜索过程的第的值从小到大进行排序（一般搜索过程的第 7步）步）v 2. g(x)是对是对g*(x)的估计，的估计，g(x)0.v

33、3. h(x)是对是对h*(x)的下界，即对所有的的下界，即对所有的x均有：均有：h(x)h*(x)其中其中g*(x) 是从初始节点是从初始节点S0到节点到节点x的最小代价；的最小代价； h*(x) 是从节点是从节点x到目标节点的最小代价，若有多个目标节点，则到目标节点的最小代价，若有多个目标节点，则为其中的最小值。为其中的最小值。71A*算法的性质v A*算法的假设算法的假设 设设ni、nj是任意两个节点，有：是任意两个节点，有： C(ni, nj) ，其中，其中 为大于为大于0的常数。的常数。v 几个等式几个等式 1. f*(s) = f*(t) = h*(s) = g*(t) = f*(

34、n) 其中其中s是初始节点，是初始节点，t是目标节点，是目标节点，n是是s到到t的最佳路径上的节点。的最佳路径上的节点。 2. 对于最佳路径（对于最佳路径（s, n1, n2, , ni, , t）中的任一节点）中的任一节点ni，均有，均有f(ni)=f*(s)。 3. 对于一条到达对于一条到达t的最佳路径（的最佳路径（s, n1, n2, , ni, ni+1, , t），则针对任一节），则针对任一节点点ni， 路径（路径（s, n1, n2, , ni）也是从）也是从s到达到达ni的最佳路径，即：的最佳路径，即：g*(ni)=g(ni). 证明证明：对任意节点：对任意节点ni， 若（若（s

35、, n1, n2, , ni）不是到达）不是到达ni的最佳路径，即存在路的最佳路径，即存在路径（径（s, n1 , n2 , , ni），使得从），使得从s到达到达ni更近，那么显然路径（更近，那么显然路径（s, n1 , n2 , , ni, ni+1, , t ）也是从）也是从s到达到达t的最佳路径，这与（的最佳路径，这与（s, n1, n2, , ni, ni+1, , t）是从）是从s到达到达t的最佳路径矛盾。的最佳路径矛盾。问题v 什么是图搜索什么是图搜索? 其中，重排其中，重排OPEN表意味着什么，重排的表意味着什么，重排的原则是什么原则是什么?v 广度优先搜索方法中广度优先搜索方

36、法中OPEN表需要按什么方式进行操作表需要按什么方式进行操作A先进后出先进后出 B先进先出先进先出v 有界深度优先搜索方法能够保证在搜索树中找到一条通向有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？目标节点的最短途径吗？v 试比较各种盲目搜索搜索方法的效率，找出影响算法效率试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因的原因v 试比较广度优先搜索、有界深度优先搜索及有序搜索的搜试比较广度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明索效率，并以实例数据加以说明启发式搜索的必要性v 现实的困难迫使人们转而求援于启发式算法。这现实的困难迫使

37、人们转而求援于启发式算法。这种算法的本质是部分地放弃算法种算法的本质是部分地放弃算法“一般化一般化, 通用化通用化”的概念的概念, 把所要解的问题的具体领域把所要解的问题的具体领域 的知识加进的知识加进算法中去算法中去, 以提高算法的效率。以提高算法的效率。 如广度优先法几乎可以用于解一切搜索问题：九宫图(八数码难题), hanoi塔(焚塔问题), 旅行推销员, 华容道, 以至魔方等等。但实际使用时, 效率也许低得惊人, 甚至根本解不出来(例如魔方问题)。 如果我们为每类问题找出一些特殊规则, 和广度优先法配合起来使用, 那结果就可能完全不一样了。启发式搜索的必要性v 根据启发信息根据启发信息

38、, 在生成各种搜索树时可以考虑种种可能的选择在生成各种搜索树时可以考虑种种可能的选择, 如如: 1. 下一步展开哪个节点? 2. 是部分展开还是完全展开? 3. 使用哪个规则(或算子)? 4. 怎样决定舍弃还是保留新生成的节点? 5. 怎样决定舍弃还是保留一棵子树? 6. 怎样决定停止或继续搜索? 7. 如何定义启发函数(评价函数)? 8. 如何决定搜索方向? 由于这些选择的不同由于这些选择的不同, 就得到了不同的启发式算法就得到了不同的启发式算法*解路径如粗线所标左、上、右、下*S、A、B、L、M等为状态空间图中各个节点名, 其后的小括号中数字表示该节点的评价函数f(n)的估计值, 例如S(

39、4)、L(5)等。 * 图中标记节点为被扩的节点, 标记的节点为生成的节点。九宫重排问题搜索效率比较77A*算法的性质（续1）定理定理1.1：对有限图，如果从初始节点对有限图，如果从初始节点s到目标节点到目标节点t有路有路径存在，则算法径存在，则算法A一定成功结束。一定成功结束。78A*算法的性质（续2）引理引理1.1 ：对无限图，若有从初始节点对无限图，若有从初始节点s到目标节点到目标节点t的路径，则的路径，则A*不不结束时，在结束时，在OPEN表中即使最小的一个表中即使最小的一个f值也将增到任意大，值也将增到任意大，或有或有f(n)f*(s)。证明证明：假设：假设A*不终止。设不终止。设e

40、是图中各条边的最小代价，是图中各条边的最小代价，d*(xn)是从是从S0到节点到节点xn的最短路径长度，则显然有：的最短路径长度，则显然有：g*(xn) d*(xn)e，又因为，又因为g(xn) g*(xn)，所以有，所以有g(xn) d*(xn)e。因为。因为h(xn) 0, f(xn) g(xn)，故得到，故得到f(xn) d*(xn)e。由于。由于A*算法不终止，随着搜索的进行，算法不终止，随着搜索的进行， d*(xn)会无限增大，从而使会无限增大，从而使f(xn)也无限增大。最终使得也无限增大。最终使得f(n)f*(s)。而。而f*(s)显然应该是一个有限值，矛盾。显然应该是一个有限值

41、，矛盾。79A*算法的性质（续3）引理引理1.2：在：在A*终止前的每一步终止前的每一步，总是有一个节点，总是有一个节点n，它在，它在OPEN表中，且存在以下属性：表中，且存在以下属性：1.n在最佳路径上。在最佳路径上。2.A*已经发现了到达已经发现了到达n的一条最佳路径。的一条最佳路径。3.f(n)f*(s)。证明证明：用归纳法。在搜索开始时，：用归纳法。在搜索开始时，S在在OPEN表中，它是到达目标表中，它是到达目标的一条最佳路径，的一条最佳路径，A*已经发现了这条路径，而且因为已经发现了这条路径，而且因为f(S)=h(S) h*(S)=f*(S).定理成立。定理成立。假设在节点假设在节点

42、m(m 0) 扩展时引理的结论是正确的，现在证明在节扩展时引理的结论是正确的，现在证明在节点点(m+1)扩展时引理是正确的。扩展时引理是正确的。80A*算法的性质（续4） 设设n是是m个节点扩展后，个节点扩展后，A*发现的一个最佳路径上的假设节点，它在发现的一个最佳路径上的假设节点，它在OPEN上。如果在第（上。如果在第（m+1）步，）步，n没有被选择扩展，没有被选择扩展，n的属性和以前的属性和以前相同，因此证明了归纳步骤。如果相同，因此证明了归纳步骤。如果n被选为扩展点，它的所有后继将被放被选为扩展点，它的所有后继将被放在在OPEN上，他们中至少有一个上，他们中至少有一个np，将会在到达目标

43、的最优路径上（因，将会在到达目标的最优路径上（因为由于假定一个最优路径通过为由于假定一个最优路径通过n，它必须通过它的一个后继）。故，它必须通过它的一个后继）。故A*找找到了到达到了到达np的一条最佳路径，因为如果有到达的一条最佳路径，因为如果有到达np的一条更好路径，那么的一条更好路径，那么这条路径也是到达目标的更好路径（这和我们的假设没有比通过这条路径也是到达目标的更好路径（这和我们的假设没有比通过n到达目到达目标的路径更好的路径相矛盾）。这样，我们让标的路径更好的路径相矛盾）。这样，我们让np称为第称为第m+1步新的步新的n。现在证明现在证明f(np) f*(s). 因为对在一条最佳路径

44、上的节点因为对在一条最佳路径上的节点np，A*已经找到了到达已经找到了到达np的一条最佳的一条最佳路径，我们有：路径，我们有：f(np)=g(np)+h(np)=g*(np)+h(np) g*(np)+h*(np) =f*(np)=f*(s)。81A*算法的性质（续5）定理定理1.2：对无限图，若从初始节点对无限图，若从初始节点s到目标节点到目标节点t有路径有路径存在，则存在，则A*一定成功结束。一定成功结束。证明证明：由引理：由引理1.1，则，则OPEN中所有的中所有的n有有f(n)f*(s)。由引理由引理1.2，在，在A*结束前结束前OPEN表中必存在节点表中必存在节点n，使得，使得f(n

45、) f*(s)。所以如果不结束，将导。所以如果不结束，将导致矛盾。致矛盾。82A*算法的性质（续6）推论推论1.1：OPEN表上任一具有表上任一具有f(n)f*(s)的节点的节点n，最终都将被最终都将被A*选作扩展的节点。选作扩展的节点。证明：由定理证明：由定理1.2知，知，A*一定结束，由一定结束，由A*的结的结束条件，束条件，OPEN表中表中f(t)最小时才结束。而最小时才结束。而f(t) f*(t)=f*(s)。所以，。所以，f(n)f*(s). 而根据引理而根据引理1.2知结束前知结束前OPEN表上一定存在有节点表上一定存在有节点n，且处在最佳路径上，并有且处在最佳路径上，并有f(n)

46、 f*(s)，所以，所以f(n) f*(s) h1(n)，则在具有一条从，则在具有一条从s到到t的路径的的路径的隐含图上，搜索结束时，由隐含图上，搜索结束时，由A2所扩展的每一个节点，所扩展的每一个节点，也必定由也必定由A1所扩展，即所扩展，即A1扩展的节点数至少和扩展的节点数至少和A2一一样多。样多。简写：如果简写：如果h2(n) h1(n) (目标节点除外目标节点除外)，则，则A1扩展的节点数扩展的节点数A2扩展的节点数扩展的节点数87A*算法的性质（续11）v注意：注意： 在定理在定理1.4中，评价指标是中，评价指标是“扩展的节点数扩展的节点数”，也，也就是说，同一个节点无论被扩展多少次

47、，都只计就是说，同一个节点无论被扩展多少次，都只计算一次。算一次。88定理1.4的证明（续12）v使用数学归纳法，对节点的深度进行归纳使用数学归纳法，对节点的深度进行归纳v（1）当）当d(n)0时，即只有一个节点，显然定理时，即只有一个节点，显然定理成立。成立。v（2）设）设d(n)k时定理成立。（归纳假设）时定理成立。（归纳假设）v（3）当）当d(n)=k+1时，用反证法。时，用反证法。v设存在一个深度为设存在一个深度为k1的节点的节点n，被，被A2扩展，但扩展，但没有被没有被A1扩展。而由假设，扩展。而由假设，A1扩展了扩展了n的父节点，的父节点，即即n已经被生成了。因此当已经被生成了。因

48、此当A1结束时，结束时，n将被保留将被保留在在OPEN中。中。89定理1.4的证明（续1）v 因为因为A1没有扩展没有扩展n，所以有：，所以有：f1(n) f*(s) (推论推论1.1)v 即：即：g1(n)+h1(n) f*(s) v 所以：所以： h1(n) f*(s) - g1(n)v 由于由于A2扩展了扩展了n，有，有f2(n) f*(s)（推论（推论1.2）v 即：即： h2(n) f*(s) g2(n) (A)v 另一方面，由于另一方面，由于d(n)=k时，时，A2扩展的节点扩展的节点A1一定扩展，有一定扩展，有 g1(n) g2(n) (因为因为A2的路的路A1均走到了均走到了)

49、v 所以：所以： h1(n) f*(s) - g1(n) f*(s) g2(n) (B)v 比较比较A、B两式，有两式，有 h1(n) h2(n) ，与定理条件矛盾。故定理得证。，与定理条件矛盾。故定理得证。90对h加以限制v定义：一个启发函数定义：一个启发函数h，如果对所有节点，如果对所有节点ni和和nj，其中，其中nj是是ni的子节点，满足的子节点，满足h(ni) - h(nj) c(ni, nj)h(t) = 0或或 h(ni) c(ni, nj) + h(nj) h(t) = 0 则称则称h服从服从一致性条件一致性条件。h(ni)ninjh(nj)c(ni,nj)91h单调的性质v 一致性条件的性质一致性条件的性质：设：设ni和和nj是由是由