A*
Definition
A* search algorithm, referred to as A* algorithm, is an algorithm that finds the lowest pass cost for a path with multiple nodes on the graphics plane. It belongs to graph traversal and best-first search algorithm, and is also an improvement of BFS.
Algorithm
Define the starting point s, the end point t, the distance function g(x) starting from the starting point (initial state), and the distance function h(x) to the end point (final state), h*(x), and the valuation function of each point f(x) = g(x) + h(x).
A* algorithm takes out an f smallest element from the priority queue each time, and then updates the adjacent state.
If h ≤ h*, then the A* algorithm can find the optimal solution.
Under the above conditions, if h satisfies the triangle inequality, the A* algorithm will not add duplicate nodes to the queue.
When h = 0, A* algorithm is reduced to Dijkstra Algorithm. When h=0 and the edge weight is 1, it becomes is BFS.
Example
On the 3 × 3 chessboard, there are eight chess pieces, each of which is marked with a number from 1 to 8. There is a space left on the board, and the space is represented by 0. The pieces around the spaces can be moved into the spaces so that their original positions become spaces. Given an initial layout and a target layout (to make the question simple, assume the target state is as follows), find a method of moving from the initial layout to the target layout with the fewest steps.
123
804
765
It is easy to see that this problem can be easily transformed into a standard program for solving the problem using the A* algorithm.
The initial state is at node s, the final state is at node t, the distance function is the distance traveled from s to the current node, and the valuation function is from the current node to node t The minimum distance to be traveled is the shortest path from the current node to node t.
In this way, we build the graph in reverse during preprocessing, calculate the shortest path from node t to all points, then stuff the initial state into the priority queue, and take out f(x) = g(x) each time +h(x) The smallest item, calculate the information of its connected point and put it into the queue. When you walk to node t for the k th time, the k short circuit from node s to node t is also calculated.
Due to the designed distance function and valuation function, each state needs to store two parameters, the current node x and the distance traveled v.
We can add a little optimization on this basis: since we only need to find the kth short-circuit, when we go to the node for the (k+1)th time or more, we directly skip this state. Because when you go to this point the previous k times, you will definitely be able to construct k paths, so there is no need to add edges later.
Suggested Solution
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int fx, fy;
char ch;
struct matrix {
int a[5][5];
bool operator<(matrix x) const {
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (a[i][j] != x.a[i][j]) return a[i][j] < x.a[i][j];
return false;
}
} f, st;
int h(matrix a) {
int ret = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (a.a[i][j] != st.a[i][j]) ret++;
return ret;
}
struct node {
matrix a;
int t;
bool operator<(node x) const { return t + h(a) > x.t + h(x.a); }
} x;
priority_queue<node> q; // 搜索队列
set<matrix> s; // 防止搜索队列重复
int main() {
st.a[1][1] = 1; // 定义标准表
st.a[1][2] = 2;
st.a[1][3] = 3;
st.a[2][1] = 8;
st.a[2][2] = 0;
st.a[2][3] = 4;
st.a[3][1] = 7;
st.a[3][2] = 6;
st.a[3][3] = 5;
for (int i = 1; i <= 3; i++) // 输入
for (int j = 1; j <= 3; j++) {
scanf(" %c", &ch);
f.a[i][j] = ch - '0';
}
q.push({f, 0});
while (!q.empty()) {
x = q.top();
q.pop();
if (!h(x.a)) { // 判断是否与标准矩阵一致
printf("%d\n", x.t);
return 0;
}
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
if (!x.a.a[i][j]) fx = i, fy = j; // 查找空格子（0号点）的位置
for (int i = 0; i < 4; i++) { // 对四种移动方式分别进行搜索
int xx = fx + dx[i], yy = fy + dy[i];
if (1 <= xx && xx <= 3 && 1 <= yy && yy <= 3) {
swap(x.a.a[fx][fy], x.a.a[xx][yy]);
if (!s.count(x.a))
s.insert(x.a),
q.push({x.a, x.t + 1}); // 这样移动后，将新的情况放入搜索队列中
swap(x.a.a[fx][fy], x.a.a[xx][yy]); // 如果不这样移动的情况
}
}
}
return 0;
}