人工智能中的搜索问题

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/9/16,#,Searching Problems in AI,人工智能中的搜索问题,智能体,的,的初始状,态,态是确,定,定的,智能体当前,状,状态是,否,否为目,标,标状态,是,是可以,检,检测的,智能体的状,态,态空间,是,是离散,的,的,智能体,在,在每个,状,状态可,以,以采取,的,的合法行动和相应后,继,继状态,是,是确定的,环境是,静,静态的,路径的,耗,耗散函,数,数是已,知,知的,什么是,搜,搜索问,题,题,搜索问,题,题：已,知,知智能,体,体的初,始,始状态,和,和目标,状,状态，,求,求解一,个,个行动,序,序列使,得,得智能,体,体能从,初,初始状,态,态转移,到,到目标,状,状态。,如,如果所,求,求序列,可,可以使,得,得总耗,散,散最低,，,，则问,题,题称为,最,最优搜,索,索问题,。,。,几个典,型,型的搜,索,索问题,起始状,态,态：Arad,路径规,划,划问题,目标状,态,态：Bucharest,合法行,动,动与后,继,继的确,定,定性：,与某一,城,城市相,邻,邻的城,市,市才能,成,成为合,法,法后继,状态空,间,间的离,散,散性：,城市是,离,离散的,环境的,静,静态性：,城市的,相,相对位,置,置不会,改,改变,路径的,耗,耗散函,数,数的确,定,定性：,城市之,间,间的距,离,离是已,知,知的,搜索问,题,题：从Arad到Bucharest的路径,最优化,搜,搜索问,题,题：从Arad到Bucharest的最短,路,路径,几个典,型,型的搜,索,索问题,起始状,态,态,8-Puzzle问题,目标状,态,态,合法行,动,动与后,继,继的确,定,定性：,只有空,格,格四周,的,的格子,是,是可以,移,移动的,状态空,间,间的离,散,散性：,8个格子,的,的排列,方,方式是,离,离散的,环境的,静,静态性：,九宫格,的,的大小,和,和形状,在,在格子,移,移动过,程,程中不,会,会改变,路径的,耗,耗散函,数,数的确,定,定性：,相邻两,个,个状态,之,之间所,需,需步骤,为,为1,搜索问,题,题：从,起,起始状,态,态到目,标,标状态,的,的移动,方,方法,最优化,搜,搜索问,题,题：从,起,起始状,态,态到目,标,标状态,步,步骤最,少,少的移,动,动方法,华容道,是,是不是,一,一个搜,索,索问题,？,？,几个典,型,型的搜,索,索问题,八皇后,问,问题,合法行,动,动与后,继,继的确,定,定性：,满足棋,盘,盘上所,有,有皇后,不,不能互,相,相攻击,的,的后继,才,才是合,法,法的,状态空,间,间的离,散,散性：,0-8个皇后,在,在棋盘,上,上的摆,放,放方式,环境的,静,静态性：,棋盘的,格,格局和,大,大小不,会,会改变,路径的,耗,耗散函,数,数的确,定,定性：,相邻两,个,个状态,之,之间所,需,需步骤,为,为1,搜索问,题,题：求,出,出（所,有,有）合,法,法的目,标,标状态,起始状,态,态：空的,棋,棋盘,目标状,态,态：棋盘,上,上摆了,八,八个皇,后,后，并,且,且任意,两,两个皇,后,后都不,能,能互相,攻,攻击。,目,目标状,态,态不确,定,定，但,是,是当前,状,状态是,否,否为目,标,标状态,是,是可以,检,检测的,。,。,搜索问,题,题的组,成,成,初始状,态,态：智能,体,体所处,的,的初始,状,状态,后继函,数,数：输入,给,给定状,态,态，可,以,以输出,合,合法行,动,动和相,应,应的后,继,继状态,目标测,试,试：用来,确,确定给,定,定的状,态,态是否,为,为目标,状,状态,路径耗,散,散函数：在两,个,个给定,状,状态之,间,间进行,转,转移所,需,需的“,代,代价”,普通搜,索,索问题,：,：求出,一,一条从,初,初始状,态,态到目,标,标状态,之,之间的,行,行动序,列,列,全局搜,索,索问题,：,：求出,所,所有从,初,初始状,态,态到目,标,标状态,之,之间的,行,行动序,列,列,最优化,搜,搜索问,题,题：求,出,出从初,始,始状态,到,到目标,状,状态之,间,间耗散,最,最少的,行,行动序,列,列,搜索问,题,题的求,解,解,所有搜,索,索过程,都,都可以,用,用搜索,树,树算法,来,来进行,表,表示,搜索树,搜索问,题,题的求,解,解,搜索树,实,实例,搜索问,题,题的求,解,解,搜索树,实,实例,搜索问,题,题的求,解,解,搜索树,实,实例,搜索问,题,题的求,解,解,节点与状态的,区,区别,节点（Node）是一,种,种数据,结,结构，,每,每个节,点,点的信,息,息包括,当,当前状,态,态、父,节,节点、,子,子节点,、,、深度,和,和路径,耗,耗散,状态（State）只是,一,一种系,统,统可能,存,存在的,形,形式,不同节,点,点包含,的,的状态,可,可能是,相,相同的,搜索问,题,题的求,解,解,完备性：当问,题,题有解,时,时，这,个,个算法,是,是否保,证,证能找,到,到一个,解,解？,最优性：这个,搜,搜索策,略,略是否,能,能找到,最,最优解,？,？,时间复,杂,杂度：找一,个,个解需,要,要花费,多,多长时,间,间？,空间复,杂,杂度：在执,行,行搜索,过,过程中,需,需要多,少,少内存,？,？,普通搜,索,索问题,：,：求出,一,一条从,初,初始状,态,态到目,标,标状态,之,之间的,行,行动序,列,列,全局搜,索,索问题,：,：求出,所,所有从,初,初始状,态,态到目,标,标状态,之,之间的,行,行动序,列,列,最优化,搜,搜索问,题,题：求,出,出从初,始,始状态,到,到目标,状,状态之,间,间耗散,最,最少的,行,行动序,列,列,搜索策,略,略的性,能,能,搜索问,题,题的求,解,解,无信息,的,的搜索,策,策略：无法,知,知道当,前,前状态,离,离目标,状,状态的,“,“远近,”,”或者,不,不利用,类,类似的,先,先验信,息,息来进,行,行搜索,的,的策略,广度优,先,先搜索,（,（BFS，Breadth-first search）,代价一,致,致搜索,（,（UCS，Uniform-costsearch）,深度优,先,先搜索,（,（DFS，Depth-firstsearch）,深度有,限,限搜索,（,（Depth-limited search）,迭代深,入,入搜索,（,（Iterativedeepening search）,有信息的,（,（启发,式,式）搜,索,索策略：利用,启,启发式,信,信息来,进,进行搜,索,索的策,略,略,贪婪最,佳,佳优先,搜,搜索（Greedybestfirstsearch）,A*搜索,（,（A*search）,搜索策,略,略的分,类,类,不同搜,索,索策略,的,的区别,仅,仅在于,扩,扩展节,点,点的顺,序,序,无信息,的,的搜索,策,策略,广度优,先,先搜索,先被访,问,问的节,点,点先进,行,行扩展,每次扩,展,展深度,最,最浅的节点,可以用,一,一个先,进,进先出,的,的数据,结,结构来,保,保存待,扩,扩展节,点,点序列,C,B,D,E,C,F,G,D,E,D,G,E,F,C,D,E,D,E,F,G,无信息,的,的搜索,策,策略,代价一,致,致搜索,累积路,径,径耗散,最,最小的,节,节点先,被,被扩展,倘若每,一,一步的,耗,耗散都,为,为正，,则,则保证,可,可以得,到,到最优,解,解,若单步,耗,耗散相,等,等，该,算,算法和,广,广度优,先,先搜索,一,一样,C,B,D,E,？,？,？,C,D,E,？,为累积,路,路径耗,散,散最小,的,的节点,无信息,的,的搜索,策,策略,深度优,先,先搜索,后被访,问,问的节,点,点先进,行,行扩展,每次扩,展,展深度最深的,节,节点,“一条,路,路走到,黑,黑”，,对,对于无,边,边界搜,索,索问题,无,无法保,证,证完备,性,性,可以用,一,一个后,进,进先出,的,的数据,结,结构来,保,保存待,扩,扩展节,点,点序列,无信息,的,的搜索,策,策略,深度优,先,先搜索,C,B,E,D,D,I,H,C,E,C,E,D,C,E,I,H,无信息,的,的搜索,策,策略,深度优,先,先搜索,C,H,I,C,E,C,E,I,C,E,I,H,E,I,C,E,无信息,的,的搜索,策,策略,深度有限搜索,深度优,先,先搜索,它,它可能,错,错误地,选,选择一,条,条分支,并,并且沿,着,着一条,很,很长的,（,（甚至,是,是无限,的,的）路,径,径一直,走,走下去,对于无,边,边界的,搜,搜索问,题,题，可,以,以通过,对,对深度,优,优先搜,索,索提供,一,一个预,先,先设定,的,的深度,限,限制m来防止,深,深度优,先,先搜索,进,进入死,循,循环,如果目,标,标深度d深度限,制,制m，深度,有,有限搜,索,索可能,无,无法得,到,到解，,因,因此完,备,备性也,无,无法保,证,证,无信息,的,的搜索,策,策略,迭代深,入,入搜索,用来寻,找,找最合,适,适的深,度,度限制,的,的通用,策,策略，,经,经常和,深,深度优,先,先搜索,结,结合使,用,用,不断增,大,大深度,限,限制，,直,直到找,到,到目标,节,节点,结合了,深,深度有,限,限搜索,的,的优点,，,，又保,证,证了完,备,备性，,还,还能保,证,证得到,最,最优解,无信息,的,的搜索,策,策略,迭代深,入,入搜索,无信息,的,的搜索,策,策略,策略之,间,间的比,较,较,为了避,免,免含有,相,相同状,态,态的节,点,点被重,复,复扩展,，,，可以,用,用一个,数,数据结,构,构来记,录,录所有,被,被访问,过,过的节,点,点。如,果,果当前,待,待扩展,节,节点与,某,某个已,访,访问过,的,的节点,对,对应的,状,状态相,同,同的话,，,，则当,前,前节点,将,将不会,被,被扩展,。,。,这时树,搜,搜索（Tree Search）策略,将,将成为,图,图（GraphSearch）策略,启发式搜索策,略,略,最佳搜,索,索策略,最佳优,先,先搜索,的,的通用,思,思想：,用,用一个,评,评价函,数,数f(n,),)来对节,点,点进行,评,评价。,在,在扩展,节,节点的,过,过程中,，,，从候,选,选节点,中,中选择f(n,),)最小的,节,节点来,进,进行扩,展,展。,对于BFS，f(n,),)表示节,点,点深度,；,；对于UCS，f(n,),)表示节,点,点的累,计,计路径,耗,耗散；,对,对于DFS，f(n,),)表示节,点,点深度,的,的负值,很多时,候,候f(n,),)不能真,正,正度量,节,节点的,好,好坏，,因,因此可,以,以考虑,引,引进启,发,发式信,息,息来估,计,计节点,离,离目标,状,状态的,距,距离,启发式,函,函数：,h(n,),)=从节点n到目标,节,节点的,最,最低耗,散,散路径,的,的耗散,估,估计值,启发式搜索策,略,略,贪婪最,佳,佳优先,搜,搜索,评价函,数,数f(n,),)=h,(,(n),在这个,路,路径规,划,划问题,中,中，h(n,),)取为当,前,前城市,离,离目标Bucharest的直线,距,距离,启发式搜索策,略,略,贪婪最,佳,佳优先,搜,搜索,评价函,数,数f(n,),)=h,(,(n),启发式搜索策,略,略,贪婪最,佳,佳优先,搜,搜索,评价函,数,数f(n,),)=h,(,(n),启发式搜索策,略,略,贪婪最,佳,佳优先,搜,搜索,评价函,数,数f(n,),)=h,(,(n),启发式搜索策,略,略,贪婪最,佳,佳优先,搜,搜索,与深度,优,优先搜,索,索一样,，,，它更,倾,倾向于,沿,沿着一,条,条路径,搜,搜索下,去,去直到,目,目标,因为在,扩,扩展节,点,点时没,有,有考虑,累,累计路,径,径耗散,，,，因此,它,它也不,能,能保证,得,得到最,优,优解,如果状,态