第三章搜索策略ppt课件

1、人工智能Artificial Intelligence搜索战略 主要内容概述形状空间搜索形状空间的普通搜索过程广度优先搜索深度优先搜索启发式搜索A*算法问题规约搜索博弈概述(1)问题求解AI中每个研讨领域都有其各自的特点和规律,但就求解问题的过程看,都可笼统为一个问题求解过程。问题求解过程实践上是一个搜索,广义地说,它包含了全部计算机科学。任何问题求解技术都包括两个重要的方面:表示和搜索表示是根本的,搜索必需求在表示的根底上进展。表示关系到搜索的效率。本章讨论的表示主要包括:形状空间表示问题空间表示概述(2)1974年，Nilsson归纳出的AI研讨的根本问题知识的模型化和表示常识性推理、演绎

2、和问题处理启发式搜索人工智能系统和言语搜索是人工智能中的一个根本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运转效率AI为什么要研讨search?问题没有直接的解法;需求探求地求解;搜索(3)什么是搜索根据问题的实践情况不断寻觅可利用的知识,构造出一条代价较少的推理道路,使问题得到圆满处理的过程称为搜索 包括两个方面： - 找到从初始现实到问题最终答案的一条推理途径 - 找到的这条途径在时间和空间上复杂度最小搜索(4)盲目搜索:也称为无信息搜索，即只按预定的控制战略进展搜索,在搜索过程中获得的中间信息不用来改良控制战略启发式搜索: 在搜索中参与了与问题有关的启发性信息,用于指点搜索

3、朝着最有希望的方向进展,加速问题的求解过程并找到最优解形状空间表示法(1)形状空间表示法：用来表示问题及其搜索过程的一种方法形状形状是描画问题求解过程中任一时辰情况的数据构造.23751486A，B，C，D2, 3,7 ,0 , 5, 2, 4, 8, 6形状空间表示法(2)形状空间:由问题的全部形状及一切可用算符所构成的集合称为问题的形状空间.普通表示为: (S, F, G)S:问题一切的初始形状集合; F:算符集合; G:目的形状集合算符: 引起形状中某些分量发生变化, 从而使问题由一个形状变为另一个形状的操作称为算符.形状空间表示法是用“形状和“算符表示问题的一种方法形状空间图:形状空间

4、的图式表示,称为形状空间图.其中节点表示形状,有向边(弧)表示算符.形状空间表示法(3)途径形状序列搜索寻觅从初始形状到目的形状的途径;S0Sg形状空间表示法4例一:二阶梵塔问题设有三个钢针,在一号钢针上穿有A,B两个金片,A小于B,A位于B的上面.要求把这两个金片全部移到另一个钢针上,而且规定每次只能挪动一片,任何时辰都不能使B位于A的上面设用Sk=(Sk0,Sk1)表示问题的形状,SK0表示金片A所在的钢针号,SK1表示金片B所在的钢针号,全部能够的形状为:S0=(1,1), S1=(1,2), S3=(1,3)S4=(2,1), S5=(2,2), S6=(2,3)S7=(3,1), S

5、8=(3,2), S9=(3,3)问题初始形状集合S=S0,目的形状集合G=S4,S8.算符:A( i,j):表示把金片A从第i号针移到第j号针上B(i,j):表示把B从第i号针移到第j号针上共12个算符:A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2)B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)形状空间表示法5用形状空间表示,首先必需定义形状的描画方式,把问题的一切形状都表示出来,其次定义算符,完成形状的转换问题的求解过程就是一个把算符不断地作用于形状的过程.假设在运用某个算符后得到的形状就是目的形状,

