#1312 : 搜尋三·啟發式搜尋
10000ms
1000ms
256MB
描述
在小Ho的手機上有一款叫做八數位的遊戲，小Ho在坐車或者等人的時候經常使用這個遊戲來打發時間。
遊戲的棋盤被分割成3x3的區域，上面放着标記有1~8八個數字的方形棋子，剩下一個區域為空。
遊戲過程中，小Ho隻能移動棋子到相鄰的空區域上。當小Ho将8個棋子都移動到如下圖所示的位置時，遊戲就結束了。
小Hi：小Ho，你覺得如果用計算機來玩這個遊戲應該怎麼做？
小Ho：用計算機來玩麼？我覺得應該是搜尋吧，讓我想一想。
提示：啟發式搜尋
輸入
第1行：1個正整數t，表示資料組數。1≤t≤8。
接下來有t組資料，每組資料有3行，每行3個整數，包含0~8，每個數字隻出現一次，其中0表示空位。
輸出
第1..t行：每行1個整數，表示該組資料解的步數。若無解輸出"No Solution!"
樣例輸入
3
1 2 3
4 5 6
7 8 0
1 2 3
4 5 6
8 7 0
8 0 1
5 7 4
3 6 2
樣例輸出
No Solution!
25
提示：啟發式搜尋
小Ho：這個問題和上一次一樣嘛，用寬度優先搜尋來求解。
然後把這個3x3的二維數組拉伸成一個長度為9的數組，将長度為9的數組作為狀态。
那麼最終狀态就是{1,2,3,4,5,6,7,8,0}。
由于每一個位置的有9種可能，是以我建立一個9維數組來判重進行搜尋就好了。
小Hi：9維數組，每一維的大小為9。小Ho，你确定這不會超過記憶體限制麼？
小Ho：9的9次方等于387420489，好像是挺大的。不過應該沒問題吧。
小Hi：怎麼可能沒問題！這個資料已經很大了好麼！
小Ho：那該怎麼辦啊？
小Hi：小Ho，你仔細觀察題目的狀态。由于每個數字一定隻會出現一次，每個狀态對應的恰好是1~9的一個排列。
那麼1~9的全排列有多少種呢？
小Ho：這個我知道，是9!，一共362880種。
小Hi：沒錯，總共隻有不到40萬種不同的情況。如果我們能夠使用一個方法來表示不同排列的狀态，那麼是不是就可以把判重的狀态數量壓縮到40萬以内了呢？
小Ho：恩，沒錯。但是有什麼好的方法麼？
小Hi：當然有啦，這裡我們需要用的事全排列的知識。小Ho你知道全排列是有順序的麼？
小Ho：恩，知道。比如3個數的全排列，按順序就是：
123, 132, 213, 231, 312, 321
小Hi：沒錯，那麼第二個問題：假如我給你一個全排列，你能計算出它是第幾個排列麼？
小Ho：(⊙v⊙)，這個我不知道。
小Hi：我就知道你不知道，讓我來告訴你吧。這裡我們需要用到一個叫做康托展開的方法。
對于一個長度為n的排列num[1..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：
num[] = {2, 1, 3}
a[] = {1, 0, 0}
X = 1 * 2! + 0 * 1! + 0 * 1! = 2
我們如果将3的全排列從0開始編号，2号對應的正是213。
其寫做僞代碼為：
Cantor(num[])
X = 0
For i = 1 .. n
tp = 0
For j = i + 1 .. n
If (num[j] < num[i]) Then
tp = tp + 1
End If
End For
X = X + tp * (n - i)!
End For
Return X
那麼接下來，第三個問題！
小Ho：你說吧！
小Hi：已知X，如何去反向求解出全排列？
小Ho：我覺得應該還是從康托展開的公式入手。
< 小Ho拿出草稿紙，在上面推算了一會兒 >
根據X的求值公式，可以推斷出對于a[i]來說，其值一定小于等于n-i。那麼有：
a[i]≤n-i, a[i]*(n-i)!≤(n-i)*(n-i)!<(n-i+1)!
也就是說，對于a[i]來說，無論a[i+1..n]的值為多少，其後面的和都不會超過(n-i)!
那麼也就是說，如果我用X除以(n-1)!，得到商c和餘數r。其中c就等于a[1]，r則等于後面的部分。
這樣依次求解，就可以得到a[]數組了！
比如求解3的全排列中，編号為3的排列：
3 / 2! = 1 ... 1 => a[1] = 1
1 / 1! = 1 ... 0 => a[2] = 1
0 / 0! = 0 ... 0 => a[3] = 0
然後就是根據a[]來求解num[]，讓我想一想。
...
我知道了！由于a[i]表示的是num[i+1..n]中比num[i]還小的數字。
那麼隻需要從num[1]開始，依次從尚未使用的數字中選取第a[i]+1小的數字填入就可以了！
緊接着上面的例子：
a[] = {1, 1, 0}
unused = {1, 2, 3}, a[1] = 1, num[1] = 2
unused = {1, 3}, a[2] = 1, num[2] = 3
unused = {1}, a[3] = 0, num[3] = 1
=> 2, 3, 1
231也确實是3的全排列中編号為3的排列。
小Hi：小Ho，你真棒！你使用的這個方法也被稱為逆康托展開，寫作代碼的話：
unCantor(X):
a = []
num = []
used = [] // 長度為n的boolean數組，初始為false
For i = 1 .. n
a[i] = X / (n - i)!
X = X mod (n - i)!
cnt = 0
For j = 1 .. n
If (used[j]) Then
cnt = cnt + 1
If (cnt == a[i] + 1) Then
num[i] = j
used[j] = true
Break
End If
End If
End For
End For
Return num
通過康托展開以及康托逆展開，我們就将該問題的狀态空間壓縮到了9!，在空間複雜度上得到了優化。
小Ho：那麼這次的問題不就解決了！
小Hi：遠遠沒那麼簡單哦，其實這個問題還有一個時間上的優化。
小Ho：但是寬度優先搜尋不就是最快尋找到解的方法了麼？還有更好的方法麼？
小Hi：當然有了，我們有一種叫做啟發式搜尋的方法。
在啟發式搜尋的過程中，不再是一定按照步數最優的順序來搜尋。
首先在啟發式搜尋中，我們每次找到目前“最有希望是最短路徑”的狀态進行擴充。對于每個狀态的我們用函數F來估計它是否有希望。F包含兩個部分：
F = G + H
G：就是普通寬度優先搜尋中的從起始狀态到目前狀态的代價，比如在這次的問題中，G就等于從起始狀态到目前狀态的最少步數。
H：是一個估計的值，表示從目前狀态到目标狀态估計的代價（步數）。
H是由我們自己設計的，H函數設計的好壞決定了A*算法的效率。H值越大，算法運作越快。
但是在設計評估函數時，需要注意一個很重要的性質：評估函數的值一定要小于等于實際目前狀态到目标狀态的代價（步數）。
否則雖然你的程式運作速度加快，但是可能在搜尋過程中漏掉了最優解。相對的，隻要評估函數的值小于等于實際目前狀态到目标狀态的代價，就一定能找到最優解
在這個問題中可以表述為：評估函數得到的從目前狀态到目标的狀态需要行動的步數一定不能超過實際上需要行動的步數。
是以，我們可以将評估函數設定為：1-8八數字目前位置到目标位置的曼哈頓距離之和。（為什麼這樣設計留給讀者思考。當然也有其他符合條件的估計函數，不同估計函數效率如何也留給讀者自行比較。）
F：評估值和狀态值的總和。
同時在啟發式搜尋中将原來的一個隊列變成了兩個隊列：openlist和closelist。
在openlist中的狀态，其F值還可能發生變化。而在closelist中的狀态，其F值一定不會再發生改變。
整個搜尋解的流程變為：
- 計算初始狀态的F值，并将其加入openlist
- 從openlist中取出F值最小的狀态u，并将u加入closelist。若u為目标狀态，結束搜尋；
- 對u進行擴充，假設其擴充的狀态為v：若v未出現過，計算v的f值并加入openlist；若v在openlist中，更新v的F值，取較小的一個；若v在closelist中，抛棄該狀态。
- 若openlist為空，結束搜尋。否則回到2。
利用這個方法可以避免搜尋一些明顯會遠離目标狀态的狀态，進而縮小搜尋空間，早一步搜尋到目标結果。
在啟發式搜尋中，最重要的是評估函數的選取，一個好的評估函數能夠更快的趨近于目标狀态。
将上述過程寫做僞代碼為：
search(status):
start.status = status
start.g = 0 // 實際步數
start.h = evaluate(start.status)
start.f = start.g + start.h
openlist.insert(start)
While (!openlist.isEmpty())
u = openlist.getMinFStatus()
closelist.insert(u)
For v is u.neighborStatus
If (v in openlist) Then
// 更新v的f值
If (v.f > v.h + u.g + 1) Then
v.f = v.h + u.g + 1
End If
Else If (v in closelist)
continue
Else
v.g = u.g + 1
v.h = evaluate(v.status)
v.f = v.g + v.h
openlist.insert(v)
End If
End For
End While
其中openlist.getMinFStatus()可以使用堆來實作。
啟發式搜尋在某些情況下并不一定好用，一方面取決于評估函數的選取，另一個方面由于在選取狀态時也會有額外的開銷。而快速趨近目标結果所減少的時間，能否彌補這一部分開銷也是非常關鍵的。
是以根據題目選取合适的搜尋方法才是最重要的。
代碼：
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
int shu[3][3],x,y,step;
bool friend operator < (node xx,node yy)
{
return xx.step>yy.step;
}
}now,qian;
int ans,a[3][3];
int p[9];
int nn[9];
bool fafe[400000];
bool pan(node xx)
{
int lp=1;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
if (xx.shu[i][j]!=lp++)
return false;
return true;
}
void ss()
{
nn[0]=1;
for (int i=1;i<9;i++)
nn[i]=nn[i-1]*i;
return ;
}
int biao(int shu[3][3])
{
int lp=0;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
p[lp++]=shu[i][j];
int s[8]={0};
for (int i=0;i<8;i++)
for (int j=i+1;j<9;j++)
if (p[i]>p[j])
s[i]++;
int ans=0;
for (int i=0;i<8;i++)
ans+=s[i]*nn[8-i];
if (fafe[ans])
return false;
fafe[ans]=true;
return true;
}
void dfs(int x,int y)
{
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
now.shu[i][j]=a[i][j];
now.step=0;
now.x=x;now.y=y;
memset(fafe,false,sizeof(fafe));
biao(now.shu);
priority_queue<node > que;
que.push(now);
while (!que.empty())
{
qian=que.top();
que.pop();
x=qian.x;y=qian.y;
if (pan(qian))
{
ans=qian.step;
return ;
}
if (x+1<3)
{
now=qian;
now.shu[x][y]=now.shu[x+1][y];
now.shu[x+1][y]=9;
now.x=x+1;now.y=y;
if (biao(now.shu))
{
now.step=qian.step+1;
que.push(now);
}
}
if (x-1>=0)
{
now=qian;
now.shu[x][y]=now.shu[x-1][y];
now.shu[x-1][y]=9;
now.x=x-1;now.y=y;
if (biao(now.shu))
{
now.step=qian.step+1;
que.push(now);
}
}
if (y+1<3)
{
now=qian;
now.shu[x][y]=now.shu[x][y+1];
now.shu[x][y+1]=9;
now.x=x;now.y=y+1;
if (biao(now.shu))
{
now.step=qian.step+1;
que.push(now);
}
}
if (y-1>=0)
{
now=qian;
now.shu[x][y]=now.shu[x][y-1];
now.shu[x][y-1]=9;
now.x=x;now.y=y-1;
if (biao(now.shu))
{
now.step=qian.step+1;
que.push(now);
}
}
}
}
void slove()
{
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
scanf("%d",&a[i][j]);
ans=-1;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
if (a[i][j]==0)
{
a[i][j]=9;
dfs(i,j);
}
}
if (ans==-1)
printf("No Solution!\n");
else
printf("%d\n",ans);
}
int main()
{
ss();
int t;scanf("%d",&t);
while (t--)
slove();
return 0;
}