人工智能--启发式搜索.doc

人工智能 -启发式搜索1 问题背景人工智能的宗旨是寻找一种有效的方式把智能的问题求解、规划和通信技巧应用到更广泛的实际问题中，集中于不存在算法解的问题，这也是为什么启发式搜索是一种主要的AI问题求解技术的原因。对于人工智能系统而言，问题可能状态的数量随搜索的深入呈现指数或阶乘增长，为了明智地找出正解，将沿最有希望的路径穿越空间来降低这种复杂性，这便是启发式求解。把没有希望的状态及这些状态的后代排除，这样便可以克服组合爆炸，找到可接受的解。2 基本简介启发式求解对问题求解过程中下一步要采取的措施的一种精明猜测，是建立于强大的知识库的由经验总结出的求解方式。 简单的启发可以排除搜索空间的绝大部分。启发式搜索由两部分组成：启发度量及是有这个度量进行空间搜索的算法。下面介绍两种算法1. 爬山法 爬山策略在搜索中现扩展当前状态，然后再评估它的“孩子”。而后选择“最佳的”孩子做进一步扩展；而且过程中既不保留它的兄弟姐妹，也不保留它的双亲。因为这种策略不保存任何历史记录，所以它不具有从失败中恢复的能力。 图1 使用3层预判的爬山方法遇到的局部最大化问题 爬山策略的一个主要问题是容易陷入局部最大值。如果这种策略达到了一个比其他任何孩子都好的状态，它便停止。因此为了提高性能，需要局部改进评估多项式。2. 最佳优先搜索算法 最佳优先搜索算法使用了优先级队列，使得从诸如陷入局部优先等情况中恢复成为可能，从而使启发式搜索更加灵活。 最佳优先搜索算法使用列表来维护状态：用open列表来记录搜索的当前状态，用close列表记录已经访问过的状态。在这种算法中新加的一步是对open中的状态进行排序，排序的依据是对状态与目标“接近程度”的某种启发性估计。 最佳优先搜索算法总是选择最有希望的状态做进一步扩展。然而由于他正在使用的启发可能被证明是错误的，所以它并不抛弃所有状态而是把他们维护在open中。一旦发现启发将搜索引导到一条证明不正确的路径，那么算法会从open中取出一些以前产生的“次优先”的状态，从而把搜索的焦点转移到空间的另一部分。以8格拼图游戏为例进行启发式搜索： 图2 游戏目标构造一个评估函数f，它是两个分量的和： f(n)=g(n)+h(n)其中：g(n)是从任意状态n到起始状态的实际路径长度，h(n)是对状态n到目标距离的启发性估计（在此表示错位的牌数）目前该游戏h=4； 图3 对8格拼图游戏进行启发式搜索而产生的状态空间归纳起来，最佳优先算法就是 1）操作当前状态以产生新的孩子 2）检查每个新状态，看其是否已经（在open或close中）出现过，以防止循环 3）给出每个状态n的f值，这个值等于该状态在搜索空间中的深度g（n）和它与目标距离的启发性估计h（n）的和。 4）open中的状态是按它们的f值排序的，在分析了所有状态或发现目标之前，所有状态都被保存在open中，这样做使算法可以从死端（dead end）恢复 5）从现实角度来看，可以通过改善维护open和close列表的方法来提高算法的效率。3 现有工作 实际生活中，启发式搜索主要应用于专家系统，例如“深蓝”与象棋高手之间的博弈、财务统计及顾问、一些复杂算法的求解它的内容也正逐步扩展，从传统的爬山和动态规划算法到最佳优先搜索，再到二人游戏中的极小极大和-剪枝的预判来尝试预测对手的行为。 启发式搜素依然存在其弊端，例如博弈过程中，对手改变惯有套路，就难以在智能机器知识库中搜索，从而无法做出正确解答。 当然，人们对于启发式搜索的探索正逐步深入4 我的想法 在人工智能中，搜索就像红线将用户与计算机强大的知识库相连，而在此，启发式搜索之所以占有一