第1章搜索问题

1、第一章 搜索问题1狼、羊、白菜游戏2野人过河游戏3第一章 搜索问题n内容内容: 状态空间的搜索问题。状态空间的搜索问题。n搜索方式搜索方式: q盲目搜索盲目搜索q启发式搜索启发式搜索n关键问题关键问题: 如何利用知识如何利用知识, 尽可能有效地找到问题的解尽可能有效地找到问题的解(最佳解最佳解)。4n人类的思维过程人类的思维过程, 可以看作是一个搜索的过程。可以看作是一个搜索的过程。从小学到现在从小学到现在, 你一定遇到过很多种的智力游戏你一定遇到过很多种的智力游戏问题问题, 比方说在前面介绍的传教士和野人问题。比方说在前面介绍的传教士和野人问题。如果你来做这个智力游戏的话如果你来做这个智力游

2、戏的话, 在每一次渡河之在每一次渡河之后后, 都会有几种渡河方案供你选择都会有几种渡河方案供你选择, 究竟哪种方究竟哪种方案才有利于在满足题目所规定的约束条件下顺利案才有利于在满足题目所规定的约束条件下顺利过河呢？经过反复努力和试探过河呢？经过反复努力和试探, 你终于找到了一你终于找到了一种解决办法。在高兴之余种解决办法。在高兴之余, 你马上可能又会想到你马上可能又会想到, 这个方案所用的步骤是否最少？也就是说它是最这个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是优的吗？如果不是, 如何才能找到最优的方案？如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实在计算机上又

3、如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。际上就是本章我们要介绍的搜索问题。 5n学习目标学习目标q掌握回溯搜索算法掌握回溯搜索算法, 深度优先搜索算法深度优先搜索算法, 宽度优先宽度优先搜索算法和搜索算法和A(A*)搜索算法搜索算法, 对典型问题对典型问题, 掌握启发掌握启发式函数的定义方法。式函数的定义方法。n学习指南学习指南q了解算法的每一个过程和细节问题了解算法的每一个过程和细节问题, 掌握一些重要掌握一些重要的定理和结论的定理和结论, 在有条件的情况下在有条件的情况下, 程序实现每一程序实现每一个算法个算法, 求解一些典型的问题。求解一些典型的问题。n难重点难重

4、点q回溯搜索算法回溯搜索算法, A*算法及其性质算法及其性质, 改进的改进的A*算法。算法。6状态空间表示法n人工智能的多个研究领域从求解现实问题的过人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个程来看，都可抽象为一个“问题求解问题求解”过程过程n问题求解过程实际上就是一个问题求解过程实际上就是一个“搜索过程搜索过程”n为了进行搜索，首先必须用某种形式把问题表为了进行搜索，首先必须用某种形式把问题表示出来示出来n“状态空间表示法状态空间表示法”就是用来表示问题及其搜就是用来表示问题及其搜索过程的一种方法索过程的一种方法7状态空间表示法n状态空间表示法是用状态空间表示法是用“状态

5、状态”和和“算子算子”来表来表示问题的一种方法示问题的一种方法q状态状态：用来描述问题求解过程中不同时刻的状况：用来描述问题求解过程中不同时刻的状况q算子算子：表示对状态的操作，算子的每次使用就使问：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态题由一种状态变换为另一种状态q当达到目标状态时，由初始状态到目标状态所用算当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解子的序列就是问题的一个解8状态空间表示法n状态状态q状态是描述问题求解过程中任一时刻状况的数据结构状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示，一般用一组变量的

6、有序组合表示: S(s0,s1,)，si是是状态的分量状态的分量q当给每一分量以确定的值时，就得到一个具体的状态当给每一分量以确定的值时，就得到一个具体的状态SK(SK0,SK1,)n算子算子q引起状态中某些分量发生变化，从而使问题由一个状引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子每一条产生式规则就是一个算子9状态空间表示法（续）n状态空间状态空间q由问题的全部状态及一切可用算符所构成的集合称为由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示

7、问题的状态空间，一般用三元组表示: (S0,F,Sg)nS0: 所有初始状态构成的集合所有初始状态构成的集合nF: 算子的集合算子的集合nSg: 目标状态的集合目标状态的集合10例子:Hanoi Towern二阶二阶hanoi towerqSK=(SK0,SK1)表示问题的状态，表示问题的状态，SK0 表示盘片表示盘片A所在所在的柱号，的柱号，SK1 表示盘片表示盘片B所在的柱号所在的柱号q全部可能的状态全部可能的状态:nS0=(1,1), S1=(1,2), S2=(1,3),nS3=(2,1), S4=(2,2), S5=(2,3),nS6=(3,1), S7=(3,2), S8=(3,3

8、).q问题的初始状态集合问题的初始状态集合S=S0,目标集合为目标集合为G=S4,S8q算子分别用算子分别用A(i,j), B(i,j)表示表示nA(i,j):盘片盘片A从柱从柱i移到柱移到柱jnB(i,j):盘片盘片B从柱从柱i移到柱移到柱jq全部可能的算子：全部可能的算子：nA(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2), nB(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2) 11121314状态空间表示法n首先必须定义首先必须定义状态状态的描述形式，通过使用这种描述可把问的描述形式，通过使用这种描述可

