搜索
问题求解与博弈汽车防盗器主要内容•状态空间•搜索技术•机器博弈一些例子•搭积木•智力游戏：–有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：•船太小，农夫每次只能带一样东西过河•没有农夫看管，则狼要吃羊，羊要吃菜–请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。•下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）状态空间表示法•人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程•问题求解过程实际上就是一个搜索过程•为了进行搜索，首先必须用某种形式把问题表示出来•状态空间表示法就是用来表示问题及其搜索过程的一种方法状态空间表示法•状态空间表示法是用“状态”和“算子”来表示问题的一种方法–状态：用来描述问题求解过程中不同时刻的状况–算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态–当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解状态空间表示法•状态–状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示–SK(SK0,SK1,…)–当给每一分量以确定的值时，就得到一个具体的状态•算子–引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子•状态空间–由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,G)•S:所有初始状态构成的集合•F:算子的集合•G:目标状态的集合例子:HanoiTower•二阶hanoitower–SK=(SK0,SK1)表示问题的状态，SK0表示盘片A所在的柱号，SK1表示盘片B所在的柱号–全部可能的状态:•S0=(1,1),S1=(1,2),S2=(1,3),•S3=(2,1),S4=(2,2),S5=(2,3),•S6=(3,1),S7=(3,2),S8=(3,3).–问题的初始状态集合S={S0},目标集合为G={S4,S8}–算子分别用A(i,j),B(i,j)表示•A(i,j):盘片A从柱i移到柱j•B(i,j):盘片B从柱i移到柱j–全部可能的算子：•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)状态空间表示法•首先必须定义状态的描述形式，通过使用这种描述可把问题的一切状态都表示出来。其实还要定义一组算子，通过使用算子可把问题由一种状态转变为另一种状态•问题的求解过程就是一个不断把算子作用于状态的过程•算子的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算子序列都可使问题从初始状态变到目标状态，这就得到了多个解，我们把使用算子最少的解称为最优解•对于任何一种状态，可使用的算子可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。搜索技术•搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。–早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦·纽厄尔)和H·A·Simon(西蒙)等人编写的LT(LogicTheorist)程序,J.Slagle写的符号积分程序SAINT,A·Newell和H·A·Simon写的GPS(GeneralProblemSolver)程序,H·Gelernter(格伦特尔)写的Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。–现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。搜索技术•搜索问题是AI核心理论问题之一–一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。–搜索方法好的标准,一般认为有两个：•(1)搜索空间小;•(2)解最佳。搜索技术•搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。–当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。–当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题搜索策略•通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式:–一种是不考虑给定问题所具有的特定知识,系统根据事先确定好的某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索的方法,一般统称为无信息引导的搜索策略。–另一种是考虑问题领域可应用的知识,动态地确定规则的排序,优先调用较合适的规则使用,这就是通常称为启发式搜索策略或有信息引导的搜索策略。AI领域的搜索方法•(1)求任一解路的搜索策略–回溯法(Backtracking)–爬山法(HillClimbing)–宽度优先法(Breadth-first)–深度优先法(Depth-first)–限定范围搜索法(BeamSearch)–最佳优先法(Best-first)•(2)求最佳解路的搜索策略–大英博物馆法(BritishMuseum)–分枝界限法(BranchandBound)–动态规划法(DynamicProgramming)–最佳图搜索法(A*)AI领域的搜索方法•(3)求与或关系解图的搜索法–一般与或图搜索法(AO*)–极小极大法(Minimax)–剪枝法(Alpha-betaPruning)–启发式剪枝法(HeuristicPruning)搜索策略分类盲目搜索方法•盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索。–典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法回溯策略•例：皇后问题–在一个4×4的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获QQQQ()()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,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))()((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))()((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))递归的思想从前有座山……从前有座山……从前有座山……Fibonacci数列•1202年，意大利家斐波那契在提出了一个关于兔子繁殖的问题：如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生後的第三个月里，又能开始生一对小兔，假定在不发生死亡的情況下，由一对出生的小兔开始，50個月后会有多少对兔子？•當n＞1時，Fn+2=Fn+1+Fn，而F0=F1=1。递归的思想（续）当前状态目标状态g回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURNFAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);存在问题及解决办法•问题：–深度问题–死循环问题•解决办法：–对搜索深度加以限制–记录从初始状态到当前状态的路径回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);一些深入的问题•失败原因分析、多步回溯QQ一些深入问题（续）•回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4334图搜索策略•问题的引出–回溯搜索：只保留从初始状态到当前状态的一条路径。–图搜索：保留所有已经搜索过的路径。一些基本概念•节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续1）•路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。•路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。一些基本概念（续1）•扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。图搜索的一般过程•(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。•(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。•(3)LOOP：若OPEN表是空表，则失败退出。•(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。•(5)若