概述
A*（A-star）算法是一种在图中探求从初始节点到目标节点最短路径的启发式搜索算法。它结合了Dijkstra算法简直保性（保证找到一条最短路径）和贪婪算法的高效性（快速找到目标）。A*算法通过评估函数f(n) = g(n) + h(n)来工作，其中g(n)是从起始点到任何顶点n的现实成本，而h(n)是从顶点n到目标的估计最低成本，通常用启发式函数来盘算，这个函数需要事先计划来反映现实的地形或情况特性。
A*算法具有以下显著特性：
- 最优性：当启发式函数h(n)满足某些条件时，A*算法能保证找到一条最低成本路径。
- 效率：A*算法在实验过程中保持高效，特别是当启发式函数能够较好地估计到目标的成本时。
A*算法广泛应用于各类路径规划题目，如机器人导航、舆图定位服务和游戏中的AI路径探求等场景。通过适当选择和调整启发式函数，A*算法能够在复杂的情况中有效地探求最短路径，同时保持盘算上的可行性和效率。
启发式函数的选择对A*算法的性能和准确性至关重要。理想情况下，h(n)不应该高估现实的成本，这种情况下，A*算法保证找到一条最低成本路径。常见的启发式函数包罗曼哈顿间隔、欧几里得间隔和对角线间隔等。
关于间隔
曼哈顿间隔
哈顿间隔（Manhattan Distance），也称为L1间隔或城市街区间隔（City Block Distance），是一种度量两个点在标准坐标系上的绝对轴距总和的间隔。在二维空间中，如果有两个点P1(x1, y1)和P2(x2, y2)，它们之间的曼哈顿间隔界说为：
曼哈顿间隔 = ∣ x 2 − x 1 ∣ + ∣ y 2 − y 1 ∣ 曼哈顿间隔=\left | x2-x1 \right | + \left | y2-y1 \right | 曼哈顿间隔=∣x2−x1∣+∣y2−y1∣
这个名称来源于纽约市的街道布局，因为曼哈顿街道呈网格状，从一个街区到另一个街区的最短路径通常是沿着街道走，而不是直线穿越建筑物。
欧几里得间隔
欧几里得间隔（Euclidean Distance），也称为欧氏间隔或L2间隔，是度量两点在欧几里得空间中直线间隔的一种方法。它是最直观的间隔度量方式，即两点之间的直线段长度。
在二维空间中，如果有两个点P1(x1, y1)和P2(x2, y2)，它们之间的欧几里得间隔界说为：
欧几里得间隔 = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 欧几里得间隔=\sqrt{(x2−x1)^2+(y2−y1)^2} 欧几里得间隔=(x2−x1)2+(y2−y1)2
这个公式可以推广到更高维度的空间中。对于n维空间中的两个点P1(p1_1, p1_2, …, p1_n)和P2(p2_1, p2_2, …, p2_n)，它们之间的欧几里得间隔为：
欧几里得间隔 = ( p 2 1 − p 1 1 ) 2 + ( p 2 2 − p 1 2 ) 2 + ⋯ + ( p 2 n − p 1 n ) 2 欧几里得间隔=\sqrt{(p2_1−p1_1)^2+(p2_2−p1_2)^2+\cdots+(p2_n−p1_n)^2} 欧几里得间隔=(p21−p11)2+(p22−p12)2+⋯+(p2n−p1n)2
欧几里得间隔是最直观和常用的间隔度量方式，因为它符合我们对“间隔”的直观理解。然而，在某些情况下，如城市街区或室内导航，直线间隔可能不是最佳的间隔度量方式，这时可能会使用曼哈顿间隔或其他间隔度量方式。
对角线间隔
对角线间隔，有时也被称为切比雪夫间隔（Chebyshev Distance），是一种在多维空间中度量两点之间间隔的方法。它基于如许一个概念：在棋盘上，一个棋子从一个方格移动到对角线相对的方格所需的步数。在二维空间中，如果有两个点P1(x1, y1)和P2(x2, y2)，它们之间的对角线间隔界说为：
对角线间隔 = m a x ( ∣ x 2 − x 1 ∣ , ∣ y 2 − y 1 ∣ ) 对角线间隔=max(\left |x2−x1\right | ,\left |y2−y1\right |) 对角线间隔=max(∣x2−x1∣,∣y2−y1∣)
这个界说可以推广到n维空间中。对于n维空间中的两个点P1(p1_1, p1_2, …, p1_n)和P2(p2_1, p2_2, …, p2_n)，它们之间的对角线间隔为：
对角线间隔 = m a x ( ∣ p 2 1 − p 1 1 ∣ , ∣ p 2 2 − p 1 2 ∣ , ⋯ , ∣ p 2 n − p 1 n ∣ ) 对角线间隔=max(\left |p2_1−p1_1 \right|,|p2_2−p1_2|,\cdots,|p2_n−p1_n|) 对角线间隔=max(∣p21−p11∣,∣p22−p12∣,⋯,∣p2n−p1n∣)
对角线间隔的一个主要优点是它在处理具有差别标准或单位的维度时相对简单和直观。然而，它可能不如欧几里得间隔那样直观，因为它不考虑维度之间的相互作用或角度。在现实应用中，选择哪种间隔度量方式取决于详细题目的性子和需求。
算法头脑
A*算法是对广搜的改进。回顾一下广搜的思路，从出发点开始一圈一圈的向外搜索，直到找到目标节点。在这个过程中实在做了许多无用功，而且当舆图的规模扩大时，其性能也非常下降。
以下面这张图为例，绿色格子是出发点，赤色格子是尽头，黑色是障碍物。
虽然中心有遮挡，但是我们很容易知道，大方向是向右的。所以，广搜的过程中向左扩展的部分实在就是无用功。我们应该优先探求右边的路。
那么如何让扩展出来的格子之间产生优先级呢？这时A*算法的f(n)、g(n)、h(n)函数就派上了用场。f(n) = g(n) + h(n)
- f(n)：总代价
- g(n)：从出发点到当前节点的现实代价
- h(n)：从当前节点到尽头的预期代价
A*算法通过引入预期代价从而包罗了尽头的方向信息。这时间我们就可以从候选节点中选一个总代价最小的节点优先扩展。从代码实现上来说也只需要用优先队列替换本来广搜的普通队列即可。
A*算法的步调可以概括如下：
- 初始化：
- 创建两个集合：开放集（Open Set）和关闭集（Closed Set）。
- 将起始节点参加开放集，并将起始节点的g(n)值设为0，h(n)值根据启发式函数盘算。
- 将起始节点的父节点设为null。
- 循环实验以下步调，直到开放集为空或找到目标节点：
- 选择节点：从开放会合选择具有最低f(n)值的节点，即f(n) = g(n) + h(n)。
- 查抄目标：如果选择的节点就是目标节点，则路径已找到，算法结束。
- 移动节点：将选择的节点从开放集移至关闭集。
- 扩展节点：对于选择的节点的每一个邻居节点：
- 如果邻居节点不在关闭会合，盘算它的g(n)值（从起始节点到邻居节点的成本），并盘算f(n)值。
- 如果邻居节点不在开放会合，将其添加到开放会合，并记载当前节点为其父节点。
- 如果邻居节点已在开放会合，但通过当前节点到达它的g(n)值更低，则更新它的g(n)值和父节点。
- 更新启发式函数：对于每个新参加开放集的节点或更新了g(n)值的节点，重新盘算它的f(n)值。
- 路径重修：
- 一旦找到目标节点，从目标节点开始，通过其父节点回溯到起始节点，构建出完备的路径。
- 输出路径：
代码实现
以卡码网：126. 骑士的攻击为例
题目形貌
在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，盘算从出发点到达目标点所需的最短步数。
棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包罗边界）
输入形貌
第一行包罗一个整数 n，表现测试用例的数目，1 <= n <= 100。
接下来的 n 行，每行包罗四个整数 a1, a2, b1, b2，分别表现骑士的起始位置 (a1, a2) 和目标位置 (b1, b2)。
输出形貌
输出共 n 行，每行输出一个整数，表现骑士从出发点到目标点的最短路径长度。
输入示例
- 6
- 5 2 5 4
- 1 1 2 2
- 1 1 8 8
- 1 1 8 7
- 2 1 3 3
- 4 6 4 6
通过代码：
- #include <iostream>
- #include <queue>
- #include <cmath>
- #include <cstring>
- using namespace std;
- int moves[1001][1001]; // 相当于开放集
- bool close[1001][1001]; // close列表
- int dir[8][2] = {-2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2}; // 移动方向
- struct Node
- {
- int x, y; // 节点位置
- int f, g, h; // 总成本，到当前节点的实际成本，到目标节点的预估成本
- Node() {}
- Node(int a, int b) : x(a), y(b) {}
- bool operator<(const Node &other) const
- {
- return f > other.f;
- }
- };
- bool check(Node node) // 检查节点合法性
- {
- if (node.x < 1 || node.x > 1000 || node.y < 1 || node.y > 1000) // 判断边界
- return false;
- return true;
- }
- int Euclidean(const Node &a, const Node &b) // 欧几里得距离
- {
- return pow(a.x - b.x, 2) + pow(a.y - b.y, 2); // 统一不开根号，这样可以提高精度
- }
- void astar(const Node &start, const Node &end)
- {
- priority_queue<Node> q; // 相当于open list
- q.push(start);
- while (!q.empty())
- {
- Node cur = q.top();
- q.pop();
- close[cur.x][cur.y] = true; // 加入close集
- if (cur.x == end.x && cur.y == end.y) // 到达目标节点
- break;
- for (int i = 0; i < 8; i++)
- {
- Node next = Node(cur.x + dir[i][0], cur.y + dir[i][1]);
- if (!check(next) || close[next.x][next.y]) // 越界和在close集的跳过
- continue;
- if (moves[next.x][next.y] == 0 || moves[cur.x][cur.y] + 1 < moves[next.x][next.y])
- {
- moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
- next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
- next.h = Euclidean(next, end);
- next.f = next.g + next.h;
- q.push(next); // 在开放集但更优的节点我也入队了，因为优先队列会把更小的节点弹出来，所以不影响
- }
- }
- }
- }
- int main()
- {
- int n;
- cin >> n;
- int a1, a2, b1, b2; // 起点和终点坐标
- while (n--)
- {
- cin >> a1 >> a2 >> b1 >> b2;
- Node start = Node(a1, a2), end = Node(b1, b2);
- start.g = 0;
- start.h = Euclidean(start, end);
- start.f = start.g + start.h;
- memset(moves, 0, sizeof(moves));
- memset(close, 0, sizeof(close));
- astar(start, end);
- cout << moves[b1][b2] << endl;
- }
- return 0;
- }
|