9、把问题的一切状态都表示出来。其实还要定义一组题的一切状态都表示出来。其实还要定义一组算子算子，通过，通过使用算子可把问题由一种状态转变为另一种状态使用算子可把问题由一种状态转变为另一种状态n问题的求解过程就是一个不断把算子作用于状态的过程问题的求解过程就是一个不断把算子作用于状态的过程n算子的一次使用，就使问题由一种状态转变为另一种状态算子的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算子序列都可使问题从初始状态变到目标状。可能有多个算子序列都可使问题从初始状态变到目标状态，这就得到了多个解，我们把使用态，这就得到了多个解，我们把使用算子最少的解称为最算子最少的解称为最优解优解n对

10、于任何一种状态，可使用的算子可能不止一个，这样由对于任何一种状态，可使用的算子可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于行操作呢？这取决于搜索策略搜索策略，不同搜索策略的操作顺序，不同搜索策略的操作顺序是不相同的。是不相同的。15搜索技术n搜索技术是人工智能的基本技术之一搜索技术是人工智能的基本技术之一, 在人工在人工智能各应用领域中被广泛地使用。智能各应用领域中被广泛地使用。q早期的人工智能程序与搜

11、索技术联系就更为紧密，几乎所有的早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦艾伦纽厄尔纽厄尔)和和HASimon(西蒙西蒙)等人编写的等人编写的LT(Logic Theorist)程序程序, J.Slagle写的符号积分程序写的符号积分程序SAINT, ANewell和和HASimon写的写的GPS(General Problem Solver)程序程序, HGelernter(格伦特尔格伦特尔)写的写的Geometry theorem-proving machine程序程序

12、, R.Fikes(菲克斯菲克斯)和和N.Nilsson(尼尔逊尼尔逊)写的写的STRIPS(Stanford Research Institute Problem Solver)程序程序以及以及A.Samuel(塞缪尔塞缪尔)写的写的Chechers程序等程序等, 都使用了各种都使用了各种搜索技术。搜索技术。q现在现在, 搜索技术渗透在各种人工智能系统中搜索技术渗透在各种人工智能系统中, 可以说没有哪一种可以说没有哪一种人工智能的应用不用搜索方法，在专家系统、自然语言理解、人工智能的应用不用搜索方法，在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛自动程序设计

13、、模式识别、机器人学、信息检索和博弈都广泛使用搜索技术。使用搜索技术。16搜索技术n 搜索问题是搜索问题是AI核心理论问题之一核心理论问题之一q一般一个问题可以用好几种搜索技术解决一般一个问题可以用好几种搜索技术解决, 选择一选择一种好的搜索技术对解决问题的效率很有关系种好的搜索技术对解决问题的效率很有关系, 甚至甚至关系到求解问题有没有解。关系到求解问题有没有解。q搜索方法好的标准搜索方法好的标准, 一般认为有两个：一般认为有两个：n(1)搜索空间小搜索空间小;n(2)解最佳。解最佳。 17搜索技术n 搜索从搜索从问题性质问题性质上来看上来看, 可分为可分为一般搜索一般搜索和和博博奕搜索奕搜

14、索, 从从处理方法处理方法上来看上来看, 可分为可分为盲目搜索盲目搜索和和启发式搜索，启发式搜索，还可以分得更细。还可以分得更细。q当所给定的问题用状态空间表示时当所给定的问题用状态空间表示时, 则求解过程可则求解过程可归结为对状态空间的搜索。归结为对状态空间的搜索。q当问题有解时当问题有解时, 使用不同的搜索策略使用不同的搜索策略, 找到解的搜索找到解的搜索空间范围是有区别的。一般来说空间范围是有区别的。一般来说, 对大空间问题对大空间问题, 搜搜索策略是要解决组合爆炸的问题。索策略是要解决组合爆炸的问题。18搜索问题(续1)S0Sg19搜索问题(续2)n讨论的问题讨论的问题: q有哪些常用

15、的搜索算法。有哪些常用的搜索算法。q问题有解时能否找到解。问题有解时能否找到解。q找到的解是最佳的吗？找到的解是最佳的吗？q什么情况下可以找到最佳解？什么情况下可以找到最佳解？q求解的效率如何？求解的效率如何？20搜索策略n 通常搜索策略的主要任务是确定如何选取规则的通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式方式。有两种基本方式:q一种是不考虑给定问题所具有的特定知识一种是不考虑给定问题所具有的特定知识, 系统根据事系统根据事先确定好的某种固定排序先确定好的某种固定排序, 依次调用规则或随机调用规依次调用规则或随机调用规则则,这实际上是这实际上是盲目搜索盲目搜索的方法的方法

