了解了基本搜索算法,下面就来看A*,神奇的A*。(--->搜索方法小结)
A*是一种启发式搜索,一种有序搜索,它之所以特殊完全是在它的估价函数上,如果我要求的是从初始结点到目的结点的一个最短路径(或加权代价)的可行解,那对于一个还不是目标结点的结点,我对它的评价就要从两个方面评价:第一,离目标结点有多近,越近越好;第二,离起始结点有多远,越近越好。记号[a,b]是表示结点a到结点b的实际最短路径代价。设起始结点为S,当前结点为n,目标结点为G,于是n的实际代价应该是f*(n)=g*(n)+h*(n),其中g*(n)=[S,n],h*(n)=[n,G],对于是g*(n)是比较容易得到的,在搜索的过程中我们可以按搜索的顺序对它进行累积计算,当然按BFS和DFS的不同,我们对它的估价g(n)可以满足g(n)>=g*(n),大多可以是相等的。但是对于h*(n)我们却了解得非常少,目标结点正是要搜索的目的,我们是不知道在哪,就更不知道从n到目标结点的路径代价,但是或多或少我们还是可以估计的,记估价函数f(n)=g(n)+h(n)。
我们说如果在一般的图搜索算法中应用了上面的估价函数对OPEN表进行排序的,就称A算法。在A算法之上,如果加上一个条件,对于所有的结点x,都有h(x)<=h*(x),那就称为A*算法。如果取h(n)=0同样是A*算法,这样它就退化成了有序算法。
A*算法是否成功,也就是说是否在效率上胜过蛮力搜索算法,就在于h(n)的选取,它不能大于实际的h*(n),要保守一点,但越接近h*(n)给我们的启发性就越大,是一个难把握的东西。
A*算法流程:
首先将起始结点S放入OPEN表,CLOSE表置空,算法开始时:
1、如果OPEN表不为空,从表头取一个结点n,如果为空算法失败
2、n是目标解吗?是,找到一个解(继续寻找,或终止算法);不是到3
3、将n的所有后继结点展开,就是从n可以直接关联的结点(子结点),如果不在CLOSE表中,就将它们放入OPEN表,并把S放入CLOSE表,同时计算每一个后继结点的估价值f(n),将OPEN表按f(x)排序,最小的放在表头,重复算法到1
最短路径问题,Dijk
A高效搜索算法 来自淘豆网m.daumloan.com转载请标明出处.
