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
- g就是普通宽度优先搜索中的从起始状态到当前状态的代价，比如在八数码的问题中，g就等于从初始状态到当前状态的最少步数
- 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
最后整个算法的流程为：
- 计算初始状态的f值，并将其加入openlist
- 从openlist中取出f值最小的状态u，并将u加入closelist。若u为目标状态，结束搜索；
- 对u进行扩展，假设其扩展的状态为v：若v未出现过，计算v的f值并加入openlist；若v在openlist中，更新v的F值，取较小的一个；若v在closelist中，抛弃该状态
- 若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你会发现程序越来越快，但是越来越多的数据输出的结果不是最优解
nbnb大佬大佬