这算是算法的最后一篇了，原本A*之前还有一些相关的最短路径算法的，比如dijkstra的堆优化，SPFA等等，但是有些我没看懂，就不写了，用A*做个结尾。
题目：骑士的攻击
127. 骑士的攻击 (kamacoder.com)
题目描述
在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。
棋盘大小 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输出示例
2
4
6
5
1
0提示信息
骑士移动规则如图，红色是起始位置，黄色是骑士可以走的地方。
题目分析：
在一个平面内，从一点到另外一点，很明显的广搜类题目。我们先来看看广搜怎么写
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
void bfs(int a1,int a2,int b1,int b2){
queue<int> que;
que.push(a1);
que.push(a2);
while(!que.empty()){
int m=que.front();que.pop();
int n=que.front();que.pop();
if(m == b1 && n == b2)
break;
for(int i=0;i<8;i++){
int mm=m+dir[i][0];
int nn=n+dir[i][1];
if(mm < 1 || mm > 1000 || nn < 1 || nn > 1000)
continue;
if(!moves[mm][nn]){
moves[mm][nn]=moves[m][n]+1;
que.push(mm);
que.push(nn);
}
}
}
}
int main(){
int n;
int a1,a2,b1,b2;
cin>>n;
while(n--){
cin>>a1>>a2>>b1>>b2;
memset(moves,0,sizeof(moves));//分配空间,填入0
bfs(a1,a2,b1,b2);
cout << moves[b1][b2] << endl;
}
return 0;
}虽然能解出来，但是由于棋盘太大了，会超时。
我们来看看A*的思路
A*实际上就是一直启发式的遍历，它也可以通过dijkstra和广搜写出来，主要区别在于给我们的图是什么样的，像无权图，广搜就可以了，如果带权值，那么使用dijkstra会简便一些。
那么A*的启发性是什么意思呢？
这个是常规广搜的遍历过程，他会一圈一圈的去搜索
这是A*的遍历过程，可以看到他的遍历是带有方向性的。
那么这个启发性是怎么来的呢？在广搜中我们获取需要遍历的结点是这样的，从队列中取出队首元素
int m=que.front();que.pop();
int n=que.front();que.pop();而这个取出的结点就是我们需要控制的，我们给队列中的元素给一个权值并且排序。
每个节点的权值为F，给出公式为：F = G + H
G：起点达到目前遍历节点的距离
H：目前遍历的节点到达终点的距离
起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离 就是起点到达终点的距离。
本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：
- 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
- 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
- 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
x1, x2 为起点坐标，y1, y2 为终点坐标 ，abs 为求绝对值，sqrt 为求开根号，
选择哪一种距离计算方式 也会导致 A * 算法的结果不同。
本题，采用欧拉距离才能最大程度体现 点与点之间的距离。
所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）
那么我们在求出权值之和，根据权值确定我们需要取出的结点然后再去遍历即可。
看看代码实现
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int moves[1001][1001];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F = G + H
// G = 从起点到该节点路径消耗
// H = 该节点到终点的预估消耗
struct Knight{ //记录位置以及权值信息
int x,y;
int g,h,f;
bool operator < (const Knight & k) const{ // 重载运算符， 从小到大排序
return k.f < f;
}
};
priority_queue<Knight> que;//优先队列
int Heuristic(const Knight& k) { // 欧拉距离
return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度
}
void astar(const Knight& k)
{
Knight cur, next;
que.push(k);
while(!que.empty())
{
cur=que.top(); que.pop();
if(cur.x == b1 && cur.y == b2)
break;
for(int i = 0; i < 8; i++)
{
next.x = cur.x + dir[i][0];
next.y = cur.y + dir[i][1];
if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
continue;
if(!moves[next.x][next.y])
{
moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
// 开始计算F
next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
next.h = Heuristic(next);
next.f = next.g + next.h;
que.push(next);
}
}
}
}
int main()
{
int n, a1, a2;
cin >> n;
while (n--) {
cin >> a1 >> a2 >> b1 >> b2;
memset(moves,0,sizeof(moves));
Knight start;
start.x = a1;
start.y = a2;
start.g = 0;
start.h = Heuristic(start);
start.f = start.g + start.h;
astar(start);
while(!que.empty()) que.pop(); // 队列清空
cout << moves[b1][b2] << endl;
}
return 0;
}
需要注意的是
A * 算法并不能保证一定是最短路，因为在设计 启发式函数的时候，要考虑 时间效率与准确度之间的一个权衡。
另外，给出 多个可能的目标，然后在这多个目标中 选择最近的目标，这种 A * 就不擅长了， A * 只擅长给出明确的目标 然后找到最短路径。
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。
代码随想录 (programmercarl.com)
已刷题目：145
那么算法日记就完结啦。近150题，各种类型都有，接下来就是二刷啦。