6、就得到了问题的解.这个解就是从初始形状到目的形状所用算符构成的序列.算符的一次运用,就使问题由一种形状转变为另一种形状.能够有多个算符序列都可使问题从初始形状变到目的形状,这就得到了多个解.对任何一个形状,可运用的算符能够不止一个,这样由一个形状所生成的后继形状能够有多个.如何选择下一步的操作,由搜索战略决议.搜索控制战略1搜索控制战略不可撤回的控制战略;试探性控制战略回溯型图搜索搜索控制战略2不可撤回的控制战略例：八数码问题评价函数:f： 规定: 评价函数非增2831647512384765与的差别为4搜索控制战略3不可撤回的控制战略28316475283147652318476512384

7、7651238476523184765f=4f=3f=3f=0f=1f=21搜索控制战略4不可撤回的控制战略283147652831476583214765813247658132476583214765f=3f=3f=3f=3f=3f=313824765f=213824765f=12搜索控制战略5不可撤回的控制战略能够无解1258476312384765目的f=2搜索控制战略6回溯战略例：四皇后问题( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)( )QQ(1,1)(1,

8、1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)(

9、 )(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)QQQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)(1,2) (2,4) (3,1) (4,3)与/或树表示法1根本概念与/或树是用于表示问题及其求解过程的又一种方式化方法.复杂问题的简化方法分解:把一个问题分解到不需再分解或不能再分解为止,然后对每个子问题进展求解,然后把各子问题的解复合起来,就得到原问题的解.等价

10、变换:利用同构或同态的等价变换,把复杂问题转换成假设干个较为容易求解的新问题.假设新问题中有一个可求解,那么就得到了原问题的解.与/或树表示法2例子:三阶梵塔问题设有A,B,C三个金片以及三个钢针,三个金片按自上而下从小到大的顺序穿在1号钢针上,要求把它们全部移到3号钢针上,而且每次只能移到一个金片,任何时候都不能把大的金片压在小的金片上面.用与/或树表示:问题分解(1)为了把三个金片全部移到3号针上,必需先把C移到3号针上(2)为了移到C,必需把A和B移到2号针上(3)当C移到3针后,就可把A和B移到3针上,完成问题求解得到三个子问题(1)把A和B移到2号针的双金片问题(2)把C移到3号针的

11、单金片问题(3)把A和B移到3号针的双金片问题度量问题求解的性能普通搜索战略可以经过下面四个准那么来评价：完备性：假设存在一个解答，该战略能否保证可以找到？时间复杂性：需求多长时间可以找到解答？空间复杂性：执行搜索需求多少存储空间？最优性：假设存在不同的几个解答，该战略能否可以发现最高质量的解答？搜索战略反映了形状空间或问题空间扩展的方法，也决议了形状或问题的访问顺序。在AI领域，形状空间图由初始形状和算子隐含地表示，经常是无限的，它的复杂度根据下面三个值来表达： 分支因子b：任何节点的后继的最大个数最浅的目的节点的深度d形状空间中任何途径的最大长度m主要内容概述形状空间搜索形状空间的普通搜索

12、过程广度优先搜索深度优先搜索启发式搜索A*算法问题规约搜索博弈形状空间搜索过程要点1求解一个可以满足目的条件的问题可以表达为搜索一个图以找到一个满足目的形状描画的节点问题.搜索过程的要点如下:起始节点:对应于初始形状描画后继节点:把适用于某个节点形状描画的一些算符用来推算该节点而得到的新节点,称为该节点的后继节点指针:从每个后继节点前往指向其父辈节点检查各后继节点看能否为目的节点.搜索过程扩展后继节点的次序假设搜索是以接近起始节点的程度(由节点之间连结弧线的数目来衡量)依次扩展节点,称为广(宽)度优先搜索假设搜索时首先扩展最新产生的节点,称为深度优先搜索形状空间搜索过程要点2指针 调整指针扩展

13、一个节点生成出该节点的一切后继节点。弧的费用有一条弧衔接ni和nj两个节点, 用C(ni, nj)表示运用规那么从ni到nj的费用(耗散值)。 玉泉路-天安门途径的耗散值一条途径的耗散值等于衔接这条途径各节点间一切耗散值的总和。用C(ni, nj)表示从ni到nj的途径的耗散值。形状空间的普通搜索过程1主要数据构造OPEN表:存放刚生成的节点,是还未扩展的节点.普通是端节点.CLOSED表:存放将要扩展或已扩展的节点.或者是已被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点形状空间的普通搜索过程2(1)把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G(2)检查OPEN

