ZFenng对《人工智能》的笔记(4)

ZFenng
ZFenng (追求技术又学习管理的IT人)

读过 人工智能

人工智能
  • 书名: 人工智能
  • 作者: (美)GeorgeF.Luger
  • 副标题: 复杂问题求解的结构和策略(原书第6版)
  • 页数: 490
  • 出版社: 机械工业出版社
  • 出版年: 2010-1
  • 第77页
    数据驱动的搜索,即正向搜索。适合于目标状况众多,或难以假设目标的情况。
    目标驱动的搜索,即逆向搜索。适合于规则数量众多,且目标状态已知的情况。
    不同的搜索策略,在不同状态空间中会影响搜索的效率。
    2013-03-13 15:04:07 回应
  • 第85页
    搜索时,对搜索到的每个状态(即已搜索过和在队列中的状态)同时保存其父节点的引用,以便在发现目标状态后回溯至父节点而重建路径。
    广度优先能发现最短路径,但空间复杂度是路径长度的指数;深度优先的空间复杂度为线性,但容易陷入循环或迷失。
    2013-03-13 15:16:03 回应
  • 第115页
    在评估函数中增加对路径长度的考量g(n),能增加搜索的“宽度优先性”,使搜索不会永久迷失。同时,评估得分相同时,离根更近的状态越有可能处于最终路径上。
    g(n)也可认为是从根状态到达当前状态的所有代价。
    h(n)为从当前状态到达目标状态的估计代价。当h(n)为实际代价的下界时,能保证A*算法能找到最短的目标状态,即此搜索方法具有“可采纳性”。
    广度优先算法可看做是h(n)=0的特殊A*算法,故其也拥有可采纳性。
    2013-03-13 16:14:51 回应
  • 第118页
    启发的单调性。即搜索到的任一节点均是最短路径,在任何一局部都具有可采纳性,因此单调性蕴含了可采纳性。
    当搜索具有单调性时,再次遇到同一个状态时,不需要再更新保存的此状态的父状态(因为之前的路径一定最短)
    当h(n)更接近真实的h*(n)时,则说明此h具有更高的信息度。信息度越高,能够正确剪去的分支也越多,但也会增加计算量,甚至可能会抵消剪支带来的优势。
    2013-03-13 16:37:29 回应