启发式搜索是利用问题自身特性信息（启发信息）来引导搜索过程，达到减少搜索范围，降低问题复杂度的搜索方法。
简介
上度娘一搜，会发现启发式搜索与当下正热门的人工智障智能算法有关系，不过我们要谈的是 OI 中的启发式搜索，它们本质上就是一种算法在不同领域的应用罢了。
启发式搜索本身就是为了更快地寻找出最优解，但是如果启发信息太强可能会导致找不到最优解，而太弱又会导致超时，因此它只是尽可能找出最优解而不保证最优解。
一般的话，想要用启发式搜索，需要知道目标状态是什么（当然起始状态也需要啊），到目标状态的步数就是一个启发信息。
让我们定义一个函数 ，叫做估价函数， 表示从起始状态到现在状态的步数， 表示到目标状态的最小估计步数，称为启发函数。
举个栗子
就拿Luogu P1379 八数码难题来说吧。 这道题的题意可以很好地用图来表示。 我们需要把棋盘上乱放的八个数字挪到目标位置，这就是我们需要的目标状态，如下图：
拿样例来说，初始状态是这样的：
发现 都不在原来的位置上。
一般思路
一般像这样的题目就是搜索，如果不用启发式搜索就用广搜(BFS)或深搜(DFS)。
当然这道题裸的深搜很显然会超时，如果不限制搜索深度的话可能会一直搜索下去，而且会存在很多重复的搜索。 如果用裸的广搜呢？也会存在很多重复的搜索，如果不加以处理空间要上天，而判重操作又会耗费时间。
不过由于有目标状态，有些 dalao 提出了双向广搜（洛谷题解上就有很多）。
但是我们着重要处理的是启发式搜索思路。
估价函数
，其中 表示当前棋子偏移目标位置的步数和。
我们可以考虑基于 DFS，那么 就是搜索的深度。
定义 step 数组，记录每两个点之间的最小步数，即最小曼哈顿距离，可以先预处理完成。
这是每个格子的编号：
代码如下：
for (int i = 1; i <= 9; i++)
for (int j = i + 1; j <= 9; j++)
step[i][j] = step[j][i] = (getx(j) - getx(i)) + abs(gety(i) - gety(j));其中 getx() 和 gety() 函数都是获取当前编号坐标信息的。
像这样写：
int getx(int x) {
return (x - 1) / 3 + 1;
}
int gety(int x) {
return x % 3 ? x % 3 : 3;
}step 数组应该是这样滴
当然还需要有目标信息，aim 数组下标对应的就是棋盘格子编号，比如0应该在编号为5的格子里，那么 aim[0] = 5。
所以 aim[10] = {5,1,2,3,6,9,8,7,4}
启发函数 的计算：
int calc() {
int sum = 0;
for (int i = 1; i <= 9; i++)
sum += step[now[i]][aim[i]];
return sum;
}估价函数应该是搜索深度+calc()的值
搜索？
启发式搜索和一般的搜索最大的区别在于，它知道下一个要搜索的结点的优先度，估价函数就是用来评估下一个搜索结点的好坏程度的。显然，越好的结点越优先搜索。 而一般的搜索对于下一个要搜索的结点全然不知，对待它们的优先程度都是一样的。
有一种算法叫 A 算法，它往往是最极端的，也就是说，它永远挑最好的结点去进行搜索，但是估价函数毕竟的估计的，得到的结果不一定是最优的，但这样做效率很高。
A* 算法是在 A 算法的基础上，进行一种偏于保守的估计，它对下一个搜索的结点更加宽容一点~~（和极端的 A 算法相比，是不是更人性化呢？）~~，所以 A* 算法中，启发函数的值一定要≤实际当前状态到目标状态的步数。
设计
定义一个 now 数组，保存数组下标的位置。
需要判断是否达到目标状态：
bool check() {
for (int i = 1; i <= 9; i++)
if (now[i] != aim[i]) return false;
return true;
}DFS 应该这么写：
struct loc {int x, y;};
void dfs(int dep, loc nowloc) { // nowloc 表示当前搜索的位置
if (dep + calc() > cnt) return; // 估价函数，其中 cnt 是当前记录的步数，排除不好的搜索结点
if (check()) {
flag = true;
return;
}
for (int i = 1; i <= 4; i++) {
int x = nowloc.x, y = nowloc.y;
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3) {
swap(save[x][y], save[nx][ny]);
swap(now[save[x][y]], now[save[nx][ny]]);
loc newloc = (loc){nx, ny};
dfs(dep + 1, newloc); // 递归进行下一步搜索
swap(save[x][y], save[nx][ny]); // 回溯
swap(now[save[x][y]], now[save[nx][ny]]);
}
}
}数据的读入就不用说了吧...(～￣▽￣)～
代码
#include <bits/stdc++.h>
using namespace std;
const int aim[10] = {5,1,2,3,6,9,8,7,4};
const int dx[5] = {0,0,0,1,-1}, dy[5] = {0,1,-1,0,0};
int board[5][5], save[5][5], now[10];
int cnt, step[10][10];
bool flag;
struct loc {
int x, y;
}blank;
int getx(int x) {
return (x - 1) / 3 + 1;
}
int gety(int x) {
return x % 3 ? x % 3 : 3;
}
void init() {
for (int i = 1; i <= 9; i++)
for (int j = i + 1; j <= 9; j++)
step[i][j] = step[j][i] = (getx(j) - getx(i)) + abs(gety(i) - gety(j));
}
int calc() {
int sum = 0;
for (int i = 1; i <= 9; i++)
sum += step[now[i]][aim[i]];
return sum;
}
bool check() {
for (int i = 1; i <= 9; i++)
if (now[i] != aim[i]) return false;
return true;
}
void dfs(int dep, loc nowloc) {
if (dep + calc() > cnt) return;
if (check()) {
flag = true;
return;
}
for (int i = 1; i <= 4; i++) {
int x = nowloc.x, y = nowloc.y;
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3) {
swap(save[x][y], save[nx][ny]);
swap(now[save[x][y]], now[save[nx][ny]]);
loc newloc = (loc){nx, ny};
dfs(dep + 1, newloc);
swap(save[x][y], save[nx][ny]);
swap(now[save[x][y]], now[save[nx][ny]]);
}
}
}
int main() {
init();
for (int i = 1; i <= 9; i++) {
int x = getx(i), y = gety(i);
int num = getchar() - '0';
now[num] = i;
board[x][y] = num;
if (!num) blank = (loc){x, y};
}
for (cnt = 0; ; cnt++) {
memcpy(save, board, sizeof(board));
dfs(0, blank);
if (flag) {
cout << cnt << endl;
break;
}
}
}