搜索（8）

A * 算法展开目录

很多人应该都玩过类似下面这样的拼图游戏（华容道）：

为了简化题目，我们只使用 3x3 的规模，并且按照从上到下，从左至右，将每块拼图标记为正确位置的编号

上图中左边是初始的状态，而我们的目的是利用空格 (灰色区域) 作为辅助，将初始状态转变为右图的状态。每一次移动，我们可以将空格与它周围的方块交换位置

根据描述，能够看出这个问题仍然是一个通过宽度优先搜索来解决的最短路径问题

首先我们通过具体的例子来对它进行分析：

为了简化状态表示，我们按照从上到下，从左到右的顺序将 3x3 的矩阵拉伸为 1x9，则每一个状态都可以通过一个包含数字 0~8 的字符串表示。比如状态 (1) 可以表示为 302581647，状态 (2) 可以表示为 032581647

同时，我们也发现在该问题的搜索过程中可能会出现一个状态被多次搜索到的情况，比如图中的状态 (1)，状态 (6) 和状态 (7)。因此搜索过程中，我们需要记录下每一个状态是否被搜索到过，避免重复搜索

我们先来分析一下状态空间，也就是一共有多少种不同的状态。显然每一个状态都对应了 0~8 的一个排列，所以一共有 9!=362880 种状态。这个状态总数并不算大

在上一节中，我们提到过将状态编码成一个整数的办法。在这道题中，我们一般有两种编码的方法。第一种是把一个状态就看成一个 9 位数，比如上图中的状态 (1) 就编码成整数 302581647。这样编码的好处是简单直观，编码和解码的程序写起来都很容易。缺点是由于状态的值域最大到 876543210，没办法用数组 int steps [] 存储一个状态的最短路径，因为数组下标范围太大了

另一种编码方法就是我们真的把一个状态，也就是一个排列，与 1~9!（362880）中的一个整数一一对应起来。这样我们就能用数组保存状态相关的数据了。下标的值就代表状态

举个例子，我们知道排列是可以按照字典序进行排序的，比如对于 1~3 的全排列来说，有顺序：{123,132,213,231,312,321}。我们可以将其对应到 0~5，123 对应了 0，231 对应了 3。根据一个排列在全排列中的次序编号来表示它，这种编码方法可以保持紧凑，极大的减小空间的开销

那么又产生了一个新的问题，如何计算一个排列在全排列中的次序？这里我们要介绍一个成熟的数学算法，叫做康托展开

康托展开展开目录

对于一个排列 {num [1],num [2],...,num [n]}，其在全排列中序号 X 的计算公式为：

X = a[1]*(n-1)!+a[2]*(n-2)!+...+a[i]*(n-i)!+...+a[n-1]*1!+a[n]*0!
其中a[i]表示在num[i+1..n]中比num[i]小的数的数量

举个例子，比如计算 213 在 1~3 的全排列中的位置：

num[] = {2, 1, 3}
a[] = {1, 0, 0}
X = 1 * 2! + 0 * 1! + 0 * 0! = 2

在前面的例子中也确实能够看到 213 对应的序号为 2

康托展开的伪代码：

Cantor(num[])
    x = 0
    For i = 1...n
        tp = 0
        For j = i+1...n
            If(num[j] < num[i])
                tp++
            End If
        End For
        x = x + tp * (n - i)!
    End for
    Return X

该段代码中，使用了临时变量 tp 来表示 a [i]，通过循环去统计 a [i] 的值。最后利用阶乘的常量来节省计算阶乘的时间。实现一次康托展开的时间复杂度为 O (L^2)，其中 L 是排列中的元素个数

有了康托展开，我们还需要逆康托展开，用来从一个整数序号求出对应的排列。逆康托展开的伪代码如下：

