1.采用曼哈顿距离之和作为启发式时可以保证每一个结点出队时都已经找到了它的最优路径

可以直接将代码中加上一个unordered_map记录某个点是否被出队过，如果有则在扩展这个点时直接continue，也能ac。
这是因为曼哈顿距离之和作为评估函数(Manhattan heuristic)满足一致性，见后文。
（不过这样做并不能加快代码运行速度，只是为了证明结论）

2.关于启发式（评估函数）

启发式的一些性质

首先A*算法中用f(n) = g(n) + h(n) 其中g是到达n结点的路径代价（即起点到n的距离）
评估函数h一定要满足可采纳性：h(n) < d(n),d(n)指从n到终点的实际代价。
评估函数满足可采纳性可以保证终点第一次出队时一定是最优解，这点y总的视频里已经讲过了。

还有一个略强于可采纳性的性质：一致性（单调性），只作用于图搜索中使用A*算法。
一致性的定义是：对于任一结点n有：n通过任一路径a到达n’，h(n) <= h(n’) + c(n,a,n’)(n通过a到达n’的路径长度)
由一致性我们很容易可以得到：

在任何路径上f的值都是非递减的：

上述式子左右各加上g(n)有
g(n)+h(n)=f(n)
g(n)+c(n,a,n’)+h(n’) = g(n’)+h(n’) = f(n’)
从而有f(n) <= f(n’)

若结点n被出队，则此时已经找到了到达n的最优路径

采用反证法：若n被出队时还没有找到n的最优路径，那么n的最优路径上的某一点n’一定在优先队列中，
由f在任何路径上的非递减性，f(n’) <= f’(n)(指n经过最优路径的f值) < f(n)(指n经过当前路径的f)，
因为对于n点f(n) = g(n) + h(n) n经过任一路径到达n都不会改变h(n),因此经过最优路径的f值一定小于其他的。
那么此时n’的f一定会先被出队，矛盾。

要证明Manhattan heuristic的一致性也很简单：
每一步最多减少1的曼哈顿距离，而每一步的路径长度都是1，因此一定满足上述不等式。

更多启发式

设计启发式的思想

在八数码问题中可以用构造松弛问题的方式来得到评估函数。
首先，原问题中对于状态改变的限制如下：数字可以从方格A移动到方格B，当且仅当
1) A与B水平或竖直相邻
2) B是空的

我们可以减少操作的限制，生成两个子问题：
1）数字可以从方格A移动到方格B，当且仅当A与B水平或竖直相邻
2）数字可以从方格A移动到方格B，当且仅当B是空的

由1)我们可以得到评估函数：Manhattan heuristic，即曼哈顿距离之和
由2)我们可以得到评估函数：Gaschnig heuristic，本函数可以以模拟的方式求出

Gaschnig启发式

虽然本启发式看起来比较笨，但是它并不总是比Manhattan heuristic差.
（一般来说我们认为评估函数在满足可采纳性的条件下越大越好）
可以看下面的例子：

起始状态：
1 2 3
8 x 4
7 6 5

目标状态：
1 2 3
7 x 4
8 6 5

Manhattan heuristic：2
Gaschnig heuristc： 3

linear conflict

linear conflict是Manhattan heuristic的加强版（但是不再满足一致性）
定义：当ai,aj两个数字处于他们的目标行（列上类似）时，若ai，aj的左右关系与它们目标的左右关系矛盾时，ai与aj有了一个线性冲突。
在Manhattan heuristic中，它们的曼哈顿距离之和为2（为了方便默认它们相邻，不相邻也是相比曼哈顿距离+2），但是显然实际上它们无法穿过彼此，因此其中一个必须要离开这一行然后在另一个数字越过它之后再回来，实际需要至少4步操作
如果一行有多个linear conflict时可以采用以下方法：先取出与其他数字冲突最多的，评估函数+2，其他与它有冲突的冲突数量-1，然后重复上述操作直到这一行没有linear conflict。

下面给出两种启发式的计算方法

Gaschnig启发式

当x位于目标位置时，将任一未处于目标位置上的数填入x，若不存在这样的数则结束

当x处于某数的目标位置上时，将这个数填入x。

int f(string state)
{
    int res = 0,p;
    p = state.find('x');
    while (1)
    {
        if (p != 8)
        {
            res++;
            for (int i = 0; i < 9; i++)
                if (state[i] == '1' + p)
                {
                    swap(state[i], state[p]);
                    p = i;
                    break;
                }
        }
        else
        {
            bool st = false;
            for (int i = 0; i < 8; i++)
            {
                if (state[i] == '1' + i) continue;
                st = true;
                swap(state[p], state[i]);
                p = i;
                res++;
            }
            if(!st) break;
        }
    }
    return res;
}

linear conflict

可以尝试打印搜索过程中扩展的节点数，linear conflict扩展的节点数明显最少，但是因为计算评估函数本身比较复杂，运行时间上没有明显的优势，这里它比Manhattan heuristc更好是数学意义上的

int f(string state)
{
    int res = 0;
    for (int i = 0; i < state.size(); i++)
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }

    for (int i = 0; i < 3; i++)//计算linear conflict
    {
        int tmp = 0;
        for (int j = 0; j < 3; j++)
        {
            if (state[i * 3 + j] == 'x') continue;
            if (!check_r(i * 3 + j, state[i * 3 + j] - '1')) continue;
            for (int k = j + 1;k < 3; k++)
            {
                if (state[i * 3 + j] == 'x') continue;
                if (!check_r(i * 3 + k, state[i * 3 + k] - '1')) continue;
                if (state[i * 3 + j] > state[i * 3 + k]) tmp++;
            }
        }
        if (tmp == 3) res += 2;
        else if (tmp) res++;
    }

    for (int i = 0; i < 3; i++)//计算linear conflict
    {
        int tmp = 0;
        for (int j = 0; j < 3; j++)
        {
            if (!check_c(i + j * 3, state[i + j * 3] - '1')) continue;
            for (int k = j + 1;k < 3; k++)
            {
                if (!check_c(i + k * 3, state[i + k * 3] - '1')) continue;
                if (state[i + j * 3] > state[i + k * 3]) tmp++;
            }
        }
        if (tmp == 3) res += 2;
        else if (tmp) res++;
    }
    return res;
}

参考文献

《人工智能：一种现代方法》