16、, 一般统称为无信息引导一般统称为无信息引导的搜索策略。的搜索策略。q另一种是考虑问题领域可应用的知识另一种是考虑问题领域可应用的知识, 动态地确定规则动态地确定规则的排序的排序, 优先调用较合适的规则使用优先调用较合适的规则使用, 这就是通常称为这就是通常称为启发式搜索启发式搜索策略或有信息引导的搜索策略。策略或有信息引导的搜索策略。21AI领域的搜索方法n(1)求任一解路的搜索策略求任一解路的搜索策略q回溯法回溯法(Backtracking)q爬山法爬山法(Hill Climbing)q宽度优先法宽度优先法(Breadth-first)q深度优先法深度优先法(Depth-first)q限定

17、范围搜索法限定范围搜索法(Beam Search)q最佳优先法最佳优先法(Best-first)n(2)求最佳解路的搜索策略求最佳解路的搜索策略q大英博物馆法大英博物馆法(British Museum)q分枝界限法分枝界限法(Branch and Bound)q动态规划法动态规划法(Dynamic Programming)q最佳图搜索法最佳图搜索法(A*)22AI领域的搜索方法n(3)求与或关系解图的搜索法求与或关系解图的搜索法q一般与或图搜索法一般与或图搜索法(AO*)q极小极大法极小极大法(Minimax)q剪枝法剪枝法(Alpha-beta Pruning)q启发式剪枝法启发式剪枝法(H

18、euristic Pruning)23搜索策略分类24盲目搜索方法n盲目搜索是不利用问题的有关信息盲目搜索是不利用问题的有关信息, 而根据事而根据事先确定好的某种固定的搜索方法进行搜索。先确定好的某种固定的搜索方法进行搜索。q典型的盲目搜索方法是典型的盲目搜索方法是深度优先深度优先搜索和搜索和宽度优先宽度优先搜搜索索(亦称广度优先搜索亦称广度优先搜索), 这是两种基本搜索方法这是两种基本搜索方法251. 1 回溯策略n回溯策略属于回溯策略属于盲目搜索盲目搜索的一种。所谓回溯策略的一种。所谓回溯策略, 简单地简单地说是这样一种策略说是这样一种策略: 首先将规则给出一个固定的排序首先将规则给出一个

19、固定的排序, 在搜索时在搜索时, 对当前状态对当前状态(搜索开始时搜索开始时, 当前状态是初始状当前状态是初始状态态)依次检测每一条规则依次检测每一条规则, 在当前状态未使用过的规则中在当前状态未使用过的规则中找到第一条可触发规则找到第一条可触发规则, 被应用于当前状态被应用于当前状态, 得到的新状得到的新状态重新设置为当前状态态重新设置为当前状态, 并重复以上搜索。如果当前状并重复以上搜索。如果当前状态无规则可用态无规则可用, 或者所有规则已经被试探过仍未找到问或者所有规则已经被试探过仍未找到问题的解题的解, 则将当前状态的前一个状态则将当前状态的前一个状态(即直接生成该状态即直接生成该状态

20、的状态的状态)设置为当前状态。重复以上搜索设置为当前状态。重复以上搜索, 直到找到问题直到找到问题的解的解, 或者试探了所有可能后仍找不到问题的解为止。或者试探了所有可能后仍找不到问题的解为止。n回溯策略可以有多种实现的方法回溯策略可以有多种实现的方法, 其中用其中用递归法递归法实现也实现也许是最简单的方法了许是最简单的方法了, 本书中给出的就是这种算法。本书中给出的就是这种算法。 26递归的思想从前有座山 从前有座山 从前有座山27Fibonacci数列n1202年，意大利家斐波那契在提出了一个关年，意大利家斐波那契在提出了一个关于兔子繁殖的问题：于兔子繁殖的问题： 如果一对兔子每月能生一对

21、小兔如果一对兔子每月能生一对小兔(一雄一雌一雄一雌)，而每对小兔在它出生後的第三个月里，又能开而每对小兔在它出生後的第三个月里，又能开始生一对小兔，假定在始生一对小兔，假定在不发生死亡的情況下，由一对出生的小兔开始不发生死亡的情況下，由一对出生的小兔开始，50個月后会有多少对兔子？個月后会有多少对兔子？n當當n1時，時，Fn+2 = Fn+1 + Fn，而，而 F0=F1=128一个递归的例子int ListLenght(LIST *pList)if (pList = NULL) return 0; else return ListLength(pList-next)+1; NULLpLIST

22、12329回溯搜索算法BACKTRACK(DATA)DATA: 当前状态。当前状态。返回值返回值: 从当前状态到目标状态的路径从当前状态到目标状态的路径(以规则表的形式表示以规则表的形式表示)或或FAIL。30回溯搜索算法递归过程递归过程BACKTRACK(DATA)nIF TERM(DATA), RETURN NIL; qTERM取真即找到目标取真即找到目标, 则过程返回空表则过程返回空表NIL。nIF DEADEND(DATA), RETURN FAIL; qDEADEND取真取真, 即该状态不合法即该状态不合法, 则过程返回则过程返回FAIL, 必须回溯。必须回溯。nRULES: APP