unCantor(X)
    a = []
    num = []
    used = []//长度为n的bool数组，初始值为false
    For i = 1...n
        a[i] = X / (n - i)!
        X = X mod (n - i)!
        cnt = 0
        For j = 1...n
            If(used[j)
                cnt++
                If(cnt == a[i] + 1)
                    num[i] = j
                    used[j] = true
                    break
                End If
            End If
        End For
    End For
    Return num

继续说 A * 算法展开目录

在 A * 搜索的过程中，不再是按照状态进入队列的顺序进行搜索，而是提出了一种 “最有希望是最短路径” 的概念

我们通过一个启发式函数 F 来计算一个状态的优先级 f， f 由 2 个部分的和组成：f = g + h

1. g 就是普通宽度优先搜索中的从起始状态到当前状态的代价，比如在八数码的问题中，g 就等于从初始状态到当前状态的最少步数
2. h 是一个估计值，表示从当前状态到目标状态估计的代价，在该问题中就是从当前状态到目标状态的可能最少步数

所以 f 值描述了如果我们从这个状态继续往下搜索，搜到的解大概有多好，有多优。A * 算法找最短路的主要思路就是优先扩展 f 值比较优也就是比较小的状态

其中 g 值是在计算过程中得到的确切的数值，而 h 值是由我们自己设计的一个估价函数计算得到的结果。h 函数设计的好坏，将会直接影响到启发式搜索的算法效率

在设计评估函数 h 时，需要注意一个很重要的要求：评估函数的值一定要小于等于实际当前状态到目标状态的代价（步数）

只要满足这个要求，A 星算法第一次搜到目标状态，经过的步数就是最短的步数。并且，在满足这个要求的前提下，h 函数值越大，搜索速度就越快。反之，当 h==0 时，A 星算法就退化成了宽搜 BFS

如果你的 h 函数过大，比实际当前状态到目标状态的步数还要大，那么就可能错过最优解。也就是第一次搜到目标状态，经过的步数可能不是最少的步数

考虑到以上 h 函数的要求，在八数码问题中，一个比较常用的 h 函数是，统计在当前状态下每块拼图到目标位置曼哈顿距离之和

举个例子：

该例子中数字 1~8 到目标位置的距离之和计算为：

数字：1 2 3 4 5 6 7 8

距离：0 + 1 + 3 + 3 + 1 + 0 + 0 + 2 = 10

得到该状态的 h 值为 10

在 A 星搜索中，每一次我们从候选队列中选取状态也不再按照先进先出的顺序，而是从已知的还未扩展的状态中选取最优的一个，在八数码问题中为选取 f 值最小的一个。因此我们需要维护两个队列，openlist 和 closelist

在 openlist 中的状态，其 f 值还可能发生变化。我们将还未扩展的状态放置于此。而在 closelist 中的状态，其 f 值一定不会再发生改变，也就是说该状态的最短路已经确定了。将已经扩展过的状态放入 closelist

最后整个算法的流程为：

1. 计算初始状态的 f 值，并将其加入 openlist
2. 从 openlist 中取出 f 值最小的状态 u，并将 u 加入 closelist。若 u 为目标状态，结束搜索；
3. 对 u 进行扩展，假设其扩展的状态为 v：若 v 未出现过，计算 v 的 f 值并加入 openlist；若 v 在 openlist 中，更新 v 的 F 值，取较小的一个；若 v 在 closelist 中，抛弃该状态
4. 若 openlist 为空，结束搜索。否则回到 2

第 2 步会被反复执行，所以我们要经常从 openlist 中取出最小的。一般使用堆实现这个功能的。不过第 3 步中，更新 v 的 F 值，取较小的一个，如果用堆的话需要支持修改操作的堆。C++ STL 里的 priority_queue 并不支持修改元素，所以需要自己写堆，或者使用 set 代替

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <set>
using namespace std;
const int exchange[9][9] = {
    {0,1,0,1,0,0,0,0,0},
    {1,0,1,0,1,0,0,0,0},
    {0,1,0,0,0,1,0,0,0},
    {1,0,0,0,1,0,1,0,0},
    {0,1,0,1,0,1,0,1,0},
    {0,0,1,0,1,0,0,0,1},
    {0,0,0,1,0,0,0,1,0},
    {0,0,0,0,1,0,1,0,1},
    {0,0,0,0,0,1,0,1,0}
};
const int value[9][9] = {
    {0,1,2,1,2,3,2,3,4},
    {1,0,1,2,1,2,3,2,3},
    {2,1,0,3,2,1,4,3,2},
    {1,2,3,0,1,2,1,2,3},
    {2,1,2,1,0,1,2,1,2},
    {3,2,1,2,1,0,3,2,1},
    {2,3,4,1,2,3,0,1,2},
    {3,2,3,2,1,2,1,0,1},
    {4,3,2,3,2,1,2,1,0}
};
unordered_map<int,int> f,g_step,sta;
set<pair<int,int>> pq;
int encode(int *a)
{
    int ret = 0;
    for(int i = 0;i < 9;i++)
        ret = ret * 10 + a[i];
    return ret;
}
int decode(int u,int *a)
{
    int ret = 0;
    for(int i = 8;i >= 0;i--)
    {
        a[i] = u % 10;
        u /= 10;
        if(a[i] == 0)
            ret = i;
    }
    return ret;
}
int evaluate(int *a)
{
    int ret = 0;
    for(int i = 0;i < 9;i++)
        if(a[i] != 0)
            ret += value[a[i] - 1][i];
    return ret;
}
void mySwap(int x,int y,int *a)
{
    int box;
    box = a[x];
    a[x] = a[y];
    a[y] = box;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        pq.clear();
        sta.clear();
        f.clear();
        g_step.clear();
        int num[10];
        for(int i = 0;i < 9;i++)
            cin >> num[i];
        int u = encode(num);
        g_step[u] = 0;
        f[u] = evaluate(num);
        sta[u] = 1;
        pq.insert(make_pair(f[u],u));
        int kyu;
        while(!pq.empty())
        {
            auto itr = pq.begin();
            int uf = itr->first;
            u = itr->second;
            if(u == 123456780)
                break;
            pq.erase(itr);
            sta[u] = 2;
            kyu = decode(u,num);
            for(int i = 0;i < 9;i++)
                if(exchange[kyu][i])
                {
                    mySwap(kyu,i,num);
                    int v = encode(num);
                    if(sta[v] != 2)
                    {
                        int old_f = f[v];
                        if(g_step.find(v) == g_step.end() || g_step[v] > g_step[u] + 1)
                        {
                            g_step[v] = g_step[u] + 1;
                            f[v] = g_step[v] + evaluate(num);
                        }
                        if(sta[v] == 1)
                        {
                            pq.erase(make_pair(old_f,v));
                            pq.insert(make_pair(f[v],v));
                        }
                        else
                        {
                            sta[v] = 1;
                            pq.insert(make_pair(f[v],v));
                        }
                    }
                    mySwap(kyu,i,num);
                }
        }
        if(g_step.find(123456780) == g_step.end())
            cout << "No solution!" << endl;
        else
            cout << g_step[123456780] << endl;
    }
}

