当前位置 博文首页 > nameofcsdn的博客：启发式搜索
?
相对于经典搜索（无信息搜索），搜索方式只取决于搜索空间的直观结构，和数据之间的直观关系（一般就是朴素的大小关系），启发式搜索引入了一种基于数据的抽象关系，用来引导更快的接近搜索目标。
?
DFS、BFS?https://blog.csdn.net/nameofcsdn/article/details/111918584
双向BFS?https://blog.csdn.net/nameofcsdn/article/details/116701760
一致代价搜索（Uniform-cost Search,UCS），其实就是迪杰斯特拉，https://blog.csdn.net/nameofcsdn/article/details/115677806
?
也叫最佳优先搜索，关于为什么叫A算法，没找到具体的解释，据说和admissible?这个词有关：A search algorithm is said to be?admissible?if it is guaranteed to return an optimal solution.??optimal即最佳的。但是A算法并不能保证得到最优路径，所以这就很迷惑了。
A算法思路：
和BFS一样，初始队列中只有起点，然后每次取出一个点，把与它的相邻的不在队列中的点都加入到队列中，直到到达终点。
不同之处在于，BFS实际上是根据起点到每个点的距离进行排序的，而A算法需要根据每个点到终点的估计距离进行排序。
以HackerRank - pacman-astar为例，https://blog.csdn.net/nameofcsdn/article/details/116701760
A算法代码：
#include<iostream>
#include<queue>
#include<unordered_map>
#include<stack>
#include<vector>
using namespace std;
#define M 100
char ch[M][M];
int row, col;
struct Point
{
int x, y;
};
Point s, e;
int PtoI(Point s)
{
return s.x * M + s.y;
}
Point ItoP(int x)
{
return { x / M,x % M };
}
bool inBoard(Point s)
{
return s.x >= 0 && s.x < row&& s.y >= 0 && s.y < col;
}
bool available(Point s)
{
return ch[s.x][s.y] != '%';
}
vector<Point> neighbor(Point s)
{
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
Point t;
vector<Point>ans;
for (int i = 0; i < 4; i++)
{
t.x = s.x + dx[i], t.y = s.y + dy[i];
if (!inBoard(t))continue;
if (!available(t))continue;
ans.push_back(t);
}
return ans;
}
int h(Point a)
{
return abs(a.x - e.x) + abs(a.y - e.y);
}
class cmp
{
public:
bool operator()(Point a, Point b)
{
return h(a) > h(b);
}
};
int main()
{
cin >> s.x >> s.y >> e.x >> e.y;
cin >> row >> col;
for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)cin >> ch[i][j];
priority_queue<Point, vector<Point>, cmp>q;
q.push(s);
unordered_map<int, int>m;
m[PtoI(s)] = 1;
while (true)
{
s = q.top();
q.pop();
if (m[PtoI(e)])break;
vector<Point>v = neighbor(s);
for (auto vs : v)
{
if (m[PtoI(vs)])continue;
m[PtoI(vs)] = m[PtoI(s)] + 1;
q.push(vs);
}
}
cout << m[PtoI(e)] -1 << endl;
s = e;
stack<Point>sp;
for (int i = m[PtoI(e)]; i > 1; i--)
{
sp.push(s);
vector<Point>v = neighbor(s);
for (auto vs : v)
{
if (m[PtoI(vs)] == i - 1) {
s = vs;
break;
}
}
}
sp.push(s);
while (!sp.empty()) {
s = sp.top();
cout << s.x << " " << s.y << endl;
sp.pop();
}
return 0;
}A算法最大的问题在于，往往得不到最优解，比如如下数据：
2 7
2 0
6 8
--------
-%%%%%%-
.%%%---P
-%%%----
-%------
--------
A算法输出的是13，
双向BFS输出的是11，这才是最优解。
?
A*，中文名A星，英文名A star
A*搜索是在A算法的基础之上加以改进，保证能得到最优解，而且搜索速度很快。
?
?
