试题详情
简答题A*算法的基本思想是什么？
  • 该算法在选择下一个被检查的节点时，对当前节点距离终点的长度作为估计，评价其处于最优路线上的可能性量度，这样就可以首先搜索可能性较大的节点，从而提高搜索过程的效率。
    A*算法的估价函数可表示为：
    F’（v）=g（v）+h’（v）
    其中g（v）是从起点到当前顶点，的实际费用的量度，h’（v）是从当前顶点，到终点的最小费用的估计，如果h’（v）=0，即没有利用任何启发式信息，这时的A*算法就变成了普通的Dijkstra算法。h’（v）具体形式的选择取决于路线优化标准，在选择h’（v）时，要满足一个要求，就是不能过高估计当前顶点的最小费用，这被称为可纳性条件，只要启发式函数满足可纳性条件，且原问题存在最优解，则A*算法一定能够计算出最优路径。
    A*算法的程序编写原理
    如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）

    搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：
    1）初始状态：
    OPEN=[A5]；CLOSED=[]；
    2）估算A5，取得搜有子节点，并放入OPEN表中；
    OPEN=[B4，C4，D6]；CLOSED=[A5]
    3）估算B4，取得搜有子节点，并放入OPEN表中；
    OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
    4）估算C4；取得搜有子节点，并放入OPEN表中；
    OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
    5）估算H3，取得搜有子节点，并放入OPEN表中；
    OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=[H3，C4，B4，A5]
    6）估算O2，取得搜有子节点，并放入OPEN表中；
    OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
    7）估算P3，已得到解。

  • 关注下方微信公众号，在线模考后查看

热门试题