好的空间网站,银川网站seo,dw网页设计模板制作过程,网站建设后期需要后期做的这算是算法的最后一篇了#xff0c;原本A*之前还有一些相关的最短路径算法的#xff0c;比如dijkstra的堆优化#xff0c;SPFA等等#xff0c;但是有些我没看懂#xff0c;就不写了#xff0c;用A*做个结尾。
题目#xff1a;骑士的攻击 127. 骑士的攻击 (kamacoder.co…这算是算法的最后一篇了原本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
提示信息
骑士移动规则如图红色是起始位置黄色是骑士可以走的地方。 题目分析 在一个平面内从一点到另外一点很明显的广搜类题目。我们先来看看广搜怎么写
#includeiostream
#includequeue
#includestring.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){queueint que;que.push(a1);que.push(a2);while(!que.empty()){int mque.front();que.pop();int nque.front();que.pop();if(m b1 n b2)break;for(int i0;i8;i){int mmmdir[i][0];int nnndir[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;cinn;while(n--){cina1a2b1b2;memset(moves,0,sizeof(moves));//分配空间,填入0bfs(a1,a2,b1,b2);cout moves[b1][b2] endl;}return 0;
}
虽然能解出来但是由于棋盘太大了会超时。
我们来看看A*的思路
A*实际上就是一直启发式的遍历它也可以通过dijkstra和广搜写出来主要区别在于给我们的图是什么样的像无权图广搜就可以了如果带权值那么使用dijkstra会简便一些。
那么A*的启发性是什么意思呢
这个是常规广搜的遍历过程他会一圈一圈的去搜索 这是A*的遍历过程可以看到他的遍历是带有方向性的。 那么这个启发性是怎么来的呢在广搜中我们获取需要遍历的结点是这样的从队列中取出队首元素 int mque.front();que.pop();int nque.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 * 算法的结果不同。
本题采用欧拉距离才能最大程度体现 点与点之间的距离。
所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 路径可能不同但路径上的节点数是相同的
那么我们在求出权值之和根据权值确定我们需要取出的结点然后再去遍历即可。
看看代码实现
#includeiostream
#includequeue
#includestring.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_queueKnight 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()){curque.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;// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.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题各种类型都有接下来就是二刷啦。
