人工智能启发式搜索.doc

人工智能启发式搜索.doc人工智能-----启发式搜索问题背景人工智能的宗旨是寻找一种有效的方式把智能的问题求解、规划和通信技巧应用到更广泛的实际问题中,集中于不存在算法解的问题,这也是为什么启发式搜索是一种主要的AI问题求解技术的原因。对于人工智能系统而言,问题可能状态的数量随搜索的深入呈现指数或阶乘增长,为了明智地找出正解,将沿最有希望的路径穿越空间来降低这种复杂性,这便是启发式求解。把没有希望的状态及这些状态的后代排除,这样便可以克服组合爆炸,找到可接受的解。基本简介启发式求解对问题求解过程中下一步要采取的措施的一种精明猜测,是建立于强大的知识库的由经验总结出的求解方式。简单的启发可以排除搜索空间的绝大部分。启发式搜索由两部分组成:启发度量及是有这个度量进行空间搜索的算法。下面介绍两种算法爬山法爬山策略在搜索中现扩展当前状态,然后再评估它的“孩子”。而后选择“最佳的”孩子做进一步扩展;而且过程中既不保留它的兄弟姐妹,也不保留它的双亲。因为这种策略不保存任何历史记录,所以它不具有从失败中恢复的能力。图1使用3层预判的爬山方法遇到的局部最大化问题爬山策略的一个主要问题是容易陷入局部最大值。如果这种策略达到了一个比其他任何孩子都好的状态,它便停止。因此为了提高性能,需要局部改进评估多项式。最佳优先搜索算法最佳优先搜索算法使用了优先级队列,使得从诸如陷入局部优先等情况中恢复成为可能,从而使启发式搜索更加灵活。最佳优先搜索算法使用列表来维护状态:用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值,这个值等于该状态在搜索空间中的深度