初学A*算法求解静态地图的最短路径

以前所接触过的最短路径算法是dijkstra或floyd之类的,都是在已知每两点之间距离的情况下求最短路的。

那么想一下这样的案例

给你一个地图,类似于迷宫一样,中间有些障碍物,再给定起点终点,求该两点间最短路,显然,上述两种算法就不适用了,因为提到的迷宫,我们可能会很容易想到广搜b
fs,但一次bfs下来实际上求出了起点到所有点的最短路径,但我们只想知道它与终点间的最短路径,也就是说这个方案里有很多冗余的操作。

说到这里,该步入正题,介绍A*算法。

A算法;A(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近,估价函数取得就越好。(取自百度百科)

何谓直接搜索方法,即 ** _ 不进行任何预处理直接进行搜索的方法 _ ** 。
那么它为何可以称为最有效的直接搜索方法呢,我们看到上文说到一个估价值与估价函数。
所以有这么一个式子

** f(n) = g(n) + h(n) **

先记住这个式子,在讨论这个式子之前,先谈点题外话。
我们都接触过 ** _ 贪心思想 _ ** ,即 ** _ 在对问题求解时,总是做出在当前看来是最好的选择。 _ **
从起点开始,它可走的地方是周围的8个点(最多),平常广搜时多个可能是平等对待,全部考虑。

那么?我们可不可以运用贪心的思想从8个点中选出一个最有可能达到最短路的点来优先进行操作呢?

当然可以,这样我们就是 ** 有针对性的搜索 ** ,而不是 ** 盲目搜索 ** 了。

有的道友可能会说了, ** 这样贪心下来求出的只能是接近于最优解的相对最优解,并不能保证一定最优 ** ,没错,事实的确是这样。
那么这样就行不通了,因为我们的目的是很明确的,要的是最短路径。

但是往常的贪心算法都是 ** 选取当前状态下最好的选择,至于次好选择等等全部就丢掉了 **
,那如果我们仍然保留这些选择,仍与后来的可能进行比较呢,这样就保证最后的解一定是最优解了。

如何将所有可能性都保留下来继续参与后来的比较呢, ** _ 优先队列 _ ** 是一个不错的法子。
1. 从A开始,将其周围可走且未标记的点,全部加入队列,然后标记A点
2. 从队列中选取优先度最高的点B
3. 对B重复1操作,直到到达终点为止

但优先度如果获得呢,现在我们回到这个式子

** f(n) = g(n) + h(n) **
g(n)为从起点到点n所花费的代价值
h(n)为点n到终点所花费代价的估价值
两者之和 f(n)就是点n的优先值

例如,对几何地图进行求解时,可以将从起点到点n走的步数作为g(n),将点n到终点的几何距离作为h(n)估价值,那么此时,f(n)的值越小,优先度越高。

下面贴代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<functional>
#include<set>

using namespace std;

const int N = 10009;//地图范围

int v[N][N] = {};//记录地图
int dx[] = {1,1,1,0,0,-1,-1,-1};//8个方向
int dy[] = {1,0,-1,1,-1,1,-1,0};
int f[N*N];//对当前点进行标记,同时记录上一个位置的坐标

struct Node
{
    int x,y,f,g;//坐标与权值
};

struct Nodecmp//优先队列比较函数
{
    bool operator() (const Node &a, const Node &b)
    {
        return a.f > b.f;
    }
};

int leng(Node a, Node b)//求点与终点的几何长度
{
    return sqrt((a.x - b.x)*(a.x - b.x)
                + (a.y - b.y)*(a.y - b.y));
}

void print(int nid, int n)//输出最短路径
{
    if(nid == -1)
        return;
    print(f[nid],n);
    printf("%d %d\n",(nid-1)/n, nid-(nid-1)/n*n);
}

bool a_start(Node s, Node e, int n)
{
    if(!v[e.x][e.y])//终点不可达
        return false;
    memset(f, 0, sizeof(f));
    priority_queue<Node, vector<Node>, Nodecmp> q;
    int eid = e.x * n + e.y;
    f[s.x * n + s.y] = -1;//二维转一维进行标记,便于操作
    while(!q.empty())
    {
        Node now = q.top();
        q.pop();//出队
        int nid = now.x * n + now.y;
        if(nid == eid)//判断是否为终点
        {
            print(nid, n);
            return true;
        }
        for(int i=0;i<8;i++)//遍历8个方向
        {
            Node t;
            t.x = dx[i] + now.x;
            t.y = dy[i] + now.y;
            int tid = t.x * n + t.y;
            if(v[t.x][t.y] && f[tid] == 0)
            {//符合条件便标记并入队
                f[tid] = nid;
                t.g = now.g + 1;
                t.f = t.g + leng(t, e);
                q.push(t);
            }
        }
    }
    return false;
}

int main()
{
    int n;
    Node s,e;
    s.g = 0;
    cin>>n>>s.x>>s.y>>e.x>>e.y;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cin>>v[i][j];
    if(!a_start(s,e,n))
        cout<<"无法到达"<<endl;
}