人工智能--状态空间的盲目搜索

文章目录状态空间的盲目搜索广度优先算法算法描述:总结深度优先算法总结状态空间的盲目搜索根据状态空间所采用的数据结构的不同,可分为图搜索算法和树搜索算法。由于图搜索算法且一般问题都可用树搜索算法解决,于是主要讨论树搜索算法,包括一般和代价树。一般树的盲目搜索主要包括深度优先和广度优先两种搜索算法。广度优先算法也称为宽度优先算法,是一种先生成的节点先扩展的策略。算法精髓:从初始节点$S_0$开始逐层向...

人工智能--状态空间的盲目搜索

状态空间的盲目搜索

根据状态空间所采用的数据结构的不同,可分为图搜索算法和树搜索算法。由于图搜索算法且一般问题都可用树搜索算法解决,于是主要讨论树搜索算法,包括一般和代价树。

一般树的盲目搜索主要包括深度优先和广度优先两种搜索算法。

广度优先算法

也称为宽度优先算法,是一种先生成的节点先扩展的策略。

算法精髓:从初始节点$S_0$开始逐层向下扩展,在第n层还没有完全搜索完之前不会进入第n 1层的搜索。Open表中的节点总是按进入的先后排序,先进入的节点排在前面。

算法描述:
  • 把初始节点$S_0$放入Open表中
  • 如果Open表为空,则问题无解,失败退出
  • 把Open表的第一个节点取出,放入Closed表,并记该节点为n
  • 考察节点n是否为目标节点,若是,则得到问题的解,成功退出
  • 若节点n不可扩展,则转第二步
  • 扩展节点n,将其子节点放入Open表的尾部,并未每一个子节点设置指向父节点的指针,然后转到第二步。
  • image

    总结

    广度优先搜索是一种完备策略,即只要问题有解,算法就一定可以找到解。并且,广度优先算法找到的解还一定是路径最短的解。

    缺点是盲目性较大,特别是当目标节点与初始节点距离较远时,将产生许多无用的节点,效率较低。

    深度优先算法

    算法步骤基本与广度优先算法相同,只是Open表中的排序不同,在深度优先算法中,后进入Open表的节点总是排在最前面。即后生成的节点先扩展。

    总结

    深度优先算法是一种非完备策略,即某些本身有解的问题,该算法可能找不到最优解,甚至找不到解。常见做法是增加一个深度限制,当达到一定深度时,停止深度搜索,转向宽度搜索。这种算法也叫有界深度优先算法。

    源文地址:https://www.guoxiongfei.cn/csdn/4899.html