23、RULES(DATA); qAPPRULES计算计算DATA的可应用规则集的可应用规则集, 依某种原则依某种原则(任意排列或按启发式准则任意排列或按启发式准则)排列后赋给排列后赋给RULES。nLOOP: IF NULL(RULES), RETURN FAIL; qNULL取真取真, 即规则用完未找到目标即规则用完未找到目标, 过程返回过程返回FAIL, 必必须回溯。须回溯。nR: FIRST(RULES); q取头条可应用规则取头条可应用规则31回溯搜索算法nRULES: TAIL(RULES); q删去头条规则删去头条规则, 减少可应用规则表的长度。减少可应用规则表的长度。nRDATA:

24、GEN(R, DATA); q调用规则调用规则R作用于当前状态作用于当前状态, 生成新状态。生成新状态。nPATH: BACKTRACK(RDATA); q对新状态递归调用本过程。对新状态递归调用本过程。nIF PATHFAIL, GO LOOP; q当当PATHFAIL时时, 递归调用失败递归调用失败, 则转移调用另则转移调用另一规则进行测试。一规则进行测试。nRETURN CONS(R, PATH); q过程返回解路径规则表过程返回解路径规则表(或局部解路径子表或局部解路径子表)。32递归的思想331. 1 回溯策略n四皇后问题四皇后问题: 在一个在一个44的国际象棋棋盘上的国际象棋棋盘上

25、, 一次一个一次一个地摆布四枚皇后棋子地摆布四枚皇后棋子, 摆好后要满足每行摆好后要满足每行, 每列和对角线每列和对角线上只允许出现一枚棋子上只允许出现一枚棋子, 即棋子间不许相互俘获。图即棋子间不许相互俘获。图2. 2给出棋盘的几个势态给出棋盘的几个势态, 其中其中a, b满足目标条件满足目标条件, c, d, e为不为不合法状态合法状态, 即不可能构成满足目标条件的中间势态。即不可能构成满足目标条件的中间势态。 34n综合数据库综合数据库: DATAL(表表), L的元素的元素 ij, 1 i, j 4 。DATA非空时非空时, 其表元素表示棋子所其表元素表示棋子所在的行和列。因只有在的行

