题选：图的最短路径算法，A*算法

求解最短路径的算法有很多，而A*算法无疑是其中最高效率、适用性更强的算法之一。

概括来说 A*算法=贪心最优搜索+BFS+优先队列=贪心+Dijkstra+优先队列

A*算法的核心在于估价函数 f=g+h，其效率取决于H函数的设计

1.贪心最优搜索

贪心是启发式算法，在寻找图中最短路径时能高效找到局部最优解，但无法保证全局最优解

具体的实现思想：从起点s出发，寻找i点（i点是距离终点t最近的邻居节点）

如何找距离终点最近的邻居节点i？如何估计i到t的距离？

BFS+优先队列；我们用曼哈顿距离估算最短距离。

然而，这样的贪心算法无法确保我们假定的最优解存在。我们分情况讨论：

  • 在无障碍网格中，贪心结果是最优解。因为曼哈顿距离一定存在
  • 在有障碍网格图中，曼哈顿距离不一定存在，可能i节点在走曼哈顿距离时碰壁，回头绕路。因此，在有障碍网格图中，我们不能确保贪心得到存在的最优解。

然而，无障碍网格图要求这是个连通图，这样大量图无法适用于贪心法。

总结来看：贪心最优搜索，只看终点，不看起点，错了不能改正，没有回头路，而且曼哈顿距离无法绕过障碍

2.Dijkstra（BFS）算法

优先队列的Dijkstra 算法能够高校球的起点s到终点t的距离，但是Dijkstra有bfs通病：没有方向，一股脑一层一层往下。但我们需求只有求一条s到t的最短路径,而不是s到图的任意节点的最短路径，这样会遍历大量的节点空间造成浪费。

总结来看：Dijkstra,只看起点，不看终点

A*算法

其实很多高效复杂的算法都是针对同一种问题基本的不同算法的杂交。举个例子，在探究图的连通性时，我们会用到加权快速并集和路径压缩快速并集，很自然地，将两者结合，我们就会想到Weighted quick-union with path compression

同理，A算法也是两种基本解决最短路径算法的结合，贪心和Dijkstra，总结来看，*既看起点，也看终点，这恰好互补了两种基本算法的缺陷。

我们用曼哈顿方法作为计算距离的方法 算法代码实例（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define N 10 // 地图的阶数
using namespace std;

typedef struct NODE
{
    int x, y;    // 节点所在位置
    int F, G, H; // G:从起点开始，沿着产的路径，移动到网格上指定方格的移动耗费。
    // H:从网格上那个方格移动到终点B的预估移动耗费，使用曼哈顿距离。
    // F = G + H
    NODE(int a, int b) { x = a, y = b; }
    // 重载操作符，使优先队列以F值大小为标准维持堆
    bool operator<(const NODE &a) const
    {
        return F == a.F ? G > a.G : F > a.F;
    }
} Node;

