好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

人工智能中得搜索问题.docx

7页
  • 卖家[上传人]:hua****92
  • 文档编号:287444351
  • 上传时间:2022-05-03
  • 文档格式:DOCX
  • 文档大小:18.75KB
  • / 7 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 人工智能中得搜索问题SearchingProblemsinAI(rnnzhnn)中的搜索问题第一页,共三十七页 智能体的初始状态是确定的智能体当前状态是否为目标(mbio)状态是可以检测的智能体的状态空间是离散的智能体在每个状态可以采取的合法行动和相应后继状态是确定的环境是静态的路径的耗散函数是的什么是搜索(susu)问题搜索问题:智能(zhnn)体的初始状态和目标状态,求解一个行动序列使得智能(zhnn)体能从初始状态转移到目标状态 如果所求序列可以使得总耗散最低,则问题称为最优搜索问题 第二页,共三十七页 几个典型(dinxng)的搜索问题起始(qsh)状态:Arad路径规划(guhu)问题目标状态:Bucharest合法行动与后继确实定性:与某一城市相邻的城市才能成为合法后继状态空间的离散性:城市是离散的环境的静态性:城市的相对位置不会改变路径的耗散函数确实定性:城市之间的距离是的搜索问题:从Arad到Bucharest的路径最优化搜索问题:从Arad到Bucharest的最短路径第三页,共三十七页 几个(j)典型的搜索问题起始(qsh)状态8-Puzzle问题(wnt)目标状态合法行动与后继确实定性:只有空格四周的格子是可以移动的状态空间的离散性:8个格子的排列方式是离散的环境的静态性:九宫格的大小和形状在格子移动过程中不会改变路径的耗散函数确实定性:相邻两个状态之间所需步骤为1搜索问题:从起始状态到目标状态的移动方法最优化搜索问题:从起始状态到目标状态步骤最少的移动方法华容道是不是一个搜索问题?第四页,共三十七页。

      几个(j)典型的搜索问题八皇后(hunghu)问题合法行动与后继确实定性:满足(mnz)棋盘上所有皇后不能互相攻击的后继才是合法的状态空间的离散性:0-8个皇后在棋盘上的摆放方式环境的静态性:棋盘的格局和大小不会改变路径的耗散函数确实定性:相邻两个状态之间所需步骤为1搜索问题:求出所有合法的目标状态起始状态:空的棋盘目标状态:棋盘上摆了八个皇后,并且任意两个皇后都不能互相攻击 目标状态不确定,但是当前状态是否为目标状态是可以检测的 第五页,共三十七页 搜索(susu)问题的组成初始状态:智能体所处的初始状态后继函数:输入给定(idn)状态,可以输出合法行动和相应的后继状态目标测试:用来确定给定的状态是否为目标状态路径耗散函数:在两个给定状态之间进行转移所需的“代价普通搜索问题(wnt):求出一条从初始状态到目标状态之间的行动序列全局搜索问题:求出所有从初始状态到目标状态之间的行动序列最优化搜索问题:求出从初始状态到目标状态之间耗散最少的行动序列第六页,共三十七页 搜索(susu)问题的求解所有搜索(susu)过程都可以用搜索(susu)树算法来进行表示搜索(susu)树第七页,共三十七页。

      搜索(susu)问题的求解搜索(susu)树实例第八页,共三十七页 搜索问题(wnt)的求解搜索(susu)树实例第九页,共三十七页 搜索问题(wnt)的求解搜索(susu)树实例第十页,共三十七页 搜索问题(wnt)的求解节点(jidin)与状态的区别节点Node是一种数据结构,每个节点的信息包括当前状态(zhungti)、父节点、子节点、深度和路径耗散状态State只是一种系统可能存在的形式不同节点包含的状态可能是相同的第十一页,共三十七页 搜索(susu)问题的求解完备性:当问题有解时,这个算法是否保证能找到一个解?最优性:这个搜索策略是否能找到最优解?时间复杂度:找一个解需要花费多长时间?空间复杂度:在执行(zhxng)搜索过程中需要多少内存?普通搜索问题:求出一条从初始状态到目标(mbio)状态之间的行动序列全局搜索问题:求出所有从初始状态到目标状态之间的行动序列最优化搜索问题:求出从初始状态到目标状态之间耗散最少的行动序列搜索策略的性能第十二页,共三十七页 搜索问题(wnt)的求解无信息的搜索策略:无法知道当前状态离目标状态的“远近(yunjn)或者不利用类似的先验信息来进行搜索的策略广度优先搜索BFS,Breadth-firstsearch代价一致搜索UCS,Uniform-costsearch深度优先搜索DFS,Depth-firstsearch深度有限搜索Depth-limitedsearch迭代深入搜索Iterativedeepeningsearch有信息的启发式搜索策略:利用启发式信息来进行搜索的策略贪婪最正确优先搜索GreedybestfirstsearchA*搜索A*search搜索策略(cl)的分类不同搜索策略的区别仅在于扩展节点的顺序第十三页,共三十七页。

      无信息的搜索(susu)策略广度优先(yuxin)搜索先被访问的节点先进行扩展每次扩展深度(shnd)最浅的节点可以用一个先进先出的数据结构来保存待扩展节点序列CBDECFGDEDGEFCDEDEFG第十四页,共三十七页 无信息(xnx)的搜索策略代价(diji)一致搜索累积路径耗散最小的节点先被扩展倘若(tngru)每一步的耗散都为正,则保证可以得到最优解若单步耗散相等,该算法和广度优先搜索一样CBDE???CDE?为累积路径耗散最小的节点第十五页,共三十七页 无信息的搜索(susu)策略深度优先(yuxin)搜索后被访问的节点先进行扩展每次扩展深度最深的节点“一条路走到黑,对于无边界搜索问题无法(wf)保证完备性可以用一个后进先出的数据结构来保存待扩展节点序列第十六页,共三十七页 无信息(xnx)的搜索策略深度优先(yuxin)搜索CBEDDIHCECEDCEIH第十七页,共三十七页 无信息(xnx)的搜索策略深度(shnd)优先搜索CHICECEICEIHEICE第十八页,共三十七页 无信息的搜索(susu)策略深度有限(yuxin)搜索深度优先搜索它可能错误地选择一条分支并且沿着一条很长的甚至是无限的路径一直走下去对于无边界的搜索问题,可以通过对深度优先搜索提供一个预先设定的深度限制m来防止深度优先搜索进入死循环如果目标深度d深度限制m,深度有限搜索可能无法得到解,因此(ync)完备性也无法保证第十九页,共三十七页。

      无信息(xnx)的搜索策略迭代(didi)深入搜索用来寻找最适宜的深度限制的通用策略(cl),经常和深度优先搜索结合使用不断增大深度限制,直到找到目标节点结合了深度有限搜索的优点,又保证了完备性,还能保证得到最优解第二十页,共三十七页 无信息的搜索(susu)策略迭代(didi)深入搜索第二十一页,共三十七页 无信息的搜索(susu)策略策略(cl)之间的比较为了(wile)防止含有相同状态的节点被重复扩展,可以用一个数据结构来记录所有被访问过的节点 如果当前待扩展节点与某个已访问过的节点对应的状态相同的话,则当前节点将不会被扩展 这时树搜索TreeSearch策略将成为图GraphSearch策略第二十二页,共三十七页 启发式搜索(susu)策略最正确搜索(susu)策略最正确优先搜索的通用思想:用一个评价函数f(n)来对节点进行评价 在扩展节点的过程中,从候选节点中选择f(n)最小的节点来进行扩展 对于BFS,f(n)表示节点深度;对于UCS,f(n)表示节点的累计路径耗散;对于DFS,f(n)表示节点深度的负值很多时候f(n)不能真正度量节点的好坏,因此可以考虑引进启发式信息来估计节点离目标(mbio)状态的距离启发式函数:h(n)=从节点n到目标节点的最低耗散路径的耗散估计值第二十三页,共三十七页。

      启发式搜索(susu)策略贪婪最正确优先(yuxin)搜索评价(pngji)函数f(n)=h(n)在这个路径规划问题中,h(n)取为当前城市离目标Bucharest的直线距离第二十四页,共三十七页 启发式搜索(susu)策略贪婪(tnln)最正确优先搜索评价(pngji)函数f(n)=h(n)第二十五页,共三十七页 启发式搜索(susu)策略贪婪(tnln)最正确优先搜索评价(pngji)函数f(n)=h(n)第二十六页,共三十七页 启发式搜索(susu)策略贪婪(tnln)最正确优先搜索评价(pngji)函数f(n)=h(n)第二十七页,共三十七页 启发式搜索(susu)策略贪婪最正确(zuji)优先搜索与深度优先搜索一样,它更倾向于沿着一条路径搜索下去直到目标因为在扩展节点时没有考虑累计路径耗散,因此它也不能保证得到(ddo)最优解如果状态空间是无限的,它也可能是不完备的第二十八页,共三十七页 启发式搜索(susu)策略A*搜索(susu)为了弥补贪婪最正确优先搜索无法找到最优解的缺点,考虑在评价函数里参加累计路径(ljng)耗散,由此形成A*搜索算法评价函数f(n)=g(n)+h(n)g(n):从起始节点到节点n的路径耗散h(n):从节点n到目标节点的最低耗散路径的耗散估计值f(n):经过节点n到目标节点的总耗散估计值第二十九页,共三十七页。

      启发式搜索(susu)策略A*搜索(susu)第三十页,共三十七页 启发式搜索(susu)策略A*搜索(susu)第三十一页,共三十七页 启发式搜索(susu)策略A*搜索(susu)第三十二页,共三十七页 启发式搜索(susu)策略A*搜索(susu)第三十三页,共三十七页 启发式搜索(susu)策略A*搜索(susu)第三十四页,共三十七页 启发式搜索(susu)策略如果h(n)是可采纳的admissible,即h(n)从不过高估计节点(jidin)n到目标节点的最低耗散,则基于A*搜索策略的树搜索方法不检查重复节点是最优的如果h(n)是一致的consistent,则基于A*搜索策略的图搜索方法检查重复节点是最优的A*搜索(susu)第三十五页,共三十七页 Thanks第三十六页,共三十七页 内容(nirng)总结SearchingProblemsinAI 如果所求序列可以使得总耗散最低,则问题称为最优搜索问题 与某一城市相邻的城市才能成为合法后继 满足棋盘上所有皇后不能互相攻击的后继才是合法的。

      目标(mbio)状态:棋盘上摆了八个皇后,并且任意两个皇后都不能互相攻击 初始状态:智能体所处的初始状态 所有搜索过程都可以用搜索树算法来进行表示 不同搜索策略的区别仅在于扩展节点的顺序 先被访问的节点先进行扩展 Thanks第三十七页,共三十七页 7Word版本。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.