题解 P1746 【离开中山路】
Ciyang
·
·
题解
此题好像还没有启发式搜索A Star算法题解,我就水一发.
以下废话:
两三天我为了学A Star算法,随便找了这道BFS伪模板水题来练习,当时对A Star了解的不够深刻,因为自己的问题,只能拿40分.
经过三天的更深层研究后,终于找到了问题所在,修改代码后AC.
以下是A Star简介:
A Star算法通常用来寻路,是启发式搜索的一种,它与DFS,BFS搜索方式略不相同.如果你熟悉BFS就很好理解,因为BFS可以算是A Star算法中极端的一种.所以我打算将BFS与A Star进行比较说明.
在BFS算法中,每一个格子向外扩展的优先级就是自己的步数,因为步数少的先进入搜索队列.在A Star算法中,每一个格子向外扩展的优先级需要计算,通过估步函数后,每个格子就带上了权值,代表它的优先级.
再来看BFS,通常扩展后的格子放在普通的队列中,队列是先进先出的,所以先搜到的格子先进行扩展.而A Star算法一般使用优先队列(二叉堆),所以后进去的格子,有可能因为优先级高排在在队列前端,很快就开始扩展此格子,来搜索下一步.
说到估步函数,一般叫评价函数,就是计算某个格子优先级的函数.在这个题中,要计算平面最短路径,所以f(优先级)=step(到达此格子的最小步数)+h(与终点的曼哈顿距离)
先放上部分代码,再继续讲解:
bool closelist[1002][1002], openlist[1002][1002];
//关闭列表和开放列表
struct node {
int x, y, step, f, h;
void init(int _x, int _y, int _step) {
x= _x;
y= _y;
step= _step;
h= abs(x - wx) + abs(y - wy);
//曼哈顿距离
f= step + h;
//f为已走步数+到达目标需要距离
}
void update(int _step) {
step= _step;
f= step + h;
}
int abs(int _a) {
return _a > 0 ? _a : -_a;
}
} newn[1002][1002];
struct nodecmp {
bool operator()(node *&a, node *&b) const {
if(a->f == b->f) return a->h > b->h;
return a->f > b->f;
//小根堆,f越低在小根堆里越靠前,f一样就选离目标近的
}
};
int lx, ly, lstep, newx, newy;
void Astar() {
priority_queue<node *, vector<node *>, nodecmp> q;
//优先队列存放的是指针,存放指针后默认是指针的从小到大排序
//因此不能重载<运算符,要把比较函数写到一个类里
newn[bx][by].init(bx, by, 0);
q.push(&newn[bx][by]);
while(!q.empty()) {
lx= q.top()->x;
ly= q.top()->y;
lstep= q.top()->step;
q.pop();
closelist[lx][ly]= true;
//将此点放到关闭列表,进行扩展
for(int i= 0; i < 4; i++) {
newx= lx + moves[i][0], newy= ly + moves[i][1];
if(tmap[newx][newy] == '1' || closelist[newx][newy]) continue;
if(newx == wx && newy == wy) {
//到达目标结束搜索
ans= lstep + 1;
return;
}
if(openlist[newx][newy]) {
//如果扩展后的点已经存在于开放列表
if(lstep < newn[newx][newy].step) {
//比较步数,更新扩展后的点
newn[newx][newy].update(lstep + 1);
}
}
else {
//如果扩展后的点不存在于开放列表
newn[newx][newy].init(newx, newy, lstep + 1);
q.push(&newn[newx][newy]);
openlist[newx][newy]= true;
//将扩展后的点放入优先队列和开放列表中
}
}
}
return;
}
我的代码还是可以优化的,有些地方为了写着容易而耗费了运行时间空间.
A Star在实现时有两个bool二维数组,一个优先队列(可以手写会更快).
这两个bool二维数组分别是开放列表(OpenList)和关闭列表(CloseList),分别代表某个方格是否已经在队列中,某个方格是否已经向外扩展过
我在代码中用优先队列存指针,不存指针而是存元素也可以,时间空间差不了太多,貌似是不用指针好,不用指针的话还可以省略更新节点的操作,只不断向优先队列push就够了(我感觉指针省空间,但结果相反)
对于这个题,别的就没什么了,学会BFS搜索后,这种较为普通的A Star寻路只不过多了优先级.而对于更高深的启发式搜索题,才是A Star算法的真面目(好奇怪).
若想更好了解学习A Star,可以试试 【模板】k短路（[SDOI2010]魔法猪学院）,就是有一个点卡A Star会MLE.
下面附上完整代码:
#include <iostream>
#include <stdio.h>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
int n, bx, by, wx, wy, moves[4][2]= {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}, ans;
bool closelist[1002][1002], openlist[1002][1002];
char tmap[1002][1002];
struct node {
int x, y, step, f, h;
void init(int _x, int _y, int _step) {
x= _x;
y= _y;
step= _step;
h= abs(x - wx) + abs(y - wy);
f= step + h;
}
void update(int _step) {
step= _step;
f= step + h;
}
int abs(int _a) {
return _a > 0 ? _a : -_a;
}
} newn[1002][1002];
struct nodecmp {
bool operator()(node *&a, node *&b) const {
if(a->f == b->f) return a->h > b->h;
return a->f > b->f;
}
};
int lx, ly, lstep, newx, newy;
void Astar() {
priority_queue<node *, vector<node *>, nodecmp> q;
newn[bx][by].init(bx, by, 0);
q.push(&newn[bx][by]);
while(!q.empty()) {
lx= q.top()->x;
ly= q.top()->y;
lstep= q.top()->step;
q.pop();
closelist[lx][ly]= true;
for(int i= 0; i < 4; i++) {
newx= lx + moves[i][0], newy= ly + moves[i][1];
if(tmap[newx][newy] == '1' || closelist[newx][newy]) continue;
if(newx == wx && newy == wy) {
ans= lstep + 1;
return;
}
if(openlist[newx][newy]) {
if(lstep < newn[newx][newy].step) {
newn[newx][newy].update(lstep + 1);
}
}
else {
newn[newx][newy].init(newx, newy, lstep + 1);
q.push(&newn[newx][newy]);
openlist[newx][newy]= true;
}
}
}
return;
}
int main() {
cin >> n;
for(int i= 0; i <= n + 1; i++) {
for(int j= 0; j <= n + 1; j++) {
if(i == 0 || j == 0 || i == n + 1 || j == n + 1)
tmap[i][j]= '1';
else
cin >> tmap[i][j];
}
}
cin >> bx >> by >> wx >> wy;
Astar();
cout << ans << endl;
return 0;
}