人工智能中的搜索问题课件

Searching Problems in AI人工智能中的搜索问题智能体的初始状态是确定的智能体当前状态是否为目标状态是可以检测的智能体的状态空间是离散的智能体在每个状态可以采取的合法行动和相应后继状态是确定的环境是静态的路径的耗散函数是已知的什么是搜索问题搜索问题：已知智能体的初始状态和目标状态，求解一个行动序列使得智能体能从初始状态转移到目标状态。如果所求序列可以使得总耗散最低，则问题称为最优搜索问题。几个典型的搜索问题起始状态：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*搜索启发式搜索策略A*搜索启发式搜索策略A*搜索启发式搜索策略如果h(n)是可采纳的（admissible），即h(n)从不过高估计节点n到目标节点的最低耗散，则基于A*搜索策略的树搜索方法（不检查重复节点）是最优的如果h(n)是一致的（consistent），则基于A*搜索策略的图搜索方法（检查重复节点）是最优的A*搜索Thanks学科前沿讲座学科前沿讲座皇帝的新脑还是人类的终结皇帝的新脑还是人类的终结 一、关于人工智能 一、关于人工智能从数值计算文字、图像等多媒体信息处理初步实现了Leibniz提出的“将人的思维机器化”的思想让机器拥有人的心智成为计算机专家梦寐以求的理想！1956年，M.L.Minsky，C.Shanon，J.McCarthy(人工智能之父)等在美国达德茅斯大学召开第一届人工智能学术会议。会上首次使用“人工智能”这一术语。标志着人工智能学科的诞生。一、关于人工智能1950年，W.格雷.瓦尔特，可以自己充电的“乌龟”1960年，K.M.柯尔，模拟了一个精神病疗法专家电脑下棋方面，97年的“深蓝”(Deep Blue)，03年的“小深”(Deep Junior)一、关于人工智能医生：我可以为你效劳吗病人：我不知道医生：请告诉我一些情形病人：不医生：请你说得仔细些病人：今天我厌烦得很医生：你知道这是什么原因病人：是的我老了医生：请继续讲病人：仿佛任何事情都激不起我的兴致医生：请更多地告诉我你的这种感觉病人：我也有些知道为何我会这样感觉医生：是吗病人：我似乎在想有一个家医生：什么东西使你有这样的想法病人：它是一种挑战医生：为什么那对你是重要的二、电脑能否实现人的智能？机器体力电脑计算速度和准确性人脑思维是否电脑能代替人脑实现智能？一旦能够实现，这种被认为是特权的智能行为将受到挑战。二、电脑能否实现人的智能？二、电脑能否实现人的智能？二、电脑能否实现人的智能？l人真实地回答问题并试图说服质问者，他确实是人；l电脑被编好“说谎”的程序，试图说服质问者它是人。三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：爱因斯坦曾经将其比喻为“与上帝的对话”三、目前人工智能两个代表性的观点：三、目前人工智能两个代表性的观点：四、对人工智能领域有影响的理论与书籍 四、对人工智能领域有影响的理论与书籍推荐网址http:/ 四、对人工智能领域有影响的理论与书籍镶嵌图案 埃舍尔的版画(1957)四、对人工智能领域有影响的理论与书籍问题求解逻辑推理与定理证明自然语言理解自动程序设计专家系统机器学习神经网络机器人学五、目前人工智能的研究与应用领域模式识别机器视觉智能控制智能检索智能调度与指挥分布式人工智能与Agent计算智能与进化智能数据挖掘与知识发现 六、计算机视觉中的困惑这些与人类视觉活动相比，显得微不足道。人类视觉中的视觉含义的把握以及主观经验在视觉中的作用，使机器不可能拥有的。六、计算机视觉中的困惑六、计算机视觉中的困惑 六、计算机视觉中的困惑六、计算机视觉中的困惑著名的混沌理论“蝴蝶效应”：美国气象学家洛伦芝（Lorenz）于1960年代提出一篇论文，名叫一只蝴蝶拍一下翅膀会不会在德克萨斯州引起龙卷风？，他说，亚马逊流域的一只蝴蝶扇动翅膀，会掀起密西西比河流域的一场风暴。洛伦芝把这种现象戏称做蝴蝶效应，意思即一件表面上看来毫无关系、非常微小的事情，可能带来巨大的改变。六、计算机视觉中的困惑眼睛和大脑的组合并不只具有“摄像机”般的功能。虽然，人们对“视觉理解”发生的机制还不太清楚，但可以肯定其中含有非线性突变的因素，而且导致某种结果的因素是不确定的。（即蝴蝶效应）“视觉理解”中抹不去的主观因素不可能通过确定的算法给出。七、展望在计算机上要实现人的心智，充满困境。要冲破这一困境，必须有理论性的突破：大自然的机理+算法 七、展望问题的解决不依赖于复杂的逻辑运算，而是利用装置本身的复杂性功能。七、展望大自然的机理+算法目前，在计算原理和模式方面出现了一些新的尝试：p生物计算p量子计算p光子计算p