14、表能否为空,假设为空那么问题无解,退出(3)把OPEN表的第一个节点取出放入CLOSED表,记该节点为n(4)调查n能否为目的节点.如是,那么问题得解,退出(5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些节点记作集合M,并把这些子节点作为节点n的子节点参与G中(6)针对M中子节点的不同情况,分别进展处置对于那些未曾在G中出现过的M成员设置一个指向父节点(即n)的指针,并把它们放入OPEN表对于那些先前已在G中出现过的M成员,确定能否需求修正它指向父节点的指针对于那些先前已在G中出现并且曾经扩展了的M成员,确定能否需求修正其后继节点指向父节点的指针(7)按某种搜索战略对OPEN表中的

15、节点进展排序(8)转第(2)步例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 2S13451,2,3 S 3,1,2 S OPENCLOSES 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,4,6,8,1,12,13

16、2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的节点修正指针2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,

17、5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点修正指针2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 6

18、76,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点(8)的后裔(10)修正指针形状空间的普通搜索过程(3)注:这是一个通用的搜索过程,后面讨论的形状空间各种搜索战略都是其特例.各种搜索战略的主要区别就是对OPEN表中节点排序准那么不同算法终了后，将生成一个图G，称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，

19、称为搜索树。 从目的节点开场，将指针指向的形状回串起来，即找到一条解途径.树/不修正指针; 图/修正指针;修正指针:找最优解 形状空间的普通搜索过程(4)搜索图2S134567891011121314形状空间的普通搜索过程(5)搜索树112S1324567891011121314广度优先搜索1搜索过程如下:(1)把初始节点S0放入OPEN表(2)假设OPEN表为空,那么问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)调查节点n能否为目的节点.假设是,那么求得了问题的解,退出(5)假设节点n不可扩展,那么转第(2)步(6)扩展节点n,将其子节点放入OPEN

20、表的尾部,并为每一个子节点都配置指向父节点的指针,转第(2)步2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目的82 3 41 8 7 6 54广度优先搜索2Complete? Yes (假设 b 是有

21、限的)Time? 1+b+b2+b3+ +bd + b(bd-1) = O(bd+1)Space? O(bd+1)Optimal? Yes (假设每步代价为1)空间是大问题(和时间相比)特点缺陷当目的节点间隔初始节点较远时会产生许多无用的节点,搜索效率低优点只需问题有解,那么总可以得到解,而且是最短途径的解深度优先搜索1搜索过程如下:(1)把初始节点S0放入OPEN表(2)假设OPEN表为空,那么问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)调查节点n能否为目的节点.假设是,那么求得了问题的解,退出(5)假设节点n不可扩展,那么转第(2)步(6)扩展节

22、点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 5

23、2 81 4 37 6 52 8 31 4 57 623456789abcd1 2 3 8 47 6 5目的深度优先搜索2Complete? No: 当空间为无限深度时Time? O(bm): 假设 m 比d大很多那么比较严重Space? O(bm), 线性空间Optimal? No特点缺陷假设目的节点不在搜索所进入的分支上,而该分支又是一个无穷分支,那么就得不到解.因此该算法是不完备的优点假设目的节点不在搜索所进入的分支上,那么可以较快地得到解有界深度优先搜索定义搜索深度的界限dm,当搜索深度到达了深度界限,而尚未出现目的节点时,就换一个分支进展搜索搜索过程如下:(1)把初始节点S0放入OP