26、和列。因只有4个棋子个棋子, 故表元素个数最故表元素个数最多为多为4。n上图中上图中a, b分别记为分别记为(12 24 31 43)和和(13 21 34 42), c, d, e分别记为分别记为(11 21), (11 22), (11 23 31)等等。等等。n规则集规则集: if 1 i 4且且Length(DATA)i-1then APPEND (DATA (ij) (1 j 4)共共16条规则条规则, 每条规则每条规则Rij表示满足前提条件下表示满足前提条件下, 在在ij处放一棋子。处放一棋子。 35( )36( )Q(1, 1)37( )QQ(1, 1)(1, 1) (2, 3)

27、38( )Q(1, 1)(1, 1) (2, 3)39( )QQ(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)40( )QQ(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)Q(1, 1) (2, 4) (3, 2)41( )QQ(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)42( )Q(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)43( )(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)44

28、( )(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)Q(1, 2)45( )(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)Q(1, 2)Q(1, 2) (2, 4)46( )(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)47( )(1, 1)(1, 1) (2, 3)(1, 1) (2, 4)(1, 1) (2, 4) (3, 2)Q(1,

29、 2)Q(1, 2) (2, 4)Q(1, 2) (2, 4) (3, 1)Q(1, 2) (2, 4) (3, 1) (4, 3)48一些深入的问题n失败原因分析失败原因分析, 多步回溯多步回溯QQ49一些深入问题(续)n回溯搜索中知识的利用回溯搜索中知识的利用基本思想基本思想(以皇后问题为例以皇后问题为例): 尽可能选取划去对角线上位置数最少的。尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 350回溯算法存在的问题及解决办法n解决办法解决办法: q对搜索深度加以限制对搜索深度加以限制q记录从初始状态到当前状态的路径记录从初始状态到当前状态的路径当前状态当前状态l问题问题: 深度问

30、题深度问题死循环问题死循环问题51回溯搜索算法1BACKTRACK1(DATALIST)DATALIST: 从初始到当前的状态表从初始到当前的状态表(逆向逆向)返回值返回值: 从当前状态到目标状态的路径从当前状态到目标状态的路径(以规则表的形式表示以规则表的形式表示)或或FAIL。52回溯搜索算法11. DATA: =FIRST(DATALIST)2. IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL; 3. IF TERM(DATA) RETURN NIL; 4. IF DEADEND(DATA) RETURN FAIL; 5. IF LENGTH(DAT

31、ALIST)BOUND RETURN FAIL; 6. RULES: =APPRULES(DATA); 7. LOOP: IF NULL(RULES) RETURN FAIL; 8. R: =FIRST(RULES); 53回溯搜索算法1(续)9. RULES: =TAIL(RULES); 10. RDATA: =GEN(R, DATA); 11. RDATALIST: =CONS(RDATA, DATALIST); 12. PATH: =BACKTRCK1(RDATALIST)13. IF PATH=FAIL GO LOOP; 14. RETURN CONS(R, PATH); 541. 2

32、 图搜索策略n问题的引出问题的引出q回溯搜索回溯搜索策略的一个特点就是只保留了从初始状态策略的一个特点就是只保留了从初始状态到当前状态的一条路径到当前状态的一条路径(无论是无论是BACKTRACK还是还是BACKTRACK1都是如此都是如此), 当回溯出现时当回溯出现时, 回溯点处回溯点处进行的搜索将被算法进行的搜索将被算法“忘记忘记”, 其好处是节省了存储其好处是节省了存储空间空间, 而不足是这些被回溯掉的已经搜索过的部分而不足是这些被回溯掉的已经搜索过的部分, 不能被以后使用。不能被以后使用。q与此相对应的与此相对应的, 将所有搜索过的状态都记录下来的搜将所有搜索过的状态都记录下来的搜索方

33、法称为索方法称为图搜索图搜索, 搜索过的路径除了可以重复利搜索过的路径除了可以重复利用外用外, 其最大的优点是可以更有效地利用与问题有关其最大的优点是可以更有效地利用与问题有关的一些知识的一些知识, 从而达到启发式搜索的目的。保留所有从而达到启发式搜索的目的。保留所有已经搜索过的路径。已经搜索过的路径。55一些基本概念n节点深度节点深度: 根节点深度根节点深度=0其它节点深度其它节点深度=父节点深度父节点深度+1012356一些基本概念(续1)n路径路径设一节点序列为设一节点序列为(n0, n1, , nk), 对于对于i=1, , k, 若节点若节点ni-1具有一个后继节点具有一个后继节点n

34、i, 则该序列称为则该序列称为从从n0到到nk的路径。的路径。n路径的路径的耗散值耗散值q一条路径的耗散值等于连接这条路径各节点间所一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用有耗散值的总和。用C(ni, nj)表示从表示从ni到到nj的路径的路径的耗散值。的耗散值。q递归公式递归公式: C(ni, t)C(ni, nj)+C(nj, t)57一些基本概念(续1)n扩展扩展一个节点一个节点生成出该节点的所有后继节点生成出该节点的所有后继节点, 并给出它们之并给出它们之间的耗散值。这一过程称为间的耗散值。这一过程称为“扩展一个节点扩展一个节点”。58一般的图搜索算法1. G=G0

35、 (G0=s), OPEN: =(s); 2. CLOSED: =( ); 3. LOOP: IF OPEN=( ) THEN EXIT(FAIL); 4. n: =FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED); 5. IF GOAL(n) THEN EXIT(SUCCESS); 6. EXPAND(n)mi, G: =ADD(mi, G); 59一般的图搜索算法(续)7. 标记和修改指针标记和修改指针: ADD(mj, OPEN), 并标记并标记mj到到n的指针的指针; 计算是否要修改计算是否要修改mk, ml到到n的指针的指针; 计算是否要修改计

36、算是否要修改ml到其后继节点的指针到其后继节点的指针; 8. 对对OPEN中的节点按中的节点按某种原则某种原则重新排序重新排序; 9. GO LOOP; 60节点类型说明如图所示如图所示, 假设假设n是当是当前被扩展的节点。在前被扩展的节点。在n被扩展之前被扩展之前, 节点节点mk和和ml已经被生成出来已经被生成出来了了, 其中其中mk还没有被还没有被扩展扩展, 他们在他们在OPEN表表中中, 而而ml已经被扩展已经被扩展了了, 他们在他们在CLOSED表中。当表中。当n被扩展时被扩展时, 它生成了节点它生成了节点mi, mi由由mj, mk和和ml三部分三部分组成组成, 其中其中mj是新出是

37、新出现的节点。现的节点。 61修改指针举例123456s62修改指针举例(续1)123456s63123456修改指针举例(续2)s64123456修改指针举例(续3)s651. 3 无信息图搜索过程n深度优先搜索深度优先搜索n宽度优先搜索宽度优先搜索66深度优先搜索1. G: =G0(G0=s), OPEN: =(s), CLOSED: =( ); 2. LOOP: IF OPEN=( ) THEN EXIT (FAIL); 3. n: =FIRST(OPEN); 4. IF GOAL(n) THEN EXIT (SUCCESS); 5. REMOVE(n, OPEN), ADD(n, CL

38、OSED); 6. IF DEPTH(n)Dm GO LOOP; 7. EXPAND(n) mi, G: =ADD(mi, G); 8. IF 目标在目标在mi中中 THEN EXIT(SUCCESS); 9. ADD(mj, OPEN), 并标记并标记mj到到n的指针的指针; 10. GO LOOP; 67深度优先搜索深度优先搜索深度优先搜索, 就是在每次扩展一个节点时就是在每次扩展一个节点时, 选择到目前为选择到目前为止深度止深度最深最深的节点优先扩展。这一点是在算法的第的节点优先扩展。这一点是在算法的第7步体步体现出来的。第现出来的。第7步中的步中的ADD(mj, OPEN)表示将被扩展

