启发式搜索是利用问题自身特性信息(启发信息)来引导搜索过程,达到减少搜索范围,降低问题复杂度的搜索方法。

简介

上度娘一搜,会发现启发式搜索与当下正热门的人工智障智能算法有关系,不过我们要谈的是 OI 中的启发式搜索,它们本质上就是一种算法在不同领域的应用罢了。

启发式搜索本身就是为了更快地寻找出最优解,但是如果启发信息太强可能会导致找不到最优解,而太弱又会导致超时,因此它只是尽可能找出最优解而不保证最优解。

一般的话,想要用启发式搜索,需要知道目标状态是什么(当然起始状态也需要啊),到目标状态的步数就是一个启发信息。

让我们定义一个函数 $f(n)=g(n)+h(n)$,叫做估价函数,$g(n)$ 表示从起始状态到现在状态的步数,$h(n)$ 表示到目标状态的最小估计步数,称为启发函数

举个栗子

就拿Luogu P1379 八数码难题来说吧。
这道题的题意可以很好地用图来表示。
我们需要把棋盘上乱放的八个数字挪到目标位置,这就是我们需要的目标状态,如下图:


拿样例来说,初始状态是这样的:

发现 $1,2,8$ 都不在原来的位置上。

一般思路

一般像这样的题目就是搜索,如果不用启发式搜索就用广搜(BFS)或深搜(DFS)。

当然这道题裸的深搜很显然会超时,如果不限制搜索深度的话可能会一直搜索下去,而且会存在很多重复的搜索。
如果用裸的广搜呢?也会存在很多重复的搜索,如果不加以处理空间要上天,而判重操作又会耗费时间。

不过由于有目标状态,有些 dalao 提出了双向广搜(洛谷题解上就有很多)。

但是我们着重要处理的是启发式搜索思路。

估价函数

$f(n)=g(n)+h(n)$,其中 $h(n)$ 表示当前棋子偏移目标位置的步数和。
我们可以考虑基于 DFS,那么 $g(n)$ 就是搜索的深度。
定义 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}

启发函数 $h(n)$ 的计算:

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;
        }
    }
}