24、EN表,置S0的深度d(S0)=0(2)假设OPEN表为空,那么问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)调查节点n能否为目的节点.假设是,那么求得了问题的解,退出(5)假设节点n的深度d(节点n)=dm,那么转第(2)步(6)假设节点n不可扩展,那么转第(2)步(7)扩展节点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步迭代加深搜索1对于有界深度搜索战略，有下面几点需求阐明： 1在有界深度搜索算法中，深度限制dm是一个很重要的参数。 2深度限制dm不能太大。 3有界深度搜索的主要问题是深度限制值dm的选取

25、。 问题：但是对很多问题，我们并不知道该值究竟为多少，直到该问题求解完成了，才可以确定出深度限制dm。迭代加深搜索2改良方法-迭代加深搜索算法 ：先恣意给定一个较小的数作为dm，然后按有界深度算法搜索，假设在此深度限制内找到了解，那么算法终了；如在此限制内没有找到问题的解，那么增大深度限制dm，继续搜索。 迭代加深搜索是一种逃避选择最优深度限制问题的战略，它是试图尝试一切能够的深度限制：首先深度为0，然后深度为1，然后为2，等等，不断进展下去。 问题：迭代加深搜索看起来会很浪费，由于很多节点都要扩展多次。 迭代加深搜索3迭代加深搜索4迭代加深搜索5迭代加深搜索6迭代加深搜索6深度为d，分支因子

26、为b的深度优先搜索生成的节点数为：NDLS = b0 + b1 + b2 + + bd-2 + bd-1 + bd 深度为d，分支因子为b的迭代加深搜索生成的节点数为NIDS = (d+1)b0 + d b1 + (d-1)b2 + + 3bd-2 +2bd-1 + 1bd 对于 b = 10, d = 5,NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456添加 = (123,456 - 111,111)/111,111

27、= 11%迭代加深搜索7Complete? YesTime? (d+1)b0 + d b1 + (d-1)b2 + + bd = O(bd)Space? O(bd)Optimal? Yes, 假设每步代价为1代价树的广度优先搜索边上标有代价(或费用)的树称为代价树g(x)表示从初始节点S0到节点x的代价,c(x1,x2)表示从父节点x1到子节点x2的代价,那么有 g(x2)=g(x1)+c(x1,x2)搜索过程如下:把初始节点S0放入OPEN表,令g(S0)=0假设OPEN表为空,那么问题无解,退出把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表调查节点n能否为目的节点.假设是,

28、那么求得了问题的解,退出假设节点n不可扩展,那么转第(2)步扩展节点n,将其子节点放入OPEN表中,并为每一个子节点都配置指向父节点的指针;计算各子节点的代价,并按各节点的代价对OPEN表中全部节点进展排序(按从小到大的顺序),然后转第(2)步代价树的深度优先搜索搜索过程如下:把初始节点S0放入OPEN表假设OPEN表为空,那么问题无解,退出把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表调查节点n能否为目的节点.假设是,那么求得了问题的解,退出假设节点n不可扩展,那么转第(2)步扩展节点n,将其子节点按边代价从小到大的顺序放入OPEN表的首部,并为每一个子节点都配置指向父节点的

29、指针,然后转第(2)步启发式搜索1前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身的特性信息,在决议要被扩展的节点时,都没有思索该节点在解的途径上的能够性有多大,它能否有利于问题求解以及求出的解能否为最优启发式搜索要用到问题本身的某些特性信息,以指点搜索朝着最有希望的方向前进启发信息的强度强：降低搜索任务量，但能够导致找不到最优解弱：普通导致任务量加大，极限情况下变为盲目搜索，但能够可以找到最优解启发式搜索2启发性信息和估价函数用于指点搜索过程,且与详细问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数.记为 f(x) = g(x) + h(x)g(x)为从初始节点

30、S0到节点x曾经实践付出的代价h(x)是从节点x到目的节点Sg的最优途径的估价代价,表达了问题的启发性信息,称为启发函数f(x)表示从初始节点经过节点x到达目的节点的最优途径的代价估价值,其作用是用来评价OPEN表中各节点的重要性,决议其次序启发式搜索3例：八数码问题，评价函数f(n) = d(n) + W(n)d(n): 节点n的深度;W(n):与目的相比, 错位的数字数目;1238476528316475初始形状目的形状 2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 3