39、节点表示将被扩展节点n的所有的所有新子节点新子节点mj加到加到OPEN表的前面表的前面。开始时。开始时, OPEN表中只有一个初始节点表中只有一个初始节点s, s被扩展被扩展, 其子节点被放入其子节点被放入OPEN表中。在算法的第表中。在算法的第3步步, OPEN表的第一个元素表的第一个元素(设为设为n)被取被取出扩展出扩展, 这时节点这时节点n的深度在的深度在OPEN表中是最大的表中是最大的, OPEN表中的其他节点的深度都不会超过表中的其他节点的深度都不会超过n的深度。的深度。n的子节点的子节点被放到被放到OPEN表的最前面。由于子节点的深度要大于父节表的最前面。由于子节点的深度要大于父节

40、点的深度点的深度, 实际上实际上OPEN表是按照节点的深度进行排序的表是按照节点的深度进行排序的, 深度深的节点被排在了前面深度深的节点被排在了前面, 而深度浅的节点被放在了后而深度浅的节点被放在了后面。这样当下一个循环再次取出面。这样当下一个循环再次取出OPEN表的第一个元素时表的第一个元素时, 实际上选择的就是到目前为止深度最深的节点实际上选择的就是到目前为止深度最深的节点, 从而实现从而实现了深度优先的搜索策略。了深度优先的搜索策略。 682 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

41、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 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标69深度优先搜索的性质n一般一般不能保证不能保证找到最优解找到最优解n当深度限制不合理时当深度限制不合理时, 可能找不到解可能找不

42、到解, 可以将算可以将算法改为可变深度法改为可变深度限制限制n最坏情况时最坏情况时, 搜索空间等同于搜索空间等同于穷举穷举n与回溯法的差别与回溯法的差别: 图搜索图搜索n是一个是一个通用通用的与问题无关的方法的与问题无关的方法70渐进式深度优先搜索方法n目的目的q解决宽度优先方法的空间问题和回溯方法不能找到解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。最优解的问题。n思想思想q首先给回溯法一个比较首先给回溯法一个比较小小的深度限制的深度限制, 然后然后逐渐增逐渐增加加深度限制深度限制, 直到找到解或找遍所以分支为止。直到找到解或找遍所以分支为止。71宽度优先搜索宽度优先搜索1. G

43、: =G0(G0=s), OPEN: =(s), CLOSED: =( ); 2. LOOP: IF OPEN=( ) THEN EXIT (FAIL); 3. n: =FIRST(OPEN); 4. IF GOAL(n) THEN EXIT (SUCCESS); 5. REMOVE(n, OPEN), ADD(n, CLOSED); 6. EXPAND(n) mi, G: =ADD(mi, G); 7. IF 目标在目标在mi中中 THEN EXIT(SUCCESS); 8. ADD(OPEN, mj), 并标记并标记mj到到n的指针的指针; 9. GO LOOP; 72宽度优先搜索同深度优

44、先算法一样同深度优先算法一样, 宽度优先算法也是从一般宽度优先算法也是从一般的图搜索算法变化而成。在深度优先搜索中的图搜索算法变化而成。在深度优先搜索中, 每每次选择深度最深的节点首先扩展次选择深度最深的节点首先扩展, 而宽度优先搜而宽度优先搜索则正好相反索则正好相反, 每次选择深度最浅的节点优先扩每次选择深度最浅的节点优先扩展。与深度优先算法不同的只是第展。与深度优先算法不同的只是第7步步, 这里这里ADD(OPEN, mj)表示将表示将mj类子节点放到类子节点放到OPEN表的后边表的后边, 从而实现了对从而实现了对OPEN表中的元素按节表中的元素按节点深度排序点深度排序, 只不过这次将深度

45、浅的节点放在只不过这次将深度浅的节点放在OPEN表的前面了表的前面了, 而深度深的节点被放在了而深度深的节点被放在了OPEN表的后边。当问题有解时表的后边。当问题有解时, 宽度优先算法宽度优先算法不但能一定找到解不但能一定找到解, 而且在而且在单位耗散单位耗散的情况下的情况下, 可以保证找到最优解。可以保证找到最优解。 732 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