// 定义方向
//const int next_position[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
const int next_position[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
priority_queue<Node> open; // 优先队列，就相当于open表
// 棋盘
int map[N][N] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
                 {0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
                 {0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
                 {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
                 {0, 0, 1, 1, 0, 1, 0, 0, 0, 0},
                 {0, 0, 1, 0, 1, 0, 1, 0, 0, 0},
                 {0, 0, 1, 0, 0, 0, 0, 1, 0, 0},
                 {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
bool close[N][N]; // 访问情况记录，close列表
int valueF[N][N]; // 记录每个节点对应的F值
int pre[N][N][2]; // 存储每个节点的父节点

int Manhattan(int x, int y, int x1, int y1)
{
    return (abs(x - x1) + abs(y - y1)) * 10;
}

bool isValidNode(int x, int y, int xx, int yy)
{
    if (x < 0 || x >= N || y < 0 || y >= N)
        return false; // 判断边界
    if (map[x][y] == 1)
        return false; // 判断障碍物
    // 两节点成对角型且它们的公共相邻节点存在障碍物，在8方向时用
    if (x != xx && y != yy && (map[x][yy] == 1 || map[xx][y] == 1))
        return false;
    return true;
}

void Astar(int x0, int y0, int x1, int y1)
{
    // 起点加入open列表
    Node node(x0, y0);
    node.G = 0;
    node.H = Manhattan(x0, y0, x1, y1);
    node.F = node.G + node.H;
    valueF[x0][y0] = node.F;
    open.push(node);

    while (!open.empty())
    {
        Node node_current = open.top();                   //取优先队列头元素，即周围单元格中代价最小的点
        open.pop();                                       //从open列表中移除
        close[node_current.x][node_current.y] = true;     // 访问该点，加入close列表
        if (node_current.x == x1 && node_current.y == y1) // 到达终点
            break;

        // 遍历node_top周围的4个位置，如果是next_position有8，那么就需要遍历周围8个点
        for (int i = 0; i < 4; i++)
        {
            Node node_next(node_current.x + next_position[i][0], node_current.y + next_position[i][1]); // 创建一个node_top周围的点
            // 该节点坐标合法 且没有被访问
            if (isValidNode(node_next.x, node_next.y, node_current.x, node_current.y) && !close[node_next.x][node_next.y])
            {
                // 计算从起点并经过node_top节点到达该节点所花费的代价
                node_next.G = node_current.G + int(sqrt(pow(next_position[i][0], 2) + pow(next_position[i][1], 2)) * 10);
                // 计算该节点到终点的曼哈顿距离
                node_next.H = Manhattan(node_next.x, node_next.y, x1, y1);
                // 从起点经过node_top和该节点到达终点的估计代价
                node_next.F = node_next.G + node_next.H;

                // node_next.F < valueF[node_next.x][node_next.y] 说明找到了更优的路径，进行更新
                // valueF[node_next.x][node_next.y] == 0 说明该节点还未加入open表中，则加入
                if (node_next.F < valueF[node_next.x][node_next.y] || valueF[node_next.x][node_next.y] == 0)
                {
                    // 保存该节点的父节点
                    pre[node_next.x][node_next.y][0] = node_current.x;
                    pre[node_next.x][node_next.y][1] = node_current.y;
                    valueF[node_next.x][node_next.y] = node_next.F; // 修改该节点对应的valueF值
                    open.push(node_next);
                }
            }
        }
    }
}

void PrintPath(int x1, int y1)
{
    if (pre[x1][y1][0] == -1 || pre[x1][y1][1] == -1)
    {
        cout << "no path to get" << endl;
        return;
    }
    int x = x1, y = y1;
    int a, b;
    while (x != -1 || y != -1)
    {
        map[x][y] = 2; // 将可行路径上的节点赋值为2
        a = pre[x][y][0];
        b = pre[x][y][1];
        x = a;
        y = b;
    }
    // ' '表示未经过的节点， '#'表示障碍物， '@'表示可行节点
    string s[3] = {"  ", " #", " @"};
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            cout << s[map[i][j]];
        cout << endl;
    }
}

int main(int argc, char *argv[])
{
    fill(close[0], close[0] + N * N, false);    // 将visit数组赋初值false
    fill(valueF[0], valueF[0] + N * N, 0);      // 初始化F全为0
    fill(pre[0][0], pre[0][0] + N * N * 2, -1); // 路径同样赋初值-1

    //  // 起点 // 终点
    int x0 = 2, y0 = 4, x1 = 8, y1 = 6;
    int t;

    printf("test number: ");
    scanf("%d",&t);

    while (t--){
     printf("input start: ");
    scanf("%d%d", &x0, &y0);
     printf("input destination: ");
     scanf("%d%d", &x1, &y1);

    if (!isValidNode(x0, y0, x0, y0))
    {
        printf("Invalid input.\n");
        return 0;
    }

    Astar(x0, y0, x1, y1); // A*算法
    PrintPath(x1, y1);     // 打印路径

}}

那这是如何结合两种算法的？

  • 对于起点s到i的路径，Dijkstra保证最优性
  • 对于i到t的路径，采用贪心预测，选择i的下一个节点。
  • 当i碰壁时，i被丢弃；回退到上一层重新选择节点j，而j任由Dijkstra保证最优性

对于以上具体实现想法，我们设计一个函数抽象的表示： f(i)=g(i)+h(i) (g反映Dijkstra,h反映贪心)

  • 显然，g=0，A 退化成贪心；h=0，A退化成Dijkstra

详细解释一遍：A*更具最小的f(i)选择下一个节点i，g(i)是走过的路径，已知；h(i)是预测未来走的路径，f(i)取决于h(i)的计算

A*的结果一定是最优吗？

当i到t终点时，h(t)=0,此时f(t)=g(t)，而g(t)是由Dijstra保证的最短路径，因此A*能够得出最优解

总的来说，A*以Dijkstra获得最优结果，用贪心扩展方向，大大减少搜索的节点

h函数设计

对于二维平面图，三种办法近似计算h函数，设i的坐标(x1,x2),t(x2,y2)

  • 曼哈顿距离。节点只能上下左右移动，h(i)=abs(x1-x2)+abs(y1-y2)
  • 对角线距离，节点能够8个方向上移动（新增东北，西北，东南，西南方向），h(i)=max{abs(x1-x2),abs(y1-y2)}
  • 欧式距离，节点可以任意方向移动,h(i)=sqrt((x1-x2) 2+(y1-y2) 2)

注意三条规则

  • g和h采用相同距离计算方法
  • 根据具体图的背景信息，选择相应的距离算法
  • h优于实际存在的所有路径，这一点很关键，接下来我们会对此具体讨论
    1.h(i) > i-t中存在的最短路径长度。设实际最短路径为path，由于计算h(i)扩展下一个节点，path被抛弃了（因为找到h(i)）,选择非最短路径
  1. h(i) < i-t中所有路径。这意味着在i-t中不存在长度为h(i)的路径，在搜寻h(i)的路径时，节点一定会碰壁。但这不要紧，因为Dijkstra算法让这些碰壁的点弹出，回退到合适的点，从而扩展出实际路径。

参考：https://blog.csdn.net/denghecsdn/article/details/78778769

A*算法例题

from poj 2249

题面描述:
给定N个点，M条有向边。给出起点s和终点t,求其中第K个最短路径。

注意：若出发点与结束点为同一点，则一定要从出发点跑出去，再跑回来，才算最短路

第K短路则运用了A ∗ AA∗的排除多余状态与优先队列B F S BFSBFS,第几次取出e d eded,即求到第几短路的性质来解决问题，A ∗ AA∗主要起优化作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

int main(){
    
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m, s, t, k;
bool vis[maxn];
int dist[maxn];

struct Node
{
    int v, c;v是节点编号，c是s到v估计值,c是g[i],dist为h[i]
    Node (int _v = 0, int _c = 0): v(_v), c(_c) {}
    bool operator < (const Node &rhs) const
    {
        return c + dist[v] > rhs.c + dist[rhs.v];  估价函数 fx = gx + hx 路径短先出队
    }
};

struct Edge
{
    int to, cost;
    Edge (int _to = 0, int _cost = 0): to(_to), cost(_cost) {}
};

vector <Edge> E[maxn], revE[maxn];

void addedge(int u, int v, int w)
{
    E[v].push_back(Edge(u, w));  反向加边
    revE[u].push_back(Edge(v, w));  正向加边
}

void dijkstra(int s, int n)  最短路径，从终点t遍历所有节点，找出所有节点到t的最短路径,即dist[v]为v到t的最短路径h[i]
{
    for (int i = 0; i <= n; ++i)
    {
        vis[i] = false;
        dist[i] = inf;
    }
    dist[s] = 0;
    priority_queue <Node> Q;
    Q.push(Node(s, dist[s]));
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < E[u].size(); ++i)
        {
            int v = E[u][i].to, cost = E[u][i].cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                Q.push(Node(v, dist[v]));
            }
        }
    }
}

int astar(int s)
{
    这里dist已经计算，优先队列排序会按照f[i]=g[i]+h[i](dist[i])排序,55行
    a*算法从s起点开始，通过反向边同样计算最短路径
    priority_queue <Node> Q;
    Q.push(Node(s, 0));
    k--;
    while (!Q.empty())
    {
        Node tmp = Q.top();
        Q.pop();
        int u = tmp.v;节点编号
        if (u == t) 找到终点
        {
            if (k)
                --k;
            else   第k次到达目标节点t
                return tmp.c;
        }
        for (int i = 0; i < revE[u].size(); ++i)
        {
            int v = revE[u][i].to, cost = revE[u][i].cost;
            Q.push(Node(v, tmp.c + cost));
        }
    }
    return -1;
}

int main()
{
    int u, v, w;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i <= n; ++i)
        {
            E[i].clear();
            revE[i].clear();
        }
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
        }
        scanf("%d%d%d", &s, &t, &k);
        dijkstra(t, n);  t点到所有点的最短路
        if (dist[s] == inf)
            printf("-1\n");
        else
        {
            if (s == t)  起点等于终点特判
                ++k;
            printf("%d\n", astar(s));
        }
    }
    return 0;
}