在看了NTU的AI课程之后,试着用C++来实现了A*搜索算法。它的思想就是Avoid expanding paths that are already expensive.
。标准的A*搜索算法描述如下:
给出带权无向图,初始顶点,目标顶点,以及evaulation function。Evalutaion function包括
- g(n):为到达顶点n,当前已有的花费(cost so far to reach n)
- h(n):一个 从任意顶点 到 目标顶点 的估计花费(estimated cost to goal from n)
- f(n):从 初始顶点 到 目标顶点 的估计花费(estimated total cost from the starting node to goal through n)
f(n) = h(n) + g(n)
例如有三个地点A, B, C,它们之间的图如下
A —— B —— C
A —— B权重为30,B —— C权重为40,
A —— C的直线距离为50,但是并没有A——C这条边(即不能直接从A开始,只经过一条边就到达C)
现在,给出初始顶点为A,目标顶点为C,h(n)如下
h(A) = 50
h(B) = 40
h(C) = 0
在一开始,我们将A放入名为froniter的优先队列中,froniter按照f(n)的值升序排序。
那么我们有f(A) = h(A) + g(A)。h(A)是由用户直接给出的,等于50。g(A)是我们为了到达C,已有的花费,在这个例子中,可以理解为已经走过的路程,因为我们是一开始就在A,还没有开始走,所以g(A)为0。于是f(A) = h(A) + g(A) = 50 + 0 = 50
froniter中的数据如下:
current | from | g(current) | h(current) |
---|---|---|---|
A | A | 0 | 50 |