題解——八數碼難題
題解——八數碼
題目（粘貼自洛谷）
題目描述
在3×3的棋盤上，擺有八個棋子，每個棋子上標有1至8的某一數字。棋盤中留有一個空格，空格用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀態）和目標布局（為了使題目簡單,設目標狀態為123804765），找到一種最少步驟的移動方法，實現從初始布局到目標布局的轉變。
輸入格式
輸入初始狀態，一行九個數字，空格用0表示
輸出格式
只有一行，該行只有一個數字，表示從初始狀態到目標狀態需要的最少移動次數(測試數據中無特殊無法到達目標狀態數據)
輸入輸出樣例
輸入 283104765 輸出 4
輸出 #1 複製
思路
那麼這個題主要的思維難度在於如何設計狀態，很多人都會想到用一個3*3的數組來模擬這個9宮格，但是實際上是不可行的，因為我們沒有辦法去表示這個狀態下與初始狀態的移動步數（也許可以用哈希表，但博主不會）那麼如何來設計我們的狀態呢？其實題目給了我們提示：用一個9位數來表示這個並狀態，與數組上上的位置一一對應。舉個例子：
123740865
1 2 3
7 4 0
8 6 5
用9位數的話，可以很好的表示到了這個狀態後與初始狀態的移動步數是多少，因為9位數比較大，開數組浪費空間，我們可以選擇用map,但是有人要問了：如果用9位數的話，我們如何去交換兩個數的位置呢？其實如果是一個數組的話就比較容易轉換的。相信讀者也注意到了，這裡的數組與我們9位數的狀態之間是可以互相轉化的，我們只需要稍微處理一下，編個函數也罷。
所以這個題的總體思路就是：用9位數作為狀態傳遞，用數組去模擬交換！
A*
因為這個題用到了A*算法，所以這裡就簡單的講講A/*是什麼.
簡單地說，我們平常的\索算法多是沒有目的的搜索，但是呢A/*卻是有目的的搜索，好比一個人在操場上，要去國旗旗杆，平常的搜索更像是一個瞎子，最壞的話要把操場每一個位置都找遍才能到達旗杆的位置，但是A*更像是一個正常人，一眼看見旗杆的位置，並朝那個方向走過去，很明顯A*算法要比BFS或DFS便捷的多，事實也是如此：A*比平常的搜索算法快得多！，這個題也不例外。
那麼如何使用A*呢
我們對每個點定義一個估價函數f(x)=g(x)+h(x)，g(x)表示從起始點到x的實際代價,h(x)表示估計的從x到結束點的代價，並要求h(x)小於等於從x到結束點的實際代價,那麼每次我們從可行點集合中找到f(x)最小的x，然後搜索他,這個過程可以用優先隊列（即堆）實現,這樣的話可以更快地到達結束點，並保證到達結束點時走的是最優路徑,一般來說，h函數的選擇決定了A*算法的效率，h函數與實際值的差距越小越好
如果不知道優先隊列是什麼，可以去我的博客中的關於STL的講解中看看（包括上文的map）。
對於這個題map的選擇有兩種：1.不在應該在的位置上的數的個數；2.所用數距離其應在位置的曼哈頓距離和。
博主選擇第一種（比較好實現）
那麼，讓我們來看看代碼吧！
代碼
我們分開來看
定義部分
庫
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>//
#include<queue>//
#include<map>//
#include<sstream>
#define N 100001
#define ll long long
using namespace std;
這裡不用細說，但注意一下,帶”//”的，都與STL有關，有興趣的讀者可以自行瀏覽我的講STL的博客（稍微打下廣告）
這裡有一個define，主要功能是替換。也就是下面的long long 下面都可以打成ll了
map+ans
ll ans;
map<ll,int> f;//f=g+h
map<ll,bool> vis;
這裡呢有一個ans，用來儲存答案，兩個map，f是A*中的f函數，（f=g+h），vis用來判重，
優先隊列
struct rode{
int fh;
ll zt;
ll g;
rode() { };
rode(int fh,ll zt,ll g) : fh(fh),zt(zt),g(g) { };
};
struct cmp{
bool operator () (rode a,rode b)
{
return a.fh>b.fh;
}
};
priority_queue<rode,vector<rode>,cmp> q;
這裡有一個rode結構體，fh是這個狀態下的f值（A*），zt是這個狀態，g是原始狀態到這個狀態移動所用的步數。在這個結構體中有有兩個函數，叫做構造函數是在定義中使用的，在這個題中的意義就是在我們往下面這個優先隊列里輸進數據時能扣簡便些。如果你不清楚哪裡簡便，一會看見dfs部分，你就知道了。
A*並不是獨立存在的，這個算法會依附於其他的搜索算法，並加快其速度。
至於結構體cmp和重載運算符operator，博主講STL博客中略有介紹，但如果有讀者對重載運算符operator感興趣，可以自行上網查閱，博主只是背了下來。在這裡，結構體cmp的作用是讓這個優先隊列q其中元素的排列順序是fh越小的越靠前，是的你沒看錯，是小。這可以被認為是一個小根堆。
至於最後一行是優先隊列的定義形式，這裡不在詳講。
其它
ll qishi,mubiao=123804765;
int a[4][4];
const int fx[]={0,1,-1,0,0};
const int fy[]={0,0,0,1,-1};
這裡理解起來就比較簡便了，qishi就是原始狀態，即「起始」，mubiao即「目標」，是目標狀態。下面那個數組是用來模擬9宮格的。下面的程序將實現這二者之間的轉化。
而下面這兩個數組，相信打過搜索的讀者都比較熟悉，這裡不多解釋。
次要函數部分
就是相對容易一些的函數
轉化1
inline ll zhuanhua1(ll zhuang,ll& x_0,ll& y_0)
{
for(int i=3;i>=1;i--)
{
for(int j=3;j>=1;j--)
{
a[i][j]=zhuang%10;
zhuang/=10;
if(a[i][j]==0)
{
x_0=i;
y_0=j;
}
}
}
}//over
這裡的inline先不用去管他，我聽別人說這個能減少時間，
但博主也不知道是什麼幹什麼用的
這個函數實現了9位數狀態到數組的轉化過程。
常數中zhuang就是我們設計的狀態，至於常數x_0，y_0，你也許已經知道這是什麼意思，他們是0的位置的「橫縱坐標」。
這裡的「&」是用來返回數值的，一般來說，在運用這個函數時的變量與這個函數的變量之間沒有關係，但這個符號實現了把數值返回。例如在我的主函數中：
zhuanhua1(zhuang,dx,dy);
在運行完畢後，dx，dy的值將會是0的位置的橫縱坐標。
這裡關於這個符號，有興趣的朋友可以自行上網瀏覽。
至於函數內部嗎，很好理解。相信各位讀者也能看懂。如果仍有不懂的問題，請各位讀者自行探索。
轉化2
ll zhuanhua2()
{
ll resu=0;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
resu+=a[i][j];
resu*=10;
}
}
resu/=10;
return resu;
}//over
這個函數實現了由數組到9位數狀態的轉化過程
其實與轉化1是相反的。
這裡請千萬不要忘了最後除以10，因為循環結束後resu是一個10位數。
h函數
int h(ll qi,ll mu)
{
int an=0;
ll q=qi,m=mu;
while(q>0)
{
int i=q%10,j=m%10;
if(i!=j) an++;
q/=10;m/=10;
}
return an;
}//over
這就是A*算法中的重中之重，h函數，h函數的選擇將直接決定到這個程序運行結果的方方面面。
剛剛在思路里講了，博主選的h函數是不在應在位置上的數的個數，這裡qi常數是目前狀態，mu是目標狀態，然後比較他們的每一位，如果不同的話an++，這便是這個函數，沒有我們想像中的那麼複雜。最後返回an。
主要函數部分
dfs+A*
ll dfs(ll zhuang)
{
if(zhuang==mubiao)
{
//return g;
return q.top().g;
}
ll dx,dy;
zhuanhua1(zhuang,dx,dy);
int gb=q.top().g;
q.pop();
for(int i=1;i<=4;i++)
{
int x,y;
x=dx+fx[i];
y=dy+fy[i];
if(x<1||y<1||x>3||y>3) continue;
swap(a[x][y],a[dx][dy]);
ll newz;
newz=zhuanhua2();
f[newz]=h(newz,mubiao)+gb+1;
if(!vis[newz]) q.push(rode(f[newz],newz,gb+1));
swap(a[dx][dy],a[x][y]);
}
int next=q.top().zt;
vis[next]=1;
return dfs(next);
vis[next]=0;
}
這裡的常數是zhuang，也就是目前搜索到的狀態。
這裡如果目前狀態已經是目標狀態，那麼優先隊列隊頭元素的g就是正解。
至於原因嘛，可以這麼理解，當目前狀態和目標狀態一樣時，h應該是0，而這時f=g+h=g，因為優先隊列是f越小的越往前，所以這裡的f自然是最小。其餘的f都大，f=g+h，而h還實際上小於實際值，加了個比實際值小的還大，更別提加的是實際值了。這裡也說明了為什麼h函數要小於實際值。
然後定義了dx，dy。調用函數zhuanhua1，這是數組a中已經至目前狀態所對應的那個「9宮格」，這時gb存儲一下隊首函數的g值（因為下面要用），並彈出隊首元素。
下面有一個循環，枚舉是哪個位置上的數與0這個位置交換，x，y，即這個位置的橫縱坐標，下面緊接着判斷是否越界，如果沒有的話交換這兩個位置的值，並調用zhuanhua2，把這個數組對應的9位數狀態輸入到newz（即new zhuangtai，博主比較喜歡用這種方式定義變量）去，接着如果這個點沒有被搜索過，就把newz的的f值算出來，就等於h函數加gb+1（因為這裡再次移動，步數又加1）。再把這個newz的f值，它本身，和它的g值，扔進隊列。
這裡構造函數的便利就顯現了出來，你不用再去構建一個結構體，而可以直接實現入隊操作。
循環最後，把兩個值交換回來，不影響另外的決策。
循環結束後，取出f值最小的那個狀態，並把它的vis標記上，然後搜索他，最後回溯。
主函數
int main()
{
cin>>qishi;
f[qishi]=h(qishi,mubiao);
q.push(rode(f[qishi],qishi,0));
ans=dfs(qishi);
cout<<ans;
return 0;
}
這就比較好懂了，輸入qishi值，因為qishi的g值為0，多以這裡不用去管，光看h就可以了，然後把它入隊，然後再搜索，然後再輸出，然後。。。就結束了。
結束
那麼這篇題解到這裡就結束了，如果覺得還可以，請點個推薦，如果對哪裡有意見回批評、建議，請在評論區留言。謝謝大家的觀看！