46、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 5474宽度优先搜索的性质n当问题有解时当问题有解时, 一定能找到解一定能找到解n当问题为单位耗散值当问题为单位耗散值, 且问题有解时且问题有解时, 一定能找一定能找到到最优解最优解n方法与问题无关方法与问题无关, 具有具有通用性通用性n效率较低效率较低n属于属于图搜索图搜索方法方法751. 4 启发式图搜索n利用知识来引导搜索利用知识来引导搜索, 达到减少搜索范围达到减少搜索范围, 降低降低问

47、题复杂度的目的。问题复杂度的目的。n启发信息的强度启发信息的强度q强强: 降低搜索工作量降低搜索工作量, 但可能导致找不到最但可能导致找不到最 优解优解q弱弱: 一般导致工作量加大一般导致工作量加大, 极限情况下变为极限情况下变为 盲目搜索盲目搜索, 但可能可以找到最优解但可能可以找到最优解76希望: n引入启发知识引入启发知识, 在保证找到最佳解的情况下在保证找到最佳解的情况下, 尽尽可能可能减少搜索范围减少搜索范围, 提高搜索效率提高搜索效率。77基本思想n定义一个定义一个评价函数评价函数f, 对当前的搜索状态进行评对当前的搜索状态进行评估估, 找出一个最有希望的节点来扩展。找出一个最有希

48、望的节点来扩展。781. 启发式搜索算法A(A算法)n评价函数的格式评价函数的格式: f(n) = g(n) + h(n)f(n): 评价函数评价函数h(n): 启发函数启发函数79符号的意义ng*(n): 从从s到到n的最短路径的耗散值的最短路径的耗散值nh*(n): 从从n到到g的最短路径的耗散值的最短路径的耗散值nf*(n)=g*(n)+h*(n): 从从s经过经过n到到g的最短路径的最短路径的耗散值的耗散值ng(n), h(n), f(n)分别是分别是g*(n), h*(n), f*(n)的的估计估计值值80A算法1. OPEN: =(s), f(s): =g(s)+h(s); 2.

49、LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3. n: =FIRST(OPEN); 4. IF GOAL(n) THEN EXIT(SUCCESS); 5. REMOVE(n, OPEN), ADD(n, CLOSED); 6. EXPAND(n) mi, 计算计算f(n, mi): =g(n, mi)+h(mi); 81A算法(续)ADD(mj, OPEN), 标记标记mj到到n的指针的指针; IF f(n, mk)f(mk) THEN f(mk): =f(n, mk), 标记标记mk到到n的指针的指针; IF f(n, ml)f(ml) THEN f(ml): =

50、f(n, ml), 标标记记ml到到n的指针的指针, ADD(ml, OPEN); 7. OPEN中的节点按中的节点按f值值从小到大从小到大排序排序; 8. GO LOOP; 82左图表示出当前要扩展节左图表示出当前要扩展节点点n之前的搜索图之前的搜索图, 扩展扩展n后新生成的子节点后新生成的子节点m1( mj), m2( mk), m3( ml)要分别计算其要分别计算其评价函数值评价函数值: f(m1)=g(m1)+h(m1)f(n, m2)=g(n, m2)+h(m2)f(n, m3)=g(n, m3)+h(m3)83一个A算法的例子定义评价函数定义评价函数: f(n) = g(n) +

51、h(n)g(n)为从初始节点到当前节点的为从初始节点到当前节点的耗散值耗散值h(n)为当前节点为当前节点“不在位不在位”的将牌数的将牌数2 8 31 6 47 51 2 38 47 6 584h计算举例h(n) =4 2 8 31 6 47 51 2 3457 6 885n设评价函数设评价函数f(n)形式如下形式如下: f(n)=d(n)+W(n)q其中其中d(n)代表节点的代表节点的深度深度, 取取g(n)=d(n)表示讨论单表示讨论单位耗散的情况位耗散的情况; 取取h(n)=W(n)表示表示“不在位不在位”的将牌的将牌个数作为启发函数的度量个数作为启发函数的度量, 这时这时f(n)可估计出

52、通向目可估计出通向目标节点的希望程度。下图表示使用这种评价函数时标节点的希望程度。下图表示使用这种评价函数时的搜索树的搜索树, 图中括弧中的数字表示该节点的评价函图中括弧中的数字表示该节点的评价函数值数值f。算法每一循环结束时。算法每一循环结束时, 其其OPEN表和表和CLOSED表的排列如下表的排列如下: 86872 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 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8

53、 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)目标目标12345688n2. 爬山法过程爬山法过程Hill-climbingn: =s; s为初始节点为初始节点LOOP: IF GOAL(n)THEN EXIT (SUCCESS); EXPAND(n)mi, 计算计算h(mi), nextn: =m(min h(mi)的节点的节点); IF h(n) 其中其中 为大于为大于0的常数的常数n几个等式几个等式q f*(s) = f*(t)

