,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2014/9/16,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,2020/6/4,#,Searching Problems in AI,人工智能中的搜索问题,Searching Problems in AI人工智能中的,1,智能体的,初始状态是确定的,智能,体当前状态是否为目标状态是可以检测的,智能,体的状态空间是离散的,智能体在每个状态可以采取的合法,行动和,相应后继状态是,确定的,环境是静态的,路径的耗散函数是已知的,什么是搜索问题,搜索问题：已知智能体的初始状态和目标状态，求解一个行动序列使得智能体能从初始状态转移到目标状态。如果所求序列可以使得总耗散最低，则问题称为最优搜索问题。,智能体的初始状态是确定的什么是搜索问题搜索问题：已知智能体的,2,几个典型的搜索问题,起始状态,：,Arad,路径规划问题,目标状态,：,Bucharest,合法行动与后继的确定性,：,与某一城市相邻的城市才能成为合法后继,状态空间的离散性,：,城市是离散的,环境的静态性,：,城市的相对位置不会改变,路径的耗散函数的确定性,：,城市之间的距离是已知的,搜索问题：从,Arad,到,Bucharest,的路径,最优化搜索问题：从,Arad,到,Bucharest,的最短路径,几个典型的搜索问题起始状态：Arad路径规划问题目标状态：B,3,几个典型的搜索问题,起始状态,8-Puzzle,问题,目标状态,合法行动与后继的确定性,：,只有空格四周的格子是可以移动的,状态空间的离散性,：,8,个格子的排列方式是离散的,环境的静态性,：,九宫格的大小和形状在格子移动过程中不会改变,路径的耗散函数的确定性,：,相邻两个状态之间所需步骤为,1,搜索问题：从起始状态到目标状态的移动方法,最优化搜索问题：从起始状态到目标状态步骤最少的移动方法,华容道是不是一个搜索问题？,几个典型的搜索问题起始状态8-Puzzle问题目标状态合法行,4,几个典型的搜索问题,八皇后问题,合法行动与后继的确定性,：,满足棋盘上所有皇后不能互相攻击的后继才是合法的,状态空间的离散性,：,0-8,个皇后在棋盘上的摆放方式,环境的静态性,：,棋盘的格局和大小不会改变,路径的耗散函数的确定性,：,相邻两个状态之间所需步骤为,1,搜索问题：求出（所有）合法的目标状态,起始状态,：空的棋盘,目标状态,：棋盘上摆了八个皇后，并且任意两个皇后都不能互相攻击。目标状态不确定，但是当前状态是否为目标状态是可以检测的。,几个典型的搜索问题八皇后问题合法行动与后继的确定性：状态空间,5,搜索问题的组成,初始状态,：智能体所处的初始状态,后继函数,：输入给定状态，可以输出合法行动和相应的后继状态,目标测试,：用来确定给定的状态是否为目标状态,路径耗散函数,：在两个给定状态之间进行转移所需的“代价”,普通搜索问题：求出一条从初始状态到目标状态之间的行动序列,全局搜索问题：求出所有从初始状态到目标状态之间的行动序列,最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列,搜索问题的组成初始状态：智能体所处的初始状态普通搜索问题：求,6,搜索问题的求解,所有搜索过程都可以用搜索树算法来进行表示,搜索树,搜索问题的求解所有搜索过程都可以用搜索树算法来进行表示搜索树,7,搜索问题的求解,搜索树实例,搜索问题的求解搜索树实例,8,搜索问题的求解,搜索树实例,搜索问题的求解搜索树实例,9,搜索问题的求解,搜索树实例,搜索问题的求解搜索树实例,10,搜索问题的求解,节点,与,状态的区别,节点（,Node,）是一种数据结构，每个节点的信息包括当前状态、父节点、子节点、深度和路径耗散,状态（,State,）只是一种系统可能存在的形式,不同节点包含的状态可能是相同的,搜索问题的求解节点与状态的区别节点（Node）是一种数据结构,11,搜索问题的求解,完备性,：当问题有解时，这个算法是否保证能找到一个解？,最优性,：这个搜索策略是否能找到最优解？,时间复杂度,：找一个解需要花费多长时间？,空间复杂度,：在执行搜索过程中需要多少内存？,普通搜索问题：求出一条从初始状态到目标状态之间的行动序列,全局搜索问题：求出所有从初始状态到目标状态之间的行动序列,最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列,搜索策略的性能,搜索问题的求解完备性：当问题有解时，这个算法是否保证能找到一,12,搜索问题的求解,无信息的搜索策略,：无法知道当前状态离目标状态的“远近”或者不利用类似的先验信息来进行搜索的策略,广度优先搜索（,BFS,，,Breadth-first search,）,代价一致搜索（,UCS,，,Uniform-cost search,）,深度优先搜索（,DFS,，,Depth-first search,）,深度有限搜索（,Depth-limited search,）,迭代深入搜索（,Iterative deepening search,）,有,信息的（启发式）搜索策略,：利用启发式信息来进行搜索的策略,贪婪最佳优先搜索（,Greedy best first search,）,A,*搜索（,A,*,search,）,搜索策略的分类,不同搜索策略的区别仅在于扩展节点的顺序,搜索问题的求解无信息的搜索策略：无法知道当前状态离目标状态的,13,无信息的搜索策略,广度优先搜索,先被访问的节点先进行扩展,每次扩展深度最浅的,节点,可以用一个先进先出的数据结构来保存待扩展节点序列,C,B,D,E,C,F,G,D,E,D,G,E,F,C,D,E,D,E,F,G,无信息的搜索策略广度优先搜索先被访问的节点先进行扩展CBDE,14,无信息的搜索策略,代价一致搜索,累积路径耗散最小的节点先被扩展,倘若每一步的耗散都为正，则保证可以得到最优解,若单步耗散相等，该算法和广度优先搜索一样,C,B,D,E,？,？,？,C,D,E,？,为累积路径耗散最小的节点,无信息的搜索策略代价一致搜索累积路径耗散最小的节点先被扩展C,15,无信息的搜索策略,深度优先搜索,后被访问的节点先进行扩展,每次扩展深度,最深的节点,“一条路走到黑”，对于无边界搜索问题无法保证完备性,可以用一个后进先出的数据结构来保存待扩展节点序列,无信息的搜索策略深度优先搜索后被访问的节点先进行扩展,16,无信息的搜索策略,深度优先搜索,C,B,E,D,D,I,H,C,E,C,E,D,C,E,I,H,无信息的搜索策略深度优先搜索CBEDDIHCECEDCEIH,17,无信息的搜索策略,深度优先搜索,C,H,I,C,E,C,E,I,C,E,I,H,E,I,C,E,无信息的搜索策略深度优先搜索CHICECEICEIHEICE,18,无信息的搜索策略,深度,有限,搜索,深度优先搜索它可能错误地选择一条分支并且沿着一条很长的（甚至是无限的）路径一直走下去,对于无边界的搜索问题，可以通过对深度优先搜索提供一个预先设定的深度限制,m,来防止深度优先搜索进入死循环,如果目标深度,d,深度限制,m,，深度有限搜索可能无法得到解，因此完备性也无法保证,无信息的搜索策略深度有限搜索深度优先搜索它可能错误地选择一条,19,无信息的搜索策略,迭代深入搜索,用来寻找最合适的深度限制的通用策略，经常和深度优先搜索结合使用,不断增大深度限制，直到找到目标节点,结合了深度有限搜索的优点，又保证了完备性，还能保证得到最优解,无信息的搜索策略迭代深入搜索用来寻找最合适的深度限制的通用策,20,无信息的搜索策略,迭代深入搜索,无信息的搜索策略迭代深入搜索,21,无信息的搜索策略,策略之间的比较,为了避免含有相同状态的节点被重复扩展，可以用一个数据结构来记录所有被访问过的节点。如果当前待扩展节点与某个已访问过的节点对应的状态相同的话，则当前节点将不会被扩展。,这时树搜索（,Tree Search,）策略将成为图（,Graph Search,）策略,无信息的搜索策略策略之间的比较为了避免含有相同状态的节点被重,22,启发式,搜索策略,最佳搜索策略,最佳优先搜索的通用思想：用一个评价函数,f(n),来对节点进行评价。在扩展节点的过程中，从候选节点中选择,f(n),最小的节点来进行扩展。,对于,BFS,，,f(n),表示节点深度；对于,UCS,，,f(n),表示节点的累计路径耗散；对于,DFS,，,f(n),表示节点深度的负值,很多时候,f(n),不能真正度量节点的好坏，因此可以考虑引进启发式信息来估计节点离目标状态的距离,启发式函数：,h(n)=,从节点,n,到目标节点的最低耗散路径的耗散估计值,启发式搜索策略最佳搜索策略最佳优先搜索的通用思想：用一个评价,23,启发式,搜索策略,贪婪最佳优先搜索,评价函数,f(n)=h(n),在这个路径规划问题中，,h(n),取为当前城市离目标,Bucharest,的直线距离,启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n)在这,24,启发式,搜索策略,贪婪最佳优先搜索,评价函数,f(n)=h(n),启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n),25,启发式,搜索策略,贪婪最佳优先搜索,评价函数,f(n)=h(n),启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n),26,启发式,搜索策略,贪婪最佳优先搜索,评价函数,f(n)=h(n),启发式搜索策略贪婪最佳优先搜索评价函数f(n)=h(n),27,启发式,搜索策略,贪婪最佳优先搜索,与深度优先搜索一样，它更倾向于沿着一条路径搜索下去直到目标,因为在扩展节点时没有考虑累计路径耗散，因此它也不能保证得到最优解,如果状态空间是无限的，它也可能是不完备的,启发式搜索策略贪婪最佳优先搜索与深度优先搜索一样，它更倾向于,28,启发式,搜索策略,A,*搜索,为了弥补贪婪最佳优先搜索无法找到最优解的缺点，考虑在评价函数里加入累计路径耗散，由此形成,A,*搜索算法,评价函数,f(n)=g(n)+h(n),g(n),：从起始节点到节点,n,的路径耗散,h,(n),：从节点,n,到目标节点的最低耗散路径的耗散估计值,f,(n),：经过节点,n,到目标节点的总耗散估计值,启发式搜索策略A*搜索为了弥补贪婪最佳优先搜索无法找到最优解,29,启发式,搜索策略,A,*搜索,启发式搜索策略A*搜索,30,启发式,搜索策略,A,*搜索,启发式搜索策略A*搜索,31,启发式,搜索策略,A,*搜索,启发式搜索策略A*搜索,32,启发式,搜索策略,A,*搜索,启发式搜索策略A*搜索,33,启发式,搜索策略,A,*搜索,启发式搜索策略A*搜索,34,启发式,搜索策略,如果,h(n),是,可采纳的（,admissible,）,，即,h(n),从不过高估计节点,n,到目标节点的最低耗散，则基于,A,*搜索策略的树搜索方法（不检查重复节点）是最优的,如果,h(n),是,一致的（,consistent,），,则,基于,A,*搜索策略,的图搜索,方法,（检查,重复节点）是最优的,A,*搜索,启发式搜索策略如果h(n)是可采纳的（admissible）,35,Thanks,Thanks,36,9,、,春去春又回，新桃换旧符。在那桃花盛开的地方，在这醉人芬芳的季节，愿你生活像春天一样阳光，心情像桃花一样美丽，日子像桃子一样甜蜜,。,11月-24,11月-24,Saturday,November 16,2024,10,、,人的志向通常和他们的能力成正比例,。,07:45:50,07:45:50,07:45,11/16/2024 7:45:50 AM,11,、,夫学须志也，才须学也，非学无以广才，非志无以成学,。,11月-24,07:45:50,07:45,Nov-24,16-Nov-24,12,、越是无能的人，越喜欢挑剔别人的错儿。,07:45:50,07:45:50,07:45,Saturday,November 16,2024,