再探a*搜索算法(启发式函数的影响)

weblog 3607 0 0

前言

了解a*搜索算法的原理请参考:http://www.jiajiajia.club/official/weblog/32

a*搜索算法动态演示分析,及代码,请参考:http://photo.jiajiajia.club/item/a-star.html

Dijkstra算法与最佳优先搜索

在了解a*算法之前相信您已经对这两个算法有所了解

        Dijkstra算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),优先从未遍历的节点集合中选取距离最近的那个节点遍历,然后再更新与该节点有关的接待你的距离,直到扩展到终点为止。条件是每条边的权值不能为负数。但是在某种情形中,和广度优先搜索一样,需要耗费更多的时间。如下图,红色为开始节点,蓝色为结束节点。

Dijkstra算法能够在复杂的环境中找到一条最短路径。如下图。

        最佳优先搜索算法是一种启发式的搜索算法,它是对广度优先搜索算法的一种改进,它在广度优先搜索算法的基础上利用一个估价函数对将要遍历的节点进行估价(一般是从该节点到目标节点的距离),然后从将要遍历的集合中取出一个代价最小的节点遍历。这样的话它的速度就会提升很快。

但是他的缺点是不能保证找到一条最短的路径。例如下面有障碍的情况,明显不是最短的路径。

A*搜索算法

        a*算法的实现在之前已经介绍过了,请参考原文:http://www.jiajiajia.club/official/weblog/32,在此就不解释实现原理了。

        a* 算法结合了 最佳优先搜索算法  和 Dijkstra算法两者的优点:在进行启发式搜索提高算法效率的同时,还可以保证找到一条最优路径。因为a*算法同时把 从 开始节点走到当前节所消耗的代价g(n)(距离)和从当前节点到目标节点的预估代价h(n)(距离)同时作为选取下一节点的参考标准 f(n)。点也可以说启发式函数基本决定了a*搜索算法搜索的方向。

        启发式函数:f(n)=g(n)+h(n)

g(n)为已知的从开始节点到当前节点经过的代价,h(n)为从当前节点到目标节点的预估代价。

那么选取下一节点的时候理应选取g(n)+h(n)和最小的节点作为下一将要遍历的节点。

所以f(n)函数的选取就成为了a*算法的核心。


启发式函数对a*搜索算法的影响

        如果不考虑g(n)的情况或者g(n)要远小于h(n),那么a*搜索算法就会逐渐趋向于最佳优先搜索。因为过分的把h(n)作为参考选择下一节点的标准,势必会以失去精准度为代价。在某种条件下,a*搜索算法不能找到一条最短路径。

        如果不考虑h(n)或g(n)远大于h(n)的时候,那么a*搜索算法会逐渐趋向于Dijkstra算法,他确实能找到一条最短路径,但是在某种条件下消耗的时间也是惊人的。

只有在均衡两者的关系的时候,才能满足和体现a*算法的特点,如下图。

        因为从开始节点到当前节点经过的距离即g(n)是根据特定情形而设定的,经过某节点时的时的距离经过Dijkstra算法的计算后也都是最近的。所以下一节点的选择几乎取决于h(n)的计算结果。

启发函数h(n)的选取

1.曼哈顿距离(城市街区距离)
D*(Math.abs(startX-endsX)+Math.abs(startY-endsY));

D为每走一步需要消耗的代价。

如果是只能四个方向走的时候,此时应该是较好的一种方案。

2.欧几里得距离
var a=Math.abs(startX-endsX);
var b=Math.abs(startY-endsY);
return D*Math.sqrt((a*a+b*b));

3.平方后的欧几里得距离
var a=Math.abs(startX-endsX);
var b=Math.abs(startY-endsY);
return D*(a*a+b*b);

4.对角线距离
D*Math.max(Math.abs(startX-endsX),Math.abs(startY-endsY));

 

具体选取什么样的f(n)作为参考依据,还需要根据具体情况。

 

猜你喜欢
weblog 3102 a*动态演示分析请参考http://photo.jiajiajia.club/item/a-star.html什么是a*A*,俗称A星,作为一种,这是一
数据结构与算法 873 广度优先(dfs、深)java实现-据结构和用邻接矩阵表示图定点之间关系如下图据结构:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 901 上一篇:广度优先(bfs、广)java实现-据结构和用邻接矩阵表示图定点之间关系如下图据结构则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 8095 问题描述思路:典型广度优先,根据字典序大小,可以确定遍历循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口一条路径就是符合
数据结构与算法 5085 科普:第一篇二分论文是1946年表,然而第一个没有bug二分查找却是在1962年才出现,中间用了16年时间。定义在计机科学中,二分查找(英语:binarysearch),也称折半
数据结构与算法 8679 问题描述思路:斐波那契变体考虑如果把20190324项每一项值都出来话,那么值范围就会超出基本据类型能够表示范围,又考虑到题目是求最后四位,而加时前一位不会后一位
java基础 529 java并编程-理解CAS1.什么是cas?CAS:CompareandSwap,即比较交换。jdk5增加了并包java.util.concurrent.*,其下面类使用CAS
official 183 述给定一个二叉根节点root,和一个整k,请你设计一个查找其中第k个最小元素(从1开始计)。示例1输入:root=[3,1,4,null,2],k=1 输出:1示例2输入:root=[5
目录
祝愿神州十三飞行乘组平安归来