人工智能中的搜索问题3

SearchingProblemsinAI人工智能中的搜索问题智能体的初始形状是确定的智能体当前形状能否为目的形状是可以检测的智能体的形状空间是离散的智能体在每个形状可以采取的合法行动和相应后继形状是确定的环境是静态的途径的耗散函数是知的什么是搜索问题搜索问题：知智能体的初始形状和目的形状，求解一个行动序列使得智能体能从初始形状转移到目的形状。假设所求序列可以使得总耗散最低，那么问题称为最优搜索问题。几个典型的搜索问题起始形状：Arad途径规划问题目的形状：Bucharest合法行动与后继确实定性：与某一城市相邻的城市才干成为合法后继形状空间的离散性：城市是离散的环境的静态性：城市的相对位置不会改动途径的耗散函数确实定性：城市之间的间隔是知的搜索问题：从Arad到Bucharest的途径最优化搜索问题：从Arad到Bucharest的最短途径几个典型的搜索问题起始形状8-Puzzle问题目的形状合法行动与后继确实定性：只需空格周围的格子是可以挪动的形状空间的离散性：8个格子的陈列方式是离散的环境的静态性：九宫格的大小和外形在格子挪动过程中不会改动途径的耗散函数确实定性：相邻两个形状之间所需步骤为1搜索问题：从起始形状到目的形状的挪动方法最优化搜索问题：从起始形状到目的形状步骤最少的挪动方法华容道是不是一个搜索问题？几个典型的搜索问题八皇后问题合法行动与后继确实定性：满足棋盘上一切皇后不能相互攻击的后继才是合法的形状空间的离散性：0-8个皇后在棋盘上的摆放方式环境的静态性：棋盘的格局和大小不会改动途径的耗散函数确实定性：相邻两个形状之间所需步骤为1搜索问题：求出〔一切〕合法的目的形状起始形状：空的棋盘目的形状：棋盘上摆了八个皇后，并且恣意两个皇后都不能相互攻击。目的形状不确定，但是当前形状能否为目的形状是可以检测的。搜索问题的组成初始形状：智能体所处的初始形状后继函数：输入给定形状，可以输出合法行动和相应的后继形状目的测试：用来确定给定的形状能否为目的形状途径耗散函数：在两个给定形状之间进展转移所需的“代价〞普通搜索问题：求出一条从初始形状到目的形状之间的行动序列全局搜索问题：求出一切从初始形状到目的形状之间的行动序列最优化搜索问题：求出从初始形状到目的形状之间耗散最少的行动序列搜索问题的求解一切搜索过程都可以用搜索树算法来进展表示搜索树搜索问题的求解搜索树实例搜索问题的求解搜索树实例搜索问题的求解搜索树实例搜索问题的求解节点与形状的区别节点〔Node〕是一种数据构造，每个节点的信息包括当前形状、父节点、子节点、深度和途径耗散形状〔State〕只是一种系统能够存在的方式不同节点包含的形状能够是一样的搜索问题的求解完备性：当问题有解时，这个算法能否保证能找到一个解？最优性：这个搜索战略能否能找到最优解？时间复杂度：找一个解需求破费多长时间？空间复杂度：在执行搜索过程中需求多少内存？普通搜索问题：求出一条从初始形状到目的形状之间的行动序列全局搜索问题：求出一切从初始形状到目的形状之间的行动序列最优化搜索问题：求出从初始形状到目的形状之间耗散最少的行动序列搜索战略的性能搜索问题的求解无信息的搜索战略：无法知道当前形状离目的形状的“远近〞或者不利用类似的先验信息来进展搜索的战略广度优先搜索〔BFS，Breadth-firstsearch〕代价一致搜索〔UCS，Uniform-costsearch〕深度优先搜索〔DFS，Depth-firstsearch〕深度有限搜索〔Depth-limitedsearch〕迭代深化搜索〔Iterativedeepeningsearch〕有信息的〔启发式〕搜索战略：利用启发式信息来进展搜索的战略贪婪最正确优先搜索〔Greedybestfirstsearch〕A*搜索〔A*search〕搜索战略的分类不同搜索战略的区别仅在于扩展节点的顺序无信息的搜索战略广度优先搜索先被访问的节点先进展扩展每次扩展深度最浅的节点可以用一个先进先出的数据构造来保管待扩展节点序列CBDECFGDEDGEFCDEDEFG无信息的搜索战略代价一致搜索累积途径耗散最小的节点先被扩展倘假设每一步的耗散都为正，那么保证可以得到最优解假设单步耗散相等，该算法和广度优先搜索一样CBDE？？？CDE？为累积途径耗散最小的节点无信息的搜索战略深度优先搜索后被访问的节点先进展扩展每次扩展深度最深的节点“一条路走到黑〞，对于无边境搜索问题无法保证完备性可以用一个后进先出的数据构造来保管待扩展节点序列无信息的搜索战略深度优先搜索CBEDDIHCECEDCEIH无信息的搜索战略深度优先搜索CHICECEICEIHEICE无信息的搜索战略深度有限搜索深度优先搜索它能够错误地选择一条分支并且沿着一条很长的〔甚至是无限的〕途径不断走下去对于无边境的搜索问题，可以经过对深度优先搜索提供一个预先设定的深度限制m来防止深度优先搜索进入死循环假设目的深度d>深度限制m，深度有限搜索能够无法得到解，因此完备性也无法保证无信息的搜索战略迭代深化搜索用来寻觅最适宜的深度限制的通用战略，经常和深度优先搜索结合运用不断增大深度限制，直到找到目的节点结合了深度有限搜索的优点，又保证了完备性，还能保证得到最优解无信息的搜索战略迭代深化搜索无信息的搜索战略战略之间的比较为了防止含有一样形状的节点被反复扩展，可以用一个数据构造来记录一切被访问过的节点。假设当前待扩展节点与某个已访问过的节点对应的形状一样的话，那么当前节点将不会被扩展。这时树搜索〔TreeSearch〕战略将成为图〔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)启发式搜索战略贪婪最正确优先搜索与深度优先搜索一样，它更倾向于沿着一条途径搜索下去直到目的由于在扩展节点时没有思索累计途径耗散，因此它也不能保证得到最优解假设形状空间是无限的，它也能够是不完备的启发式搜索战略A*搜索为了弥补贪婪最正确优先搜索无法找到最优解的缺陷，思索在评价函数里参与累计途径耗散，由此构成A*搜索算法评价函数f(n)=g(n)+h(n)g(n)：从起始节点到节点n的途径耗散h(n)：从节点n到目的节点的最低耗散途径的耗散估计值f(n)：经过节点n到目的节点的总耗散估计值启发式搜索战略A*搜索启发式搜索战略A*搜索启发式搜索战略A*搜索启发式搜索战略