exchange 数组是用来记录两个位置是不是相邻。value 数组是用来记录两个位置的曼哈顿距离。这里 9 个格子的位置依次是：0 1 2 3 4 5 6 7 8

f 用来保存每个状态的 f 值。g_step 保存的是状态的 g 值，也就是从初始状态到这个状态的步数。sta 用来记录每个状态是在 openlist 中 (sta 值 = 1)，closedlist 中 (sta 值 = 2) 或者还没遍历到 (sta 值 = 0)

pq 是 openlist，用平衡树 set 来模拟能修改的堆。每个元素 pair<int, int> 中第一个整数是 f 值，第二个整数是状态编码

Encode/decode 是编码 / 解码状态，这里用的是前面提到的第一种编码方法。也就是直接编码成一个 9 位数

Evaluate 是估价函数，计算一个状态的 h 值。我们实际算的是每块拼图到目标位置曼哈顿距离之和。显然这个 h 值满足 A * 算法的要求

第 84-120 行是 A 星搜索的代码。注意对下一个状态 v，如果 sta [v]==1 说明 v 在 openlist 中，于是考虑更新 openlist 中 v 对应的 f 值；如果 sta [v]==0 说明 v 不在 openlist 中，于是直接向 openlist 中插入 (f [v], v) 二元组

大家可以尝试修改 evaluate 函数。比如将第 56 行改成 return ret-1 /return ret-2 /return ret-3 … 0 试试。你会发现程序越来越慢，如果改成 return 0 就和 BFS 没有区别了。但是结果都是正确的

如果改成 return ret+1 /return ret+2 /return ret+3 你会发现程序越来越快，但是越来越多的数据输出的结果不是最优解