題解——八數碼
題目（粘貼自洛谷）
題目描述
在3×3的棋盤上，擺有八個棋子，每個棋子上標有1至8的某一數字，棋盤中留有一個空格，空格用0來表示，空格周圍的棋子可以移到空格中，要求解的問題是：給出一種初始布局（初始狀態）和目標布局（為了使題目簡單,設目標狀態為123804765），找到一種最少步驟的移動方法，實作從初始布局到目標布局的轉變，
輸入格式
輸入初始狀態，一行九個數字，空格用0表示
輸出格式
只有一行，該行只有一個數字，表示從初始狀態到目標狀態需要的最少移動次數(測驗資料中無特殊無法到達目標狀態資料)
輸入輸出樣例
輸入 283104765 輸出 4
思路
那么這個題主要的思維難度在于如何設計狀態，很多人都會想到用一個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就可以了，然后把它入隊，然后再搜索，然后再輸出，然后，，，就結束了，
結束
那么這篇題解到這里就結束了，如果覺得還可以，請點個推薦，如果對哪里有意見回批評、建議，請在評論區留言，謝謝大家的觀看！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53353.html
標籤：其他