31、1 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目的123456启发式搜索4启发式就是要猜测：从节点n开场，找到最优解的能够性有多大？ 从起始节点开场，经过节点n，到达目的节点的最正确途径的费用是多少？ gh部分择优搜索(瞎子爬山法)1搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)假设OPEN表为空,那

32、么问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)调查节点n能否为目的节点.假设是,那么求得了问题的解,退出(5)假设节点n不可扩展,那么转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步部分择优搜索(瞎子爬山法)2爬山法的三个问题：部分最大： 高地：也称为平顶，在某一部分点周围f(x)为常量。此时，搜索就无法确定要搜索的最正确方向，会产生随机走动，这使得搜索效率降低。 山脊：山脊能够具有峻峭的斜面，所以搜索可以比较容易地到达山脊的

33、顶部，但是山脊的顶部到山峰之间能够倾斜的很平缓。除非正好有适宜的操作符直接沿着山脊的顶部挪动，该搜索能够会在山脊的两面来回震荡，搜索的前提高伐会很小。全局择优搜索(有序搜索/最好优先)搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)假设OPEN表为空,那么问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)调查节点n能否为目的节点.假设是,那么求得了问题的解,退出(5)假设节点n不可扩展,那么转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并为每一个子节点都配置指向父节点的指针,把这些子节点都送入OPEN表,然后

34、对OPEN表中的全部节点按估价值从小到大的顺序进展陈列(7)转第(2)步A*算法1将形状空间普通搜索过程进展如下的限制,就是A*算法把OPEN表中的节点按估价函数 f(x) = g(x) + h(x)的值从小到大进展排序g(x)是对g*(x)的估价,g(x)0h(x)是h*(x)的下界,即对一切的x, h(x)=h*(x)其中: g*(x)是从初始节点S0到节点x的最小代价 h*(x)是从节点x到目的节点的最小代价,假设有多个目的节点,那么为 其中最小的一个nSg*(n)h*(n) gA*算法2f*(S)f*(S) = g*(S)+h*(S) = h*(S)从S无约束地到达目的的最正确路经上的

35、耗散值;g(n)普通取实践走过的途径的费用和.g(n) g*(n)随着算法的执行，由于指针的变动，g(n)会下降. h0没有启发式信息;A*算法38数码问题h(n) = “不在位的将牌数h(n) = 将牌“不在位的间隔和2 8 31 6 47 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：2A*算法4A*算法5宽度优先: 当问题为单位耗散值，且问题有解时，一定能找到最优解;f(n) = g(n) + h(n)g(n)h(n) = 0 h*(n)A*算法可纳性对于可解形状图(即从初始节点到目的节点有途径存在)所说,假设一个搜索算法能在有限步内终止,并且能找到最优解,那么称该搜索

36、算法是可纳的. 定理:A*算法是可纳的,即在有限步内终止,并且找到最优解证明思绪对于有限图,A*算法一定会在有限步内终止对应无限图,只需从初始节点到目的节点有途径存在,A*算法也必然终止A*算法一定终止在最优途径上A*算法的最优性和单调性最优性A*算法的搜索效率在很大程度上取决于h(x),在满足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所携带的启发性信息越多,搜索时所扩展的节点数越少,搜索效率就越高单调性限制单调性限制是指h(x)满足如下两个条件h(Sg)=0设xj是节点xi 的恣意子节点,那么有 h(xi)-h(xj)=c(xi,xj) 其中:Sg是目的节点,c(xi,xj

37、)是节点xi到子节点xj的边代价A*算法的h(x)满足单调性限制时,可有下面的结论假设A*算法选择节点xn进展扩展,那么g(xn)=g*(x)由A*算法所扩展的节点序列其f值是非递减的主要内容概述形状空间搜索形状空间的普通搜索过程广度优先搜索深度优先搜索启发式搜索A*算法问题规约搜索博弈问题规约搜索(1)问题归约法是不同于形状空间法的另一种问题描画和求解的方法。 启发式搜索可以运用的第二个问题是AND-OR图的反向推理问题。AND-OR图的反向推理过程可以看作是一个问题归约过程，即是说在问题求解过程中，将一个大的问题变换成假设干个子问题，子问题又可以分解成更小的子问题，这样不断分解到可以直接求