54、 = h*(s) = g*(t) = f*(n)q其中其中s是初始节点是初始节点, t是目标节点是目标节点, n是是s到到t的最佳路的最佳路径上的节点。径上的节点。100A*算法的性质(续1)n定理定理1.1: 对有限图对有限图, 如果从初始节点如果从初始节点s到目标到目标节点节点t有路径存在有路径存在, 则算法则算法A一定成功结束。一定成功结束。101证明证明: 设设A搜索失败搜索失败, 则算法在第则算法在第2步结束步结束, OPEN表变空表变空, 而而CLOSED表中的节点是在结束之前被表中的节点是在结束之前被扩展过的节点。由于图有解扩展过的节点。由于图有解, 令令(n0=s, n1, n

55、2, , nk=t)表示某一解路径表示某一解路径, 我们从我们从nk开始逆向逐个检开始逆向逐个检查该序列的节点查该序列的节点, 找到出现在找到出现在CLOSED表中的节表中的节点点ni, 即即ni CLOSED, ni+1 CLOSED(ni一定能一定能找到找到, 因为因为n0 CLOSED, nk CLOSED)。由于。由于ni在在CLOSED中中, 必定在第必定在第6步被扩展步被扩展, 且且ni+1被加被加到到OPEN中中, 因此在因此在OPEN表空之前表空之前, ni+1已被处已被处理过。若理过。若ni+1是目标节点是目标节点, 则搜索成功则搜索成功, 否则它被否则它被加入到加入到CLO

56、SED中中, 这两种情况都与搜索失败的这两种情况都与搜索失败的假设矛盾假设矛盾, 因此对有限图不失败则成功。因此对有限图不失败则成功。证毕证毕 102A*算法的性质(续2)n引理引理1.1: 对无限图对无限图, 若有从初始节点若有从初始节点s到目到目标节点标节点t的路径的路径, 则则A*不结束时不结束时, 在在OPEN表表中即使最小的一个中即使最小的一个f值也将增到任意大值也将增到任意大, 或或有有f(n)f*(s)。103证明n证明：设证明：设d d* *(n)(n)是是A A* *生成的搜索树中，从生成的搜索树中，从s s到任一到任一节点节点n n最短路径长度的值最短路径长度的值( (设每

57、个弧的长度均为设每个弧的长度均为1 1) )，搜索图上每个弧的耗散值为，搜索图上每个弧的耗散值为C(nC(ni i，n ni+1i+1)(C)(C取正取正) )。令。令e=min C(ne=min C(ni i，n ni+1i+1) )，则，则g g* *(n)d(n)d* *(n)e(n)e。而。而g(n)gg(n)g* *(n)d(n)d* *(n)e(n)e，故有：，故有：f(n)=g(n)+h(n)g(n)df(n)=g(n)+h(n)g(n)d* *(n)e(n)e(设设h(n)0)h(n)0) 若若A A* *不结束，不结束，d d* *(n)(n)，f f值将增到任意大。值将增到

58、任意大。n设设M=fM=f* *(s)/e(s)/e，M M是一个定数，所以搜索进行到一是一个定数，所以搜索进行到一定程度会有定程度会有d d* *(n)M(n)M，则，则f(n)df(n)d* *(n)ed(n)ed* *(n)(f(n)(f* *(s)/M)(s)/M) f f* *(s)(s)(d d* *(n)/M(n)/M) f) f* *(s) (s) 104A*算法的性质(续3)l引理引理1.2: A*结束前结束前, OPEN表中必存在表中必存在f(n) f*(s) (n是在最佳路径上的节点是在最佳路径上的节点)。105证明l证明：设从初始节点证明：设从初始节点s到目标节点到目标

59、节点t的一条最佳路的一条最佳路径序列为：径序列为：(n0=s，n1，nk=t)算法初始化时，算法初始化时，s在在OPEN中，由于中，由于A*没有结束，没有结束，在在OPEN中存在最佳路径上的节点。设中存在最佳路径上的节点。设OPEN表表中的某节点中的某节点n是处在最佳路径序列中是处在最佳路径序列中(至少有一个至少有一个这样的节点，因这样的节点，因s一开始是在一开始是在OPEN上上)，显然，显然n的先辈节点的先辈节点np已在已在CLOSED中，因此能找到中，因此能找到s到到np的最佳路径，而的最佳路径，而n也在最佳路径上，因而也在最佳路径上，因而s到到n的最佳路径也能找到，因此有的最佳路径也能找

60、到，因此有f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)而最佳路径上任一节点均有而最佳路径上任一节点均有f*(n)=f*(s)(f*(s)是最佳是最佳路径的耗散值路径的耗散值)，所以，所以f(n)f*(s)。证毕证毕106A*算法的性质(续3)n定理定理1.2: 对无限图对无限图, 若从初始节点若从初始节点s到目标节点到目标节点t有路径存在有路径存在, 则则A*一定成功结束。一定成功结束。证明：证明：q引理引理1.1: A*如果不结束如果不结束, 则则OPEN中所有的中所有的n有有 f(n) f*(s)q引理引理1.2: 在在A*结束前结束前, 必存在节点