第三章搜索策略(ppt)-PracticalReaso

ArtificialIntelligenceSearching:1©GraduateUniversity,ChineseacademyofSciences.人工智能ArtificialIntelligenceArtificialIntelligenceSearching:2©GraduateUniversity,ChineseacademyofSciences.搜索策略ArtificialIntelligenceSearching:3©GraduateUniversity,ChineseacademyofSciences.主要内容•概述•状态空间搜索状态空间的一般搜索过程广度优先搜索深度优先搜索启发式搜索A*算法问题规约搜索博弈ArtificialIntelligenceSearching:4©GraduateUniversity,ChineseacademyofSciences.概述(1)•问题求解AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学。任何问题求解技术都包括两个重要的方面:表示和搜索表示是基本的,搜索必须要在表示的基础上进行。表示关系到搜索的效率。本章讨论的表示主要包括:状态空间表示问题空间表示ArtificialIntelligenceSearching:5©GraduateUniversity,ChineseacademyofSciences.概述(2)1974年，Nilsson归纳出的AI研究的基本问题–知识的模型化和表示–常识性推理、演绎和问题解决–启发式搜索–人工智能系统和语言搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率AI为什么要研究search?–问题没有直接的解法;–需要探索地求解;ArtificialIntelligenceSearching:6©GraduateUniversity,ChineseacademyofSciences.搜索(3)•什么是搜索根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小ArtificialIntelligenceSearching:7©GraduateUniversity,ChineseacademyofSciences.搜索(4)盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解ArtificialIntelligenceSearching:8©GraduateUniversity,ChineseacademyofSciences.状态空间表示法(1)状态空间表示法：用来表示问题及其搜索过程的一种方法状态状态是描述问题求解过程中任一时刻状况的数据结构.23751486{A，B，C，D}（2,3,7,0,5,2,4,8,6）ArtificialIntelligenceSearching:9©GraduateUniversity,ChineseacademyofSciences.状态空间表示法(2)状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间.一般表示为:(S,F,G)S:问题所有的初始状态集合;F:算符集合;G:目标状态集合算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符.状态空间表示法是用“状态”和“算符”表示问题的一种方法状态空间图:状态空间的图式表示,称为状态空间图.其中节点表示状态,有向边(弧)表示算符.ArtificialIntelligenceSearching:10©GraduateUniversity,ChineseacademyofSciences.状态空间表示法(3)•路径–状态序列•搜索–寻找从初始状态到目标状态的路径;S0SgArtificialIntelligenceSearching:11©GraduateUniversity,ChineseacademyofSciences.状态空间表示法（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),S8=(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)ArtificialIntelligenceSearching:12©GraduateUniversity,ChineseacademyofSciences.状态空间表示法（5）•用状态空间表示,首先必须定义状态的描述形式,把问题的一切状态都表示出来,其次定义算符,完成状态的转换•问题的求解过程就是一个把算符不断地作用于状态的过程.如果在使用某个算符后得到的状态就是目标状态,就得到了问题的解.这个解就是从初始状态到目标状态所用算符构成的序列.•算符的一次使用,就使问题由一种状态转变为另一种状态.可能有多个算符序列都可使问题从初始状态变到目标状态,这就得到了多个解.•对任何一个状态,可使用的算符可能不止一个,这样由一个状态所生成的后继状态可能有多个.如何选择下一步的操作,由搜索策略决定.ArtificialIntelligenceSearching:13©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（1）搜索控制策略–不可撤回的控制策略;–试探性控制策略•回溯型•图搜索ArtificialIntelligenceSearching:14©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（2）•不可撤回的控制策略•例：八数码问题•评价函数:f：（规定:评价函数非增）2831647512384765与的差异为4ArtificialIntelligenceSearching:15©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（3）•不可撤回的控制策略283164752831476523184765123847651238476523184765f=4f=3f=3f=0f=1f=21ArtificialIntelligenceSearching:16©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（4）•不可撤回的控制策略283147652831476583214765813247658132476583214765f=3f=3f=3f=3f=3f=313824765f=213824765f=12ArtificialIntelligenceSearching:17©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（5）•不可撤回的控制策略可能无解1258476312384765目标f=2ArtificialIntelligenceSearching:18©GraduateUniversity,ChineseacademyofSciences.搜索控制策略（6）•回溯策略•例：四皇后问题QQQQArtificialIntelligenceSearching:19©GraduateUniversity,ChineseacademyofSciences.()ArtificialIntelligenceSearching:20©GraduateUniversity,ChineseacademyofSciences.()Q((1,1))ArtificialIntelligenceSearching:21©GraduateUniversity,ChineseacademyofSciences.()QQ((1,1))((1,1)(2,3))ArtificialIntelligenceSearching:22©GraduateUniversity,ChineseacademyofSciences.()Q((1,1))((1,1)(2,3))ArtificialIntelligenceSearching:23©GraduateUniversity,ChineseacademyofSciences.()QQ((1,1))((1,1)(2,3))((1,1)(2,4))ArtificialIntelligenceSearching:24©GraduateUniversity,ChineseacademyofSciences.()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))ArtificialIntelligenceSearching:25©GraduateUniversity,ChineseacademyofSciences.()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))ArtificialIntelligenceSearching:26©GraduateUniversity,ChineseacademyofSciences.()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))ArtificialIntelligenceSearching:27©GraduateUniversity,ChineseacademyofSciences.()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))ArtificialIntelligenceSearching:28©GraduateUniversity,ChineseacademyofSciences.()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))ArtificialIntelligenceSearching:29©GraduateUniversity,ChineseacademyofSciences.()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))ArtificialIntelligenceSearching:30©GraduateUniversity,ChineseacademyofSciences.()((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))ArtificialIntelligenceSearching:31©GraduateUniversity,Chine