38、解为止，全部子问题的解就是原问题的解。并称原问题为初始问题，可直接求解的问题为本原问题 问题规约搜索(2)问题归约的描画 :普通说来，问题归约可以用三元组表示：S0，O，P，其中S0是初始问题，即要求解的问题。P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、知现实等，或已证明过的问题。 O是操作算子集，它是一组变换规那么，经过一个操作算子把一个问题化成假设干个子问题。这样，问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样不断进展到产生的问题均为本原问题，那么问题得解。问题规约搜索(3)将问题求解归约为AND-OR图

39、搜索时，将初始节点表示初始问题描画，对应于本原问题的节点称为叶节点。在AND-OR图上执行的搜索过程，其目的在于阐明起始节点是有解的，AND-OR图中一个可解节点可递归地定义如下： 1叶节点是可解节点。 2假设某节点为或子节点，那么该节点可解当且仅当至少有一个子节点为可解节点。 3假设某节点为与子节点，那么该节点可解当且仅当一切子节点均为可解节点。不可解节点可递归定义如下： 1没有后裔节点的非叶节点是不可解节点； 2或节点是不可解节点，当且仅当它的一切子节点都是不可解节点； 3与节点是不可解节点，当且仅当它的子节点中至少有一个是不可解节点。能导致初始节点可解的那些可解节点及有关连线组成的子图称

40、为该AND-OR图的解图。问题规约搜索(4)对OR图搜索，假设搜索到某个节点n时，不论n能否生成了后继节点，n的费用是由其本身形状决议的，但对于AND-OR图不同，其费用计算规那么为：n未生成后继节点，那么费用由n本身决议；n曾经生成了后继节点，那么费用由n的后继节点的费用决议。问题规约搜索(5)问题规约搜索(6)问题规约搜索(7)主要内容概述形状空间搜索形状空间的普通搜索过程广度优先搜索深度优先搜索启发式搜索A*算法问题规约搜索博弈博弈1博弈问题也称为对抗搜索,是由假设干行为主体参与的竞争性智能活动.如下棋,打牌等等.和普通搜索相比，解答是对对手能够走的每一步都给出本人的战略。这里讨论的问题

41、是最简单的又最具代表性的“二人零和,全信息,非偶尔博弈,有弈双方的利益是完全对立的:(1)对垒的A,B双方轮番采取行动,博弈的结果只能有三种情况:A胜,B败;A败,B省;和局(2)在对垒过程中,任何一方都了解当前的格局和过去的历史(3)任何一方在采取行动前都要根据当前的实践情况,进展得失分析,选择对本人最为有利而对对方最不利的对策,不存在“碰运气的偶尔要素.即双方都很明智地决议本人的行动.博弈(2)博弈问题是一种特殊的与/或树问题,它具有如下的特点:博弈的初始格局是初始节点在博弈树中,“或和“与节点是逐层交替出现的.本人一方扩展的节点之间是“或关系,对方扩展的节点之间是“与关系.双方轮番扩展节点所用能使本人一方获胜的结局都是本原问题,相应的节点是可解节点;所用使对方获胜的结局都是不可解节点.博弈中的优化决策(1)博弈问题普通难以求解:游戏要求在即使无法计算出最优决策的情况下也能做出某种决策的才干博弈问题可以定义为下述搜索问题：初始形状：包括棋盘的局面和确定该哪个玩家出招后继函数：前往move 招数,state形状对的列表，其中每一对表示一个合法的招数及其结果形状终止函数：测试博弈能否终了