八數碼（雙向BFS和A * 和康托展開）
https://www.luogu.com.cn/problem/P1379（傳送門）
一道題用三種方法來寫
題目大意
在3×3的棋盤上，擺有八個棋子，每個棋子上標有1至8的某一數字，棋盤中留有一個空格，空格用0來表示，空格周圍的棋子可以移到空格中，要求解的問題是：給出一種初始布局（初始狀態）和目標布局（為了使題目簡單,設目標狀態為123804765），找到一種最少步驟的移動方法，實作從初始布局到目標布局的轉變，
輸入格式
輸入初始狀態，一行九個數字，空格用0表示
輸出格式
只有一行，該行只有一個數字，表示從初始狀態到目標狀態需要的最少移動次數(測驗資料中無特殊無法到達目標狀態資料)
輸入 #1復制
283104765
輸出 #1復制
4
樣例可變成這樣
一、康托展開
康托展開
函式cantor()實作的功能是 ： 輸入一個排列，計算出它的cantor值 即在全排列中是第幾個，
例如 12345 cantor值是 1； 12354 cantor值是 2；12435cantor值是 3；
那么如何實作呢？很簡單
比如說求2143是{1.2.3.4}的全排列第幾大的數
1、比首位2小的只有1這一個數，后面3個數的排列有3!種，所以ans+=1 × \times × 3!;
2、首位為2，比第二位1小的數的個數為0，后面兩個數的排列有2!種，所以ans+=0 × \times × 2!;
3、前面為21，比第三位4小的只有3一個(因為前面21已經用了)，后面的一個數的排列有1!種，所以ans+=1 × \times × 1!;
4、前三位為214，emmm，不用看也是0了(因為總共只有四位)
總的來說就是
從第一位依次往后遍歷，看在未出現的元素中比當前位小的有多少個，然后乘上后面的位數個數的階乘，累積起來即可，
代碼
int cantor(string x){
int len=x.length();
int ans=0;
for(int i=0;i<len;i++){
int t=0;//記錄在當前位之后比當前位小的數的個數
for(int j=i+1;j<len;j++){
if(x[j]<x[i])
t++;
}
ans+=t*(len-i-1)!;//階乘得自己寫函式
}
return ans;
}
逆康拓展開
顧名思義就是康托展開的逆程序，在一個集合的全排列中，給你一個數k，求出第k大的排列，即為逆康托展開
代碼(限于篇幅，會在代碼中注明原理)
void decantor(int k,int n)//n是排列的長度
{
vector<int>p;//存放當前可用的數
vector<int>q;//存放所求排列，用vector主要是覺得比較方便
for(int i=1;i<=n;i++)
p.push_back(i)//將全部能用的數存盤進去
for(int i=n;i>=1;i++){
int a=k%(i-1)!;//即減去第一位的個數后剩余的個數
int b=k/(i-1)!;//第一位是由后面的個數的階乘來乘沒出現的元素里比它小的個數，除以階乘，既可以求出在它后面比它小的有多少個了
k=a;
sort(p.begin(),p.end());
q.push_back(p[b])//因為p是從零開始，所以不需要加一
p.erase(p.begin()+b);//刪去使用過的數
}
}
言歸正傳，接下來用康托展開去重（也可以用map），外加bfs做這道題
代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int st[9];
int goal[]={1,2,3,8,0,4,7,6,5};
int fuc[]={1,1,2,6,24,120,720,5040,40320,362880};
int mp[1000000];
struct node{
int sum[9];
ll step;
};
bool cantor(int a[]){
ll ans=0;
for(int i=0;i<9;i++){
int z=0;
for(int j=i+1;j<9;j++)
if(a[j]<a[i])
z++;
ans+=fuc[8-i]*z;
}
if(!mp[ans]){
mp[ans]=1;
return 1;
}
else
return 0;
}
queue<node>p;
ll bfs(){
node t;
memcpy(t.sum,st,sizeof(t.sum));
t.step=0;
cantor(st);
if(memcmp(t.sum,goal,sizeof(goal))==0)//特判起點即為終點時
return t.step;
p.push(t);
while(!p.empty()){
t=p.front();
p.pop();
int base;
for(base=0;base<9;base++){
if(t.sum[base]==0)
break;
}//將一維轉化為二維
int x=base%3;//橫坐標
int y=base/3;//縱坐標
for(int i=0;i<4;i++){
int nx=x+dx[i];//元素0轉移后的新坐標
int ny=y+dy[i];
if(nx<0||nx>2||ny<0||ny>2)
continue;
node h;
memcpy(&h,&t,sizeof(struct node));//將t復制給h；
swap(h.sum[y*3+x],h.sum[ny*3+nx]);//這樣改變的是h里的值，t的值并未改變， 至于y*3+x是將二維轉化為一維
h.step++;
if(memcmp(h.sum,goal,sizeof(goal))==0)
return h.step;
if(cantor(h.sum))//只有之前沒出現的才壓入佇列
p.push(h);
}
}
return -1;
}
int main(){
ll x,k=8;
cin>>x;
while(x){
st[k--]=x%10;
x/=10;
}
ll anss=bfs();
cout<<anss<<endl;
return 0;
}
二、雙向bfs
同時從起點和終點向對方做bfs,將在中間的某個位置相遇，此時即得到了最優路徑，雙向廣搜的應用場合是知道起點，終點，并且正向和逆向都能進行搜索，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int st[9];
int goal[]={1,2,3,8,0,4,7,6,5};
int fuc[]={1,1,2,6,24,120,720,5040,40320,362880};
int mp[10000000];
int mq[10000000];
struct node{
int s[9];
int step;
};
queue<node>p;
queue<node>q;
ll cantor(int a[]){
ll ans=0;
for(int i=0;i<9;i++){
int z=0;
for(int j=i+1;j<9;j++)
if(a[j]<a[i])
z++;
ans+=fuc[8-i]*z;
}
return ans;
}
ll bfs(){
node t;
node t2;
memcpy(t.s,st,sizeof(t.s));
t.step=0;
if(memcmp(t.s,goal,sizeof(goal))==0)//特判，起點即為終點時
return t.step;
memcpy(t2.s,goal,sizeof(t2.s));
t2.step=0;
p.push(t);
q.push(t2);
while(!p.empty()||!q.empty()){
int z,z2;
if(p.size()<q.size()){
t=p.front();
p.pop();
for(int i=0;i<9;i++){
if(t.s[i]==0)
z=i;
}
int x=z%3;
int y=z/3;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0||nx>2||ny<0||ny>2)
continue;
node h;
memcpy(&h,&t,sizeof(struct node));
swap(h.s[y*3+x],h.s[ny*3+nx]);
++h.step;
ll sum=cantor(h.s);
if(!mp[sum]){
p.push(h);
mp[sum]=h.step;
}
if(mp[sum]&&mq[sum]){
return mp[sum]+mq[sum];
}
}
}
else{
t2=q.front();
q.pop();
for(int i=0;i<9;i++){
if(t2.s[i]==0)
z2=i;
}
int x2=z2%3;
int y2=z2/3;
for(int i=0;i<4;i++){
int nx=x2+dx[i];
int ny=y2+dy[i];
if(nx<0||nx>2||ny<0||ny>2)
continue;
node h;
memcpy(&h,&t2,sizeof(struct node));
swap(h.s[y2*3+x2],h.s[ny*3+nx]);
h.step++;
ll sum=cantor(h.s);
if(!mq[sum]){
q.push(h);
mq[sum]=h.step;
}
if(mp[sum]&&mq[sum]){
return mp[sum]+mq[sum];
}
}
}
}
}
int main(){
int x,k=8;
cin>>x;
while(x){
st[k--]=x%10;
x/=10;
}
ll anss=bfs();
cout<<anss<<endl;
return 0;
}
三、A*演算法
在搜索程序中，用一個評估函式對當前情況進行評估，得到最好的狀態，從這個狀態繼續搜索，直到目標，設x是當前所在狀態，f(x)是對x的評估函式，有 f(x)=g(x)+h(x)
g(x):表示從初始狀態到現在狀態(x)的代價；
h(x):表示從現在狀態(x)到終點的最優路徑的評估，(abs(a.x-x2)+abs(a.y-y2))*10;(曼哈頓距離，x2,y2表示終點坐標，a表示當前點)
A*演算法的具體步驟：
1.把起點加入openlist(開啟串列，一般是一個優先佇列)
2.遍歷openlist ，找到F值最小的節點，把它作為當前處理的節點，并把該節點加入closelist(關閉串列，可以開個陣串列示）中
3.對該節點的8個相鄰格子進行判斷，如果格子是不可抵達的或者在closelist中，則忽略它，否則如下操作：
a. 如果相鄰格子不在openlist中，把它加入，并將parent設定為該節點和計算f,g,h值
b.如果相鄰格子已在openlist中，并且新的G值比舊的G值小，則把相鄰格子的parent設定為該節點，并且重新計算f值，
重復2,3步，直到終點加入了openlist中，表示找到路徑；或者openlist空了，表示沒有路徑，
最后從目標格開始，沿著每一格的父節點移動直到回到起始格，這就是路徑，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int goal[]={1,2,3,8,0,4,7,6,5};
int fuc[]={1,1,2,6,24,120,720,5040,40320,362880};
int st[9];
int vis[1000000];//關閉串列
int po[1000000];
struct node{
int step;
int f;
int s[9];
bool operator < (const node &x) const { //在優先佇列里按f的大小排序
return f > x.f;
}
};
struct hh{
int x;
int y;
}mp[10000];
priority_queue<node>q;//開啟串列
ll cantor(int a[]){
ll ans=0;
for(int i=0;i<9;i++){
int k=0;
for(int j=i+1;j<9;j++){
if(a[i]>a[j])
k++;
}
ans+=k*fuc[8-i];
}
return ans;
}
//啟發函式h為所有數字離正確位置的曼哈頓距離.
ll h(int cur[]){
int res = 0;
for (int i = 0; i < 9; i ++ ){
if (goal[i] != cur[i] && goal[i] != 0) res++;
}
return res;
}
ll axing(){
node t;
t.step=0;
memcpy(t.s,st,sizeof(st));
t.f=h(t.s);
q.push(t);
vis[cantor(t.s)]=1;
while(!q.empty()){
t=q.top();
q.pop();
if(memcmp(t.s,goal,sizeof(goal))==0)
return t.step;
int z;
for(int i=0;i<9;i++){
if(t.s[i]==0)
z=i;
}
int x=z%3;
int y=z/3;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0||nx>2||ny<0||ny>2)
continue;
node he;
memcpy(&he,&t,sizeof(struct node));
swap(he.s[y*3+x],he.s[ny*3+nx]);
ll sum=cantor(he.s);
if(!vis[sum]||(vis[sum]&&(he.step+1)<po[sum])){
po[sum]=he.step+1;
he.f=h(he.s)+he.step+1;
he.step++;
q.push(he);
vis[sum]=1;
}
}
}
}
int main(){
int x,k=8;
cin>>x;
while(x){
st[k--]=x%10;
x/=10;
}
for(int i=0;i<9;i++){
int xx=i%3;
int yy=i/3;
mp[goal[i]].x=xx;
mp[goal[i]].y=yy;
}
ll anss=axing();
cout<<anss<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249551.html
標籤：其他