雙向BFS和啟發式搜索的應用
題意簡述
有12個旋鈕，每個旋鈕開始時處於狀態 \(1\) ~ \(4\) ，每次操作可以往規定方向轉動一個旋鈕 （\(1\Rightarrow2\Rightarrow3\Rightarrow4\Rightarrow1\)） ，並且會觸發一次連鎖反應：處於某個狀態的旋鈕在旋轉時會引起另一個旋鈕發生相同方向的轉動（另一個旋鈕轉動不會再觸發連鎖反應）。問將12個旋鈕都置為 \(1\) 至少需要幾次轉動，並輸出每次轉動的旋鈕編號。
單向BFS
直接暴力地進行單向 \(BFS\) ，每次轉動都有 \(12\) 種選擇，時間複雜度是 \(O(12^{step})\) ，看數據範圍，最高的步數可達 \(17\) 步，必定 \(TLE\) 。但是這樣簡單如果優化的比較好可以得 \(50\) ~ \(60\) 分（沒吸氧氣，吸了氧氣反而更低了）。
單向BFS評測記錄
超時的主要原因是搜索樹過於龐大，而我們會發現本題起始狀態和終止狀態是明確的，這時我們就可以使用神奇的雙向 \(BFS\) 來限制搜索樹的生長。
雙向BFS
雙向 \(BFS\) 非常適合在起始狀態和終止狀態明確的條件下使用，做法是從起點和終點同時進行單向 \(BFS\) ，讓兩邊 \(BFS\) 搜索樹的生長受到對面搜索樹的限制，不要過於野蠻生長，偏離目標太遠。自己畫了一張很醜很醜的對比圖，應該可以便於理解。
可以看到雙向 \(BFS\) 可以在某一狀態發現相同時就停止了，通過回溯可以找到沿路選擇的點。再看看本題的數據範圍，最大的點正向和反向 \(BFS\) 最多是 \(9\) 步, \(12^9\) 是 \(5\times10^8\) 的量級,勉強可以在一秒衝過去。事實上我最大的點用時在 \(200ms\) ~ \(300ms\) 之間，還是很穩的。
最好的一次雙向BFS記錄
狀態存儲
可以把兩個二進制位當做一個四進制位,把每個旋鈕狀態減一後就剛好可以存下了，即1對應0,2對應1，以此類推。先講一下讀入處理。
int button,Start = 0;
For(i,0,11){
button = read(); //讀入第i+1個旋鈕狀態
Start |= (button - 1) << (i << 1); //記錄初始狀態
For(j,0,3) nxt[i][j] = read()-1;
}
我代碼中的旋鈕編號和狀態全部進行了減一處理（後面描述時我都會說+1），方便位運算操作。注意記錄初始狀態時要將 \(i*2\) （即左移一位），因為我們把兩個二進制位當做一個四進制位了，後面也有這樣的乘2處理。再用一個數組 \(nxt\) 記錄第 \(i+1\) 個旋鈕在 \(j+1\) 狀態下進行旋轉時，會帶動第 \(nxt[i][j]+1\) 個旋鈕轉動。
狀態轉移
首先正向和反向的 \(BFS\) 的轉移方式是不一樣的。設當前轉到的是第 \(i+1\) 個旋鈕，它現在處於 \(j+1\) 狀態。
- 正向：將第 \(i+1\) 個旋鈕按規定方向轉動一次，同時帶動第 \(nxt[i][j]+1\) 個旋鈕轉動。旋轉後狀態可以用\((j+1)\&3\) 表示（這樣可以實現旋鈕位於4狀態，即 \(j=3\) 時，旋轉後變成1 ，即 \(j = 0\) 的操作）。
- 反向：將第 \(i+1\) 個旋鈕按規定的相反方向轉動一次，如果其轉動後的狀態為 \(k+1\) ,則帶動第 \(nxt[i][k]+1\) 個旋鈕也以相反方向轉動。逆向旋轉後狀態可以用\((j+3)\&3\) 表示。
我們把正向方向定義為1，反向方向定義為2，當前方向為 \(direction\) ，當前所有按鈕狀態為 \(state\) ,有：
int si,sNext,nx,nextState;
For(i,0,11) {
if (direction == 1) { //正向
si = (state >> (i << 1)) & 3; //1、獲取第i+1個旋鈕狀態（0~3）
nx = nxt[i][si]; //2、獲取牽連旋鈕編號
sNext = (state >> (nx << 1)) & 3; //3、獲取牽連旋鈕狀態，方式同1
nextState = state ^ (si << (i << 1)) ^ (((si + 1) & 3) << (i << 1)); //4、修改狀態為第i+1個旋鈕旋轉後的狀態
nextState ^= (sNext << (nx << 1)) ^ (((sNext + 1) & 3) << (nx << 1)); //5、修改狀態為牽連旋鈕旋轉後的狀態
} else { //反向
si = (state >> (i << 1)) & 3;
nx = nxt[i][(si + 3) & 3]; //獲取第i+1個旋鈕逆向旋轉後的牽連旋鈕編號
sNext = (state >> (nx << 1)) & 3;
nextState = state ^ (si << (i << 1)) ^ (((si + 3) & 3) << (i << 1)); //修改狀態為第i+1個旋鈕逆向旋轉後的狀態
nextState ^= (sNext << (nx << 1)) ^ (((sNext + 3) & 3) << (nx << 1));//修改狀態為牽連旋鈕逆向旋轉後的狀態
}
}
\(Code:\)
#include <bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
inline int read(){
int sum = 0,fu = 1;char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') fu = -1;ch = getchar();}
while(isdigit(ch)) { sum = (sum<<1)+(sum<<3)+(ch^48);ch =getchar();} return sum * fu;
}
const int N = 1<<24;
bool vis[N];
int nxt[14][6],fa[N],choice[N],v[N],flag,m1,m2,mid,ans1[30],ans2[30];
queue<int>q;
int main(){
int button,Start = 0;
For(i,0,11){
button = read(); //讀入第i+1個旋鈕狀態
Start |= (button - 1) << (i << 1); //記錄初始狀態
For(j,0,3) nxt[i][j] = read()-1;
}
vis[Start] = vis[0] = 1; //是否訪問過
v[Start] = 1; v[0] = 2; //區分方向
q.push(Start);
q.push(0);
while(!q.empty() && !flag){
int state = q.front(),direction = v[state];
q.pop();
int si,sNext,nx,nextState;
For(i,0,11){
if(direction == 1){ //正向
si = (state >> (i << 1))&3; //1、獲取第i+1個旋鈕狀態（0~3）
nx = nxt[i][si]; //2、獲取牽連旋鈕編號
sNext = (state >> (nx << 1)) & 3; //3、獲取牽連旋鈕狀態，方式同1
nextState = state ^ (si << (i << 1)) ^ (((si + 1) & 3) << (i << 1)); //4、修改狀態為第i+1個旋鈕旋轉後的狀態
nextState ^= (sNext << (nx << 1)) ^ (((sNext + 1) & 3) << (nx << 1)); //5、修改狀態為牽連旋鈕旋轉後的狀態
} else{ //反向
si = (state >> (i << 1))&3;
nx = nxt[i][(si+3)&3]; //獲取第i+1個旋鈕逆向旋轉後的牽連旋鈕編號
sNext = (state >> (nx << 1)) & 3;
nextState = state ^ (si << (i << 1)) ^ (((si + 3) & 3) << (i << 1)); //修改狀態為第i+1個旋鈕逆向旋轉後的狀態
nextState ^= (sNext << (nx << 1)) ^ (((sNext + 3) & 3) << (nx << 1));//修改狀態為牽連旋鈕逆向旋轉後的狀態
}
//如果這個狀態在之前訪問過
if(vis[nextState]){
if(v[nextState] == direction) continue; //同方向的直接跳過，之前到達的時候肯定不劣於現在
/*
* 不同方向說明已經找到答案了
* m1 記錄正向與逆向的連接點
* m2 記錄逆向與正向的連接點
* mid 記錄從state狀態轉移到nextState狀態選擇的旋鈕編號
*/
m1 = direction == 1 ? state : nextState;
mid = i+1;
m2 = direction == 1 ? nextState : state;
flag = 1;break;
}
vis[nextState] = 1;
v[nextState] = direction; //繼承方向
fa[nextState] = state; //用於回溯操作
choice[nextState] = i + 1; //記錄本次操作
q.push(nextState);
}
}
int cnt1 = 0,state = m1,cnt2 = 0;
//正向回溯
while(state != Start){
ans1[++cnt1] = choice[state];
state = fa[state];
}
//逆向回溯
state = m2;
while(state != 0){
ans2[++cnt2] = choice[state];
state = fa[state];
}
//總步數，還要加上中間那一步mid操作
printf("%d\n",cnt1+cnt2+1);
for(int i = cnt1; i; i--) printf("%d ", ans1[i]);
printf("%d ",mid);
For(i,1,cnt2) printf("%d ", ans2[i]);
return 0;
}
啟發式搜索
雙向 \(BFS\) 已經夠快了，但是我們可以使用更快的啟發式搜索。常用的啟發式搜索有 \(IDA*\) 和 \(A*\) ，聽說前者被卡了，我們就用 \(A*\) 吧。即使你可能不知道什麼是 \(A*\) 算法（我做這題的時候就沒聽說過），也可以繼續往下看。
在 \(A*\) 算法中，我們要利用當前狀態的信息對狀態進行評價，以此來決定下一次的操作，極大地限制了搜索樹的生長。首先介紹一個特別的估價函數 \(F^*\) 來表示：\(F^*(x)=g^* (x)+h^*(x)\) 。其中 \(g^* (x)\) 表示從初始狀態到當前狀態所付出的最小代價（在本題中意義為操作步數），而 \(h^*(x)\) 是從當前狀態到目標狀態走最佳路徑所付出的代價。在實際代碼中我們使用的其實是 \(F(x)=g (x)+h(x)\) ，因為我們實際上是不知道這個加星後的函數的，但是我們可以通過一些限制，讓不加星的函數也可以在一定範圍內求解出正確答案;
- \(g(x)\) 是對 \(g^*(x)\) 的估計，且 \(g(x)>0\) ,在代碼中我們記錄的就是步數；
- \(h(x)\) 是 \(h^*(x)\) 的下界，即對任意狀態均有 \(h(x)≤h^*(x)\)。在代碼中我們定義為 \(12\) 個旋鈕在不考慮牽連時都轉到 \(1\) 要多少步，再除以 \(2\) ,這樣就可以保證 \(h(x)\) 肯定會比實際要轉的次數要少（一次操作恰好就可以讓兩個旋鈕都向目標狀態轉一次，而實際上可能會讓某個旋鈕轉過目標狀態，從而要轉更多次數），
\(h(x)\) 是一個比較玄學的東東，沒有唯一的定義，不同的定義可能會導致程序執行效率和結果不同，這題中你還可以乘一個係數給他，能明顯加快運行效率。經過筆者多次測試，發現給 \(h\) 乘上係數從 \(1.1\) ~ \(2.3\) 都能 \(AC\) 這道題，但是乘 \(2.4\) 時會 \(WA\) 掉一個點。變化趨勢是這個係數越大，跑得越快，最大的點可以跑進 \(100ms\) 。這是因為係數越大越接近真實值 \(h^*(x)\)，但是更大的係數不能保證一定可以得到最優解。
代碼實現類似 \(Dijkstra\) 算法，定義一個結構體存狀態和這個狀態對應的估價函數值 \(F\) 。每次從小根堆中取出 \(F\) 最小的狀態進行轉移，存狀態和轉移狀態的操作和上面雙向 \(BFS\) 相同，這裡直接給出代碼。
\(Code:\)
#include <bits/stdc++.h>
using namespace std;
#define For(a,sta,en) for(int a = sta;a <= en;a++)
inline int read(){
int sum = 0,fu = 1;char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') fu = -1;ch = getchar();}
while(isdigit(ch)) { sum = (sum<<1)+(sum<<3)+(ch^48);ch =getchar();} return sum * fu;
}
const int N = 1<<24;
int g[N],nxt[14][6],fa[N],ans[30],choice[N];
struct node{
int state; //狀態
double F; //狀態對應估價函數值
node(int s):state(s){ //構造函數，冒號後面部分相當於 state = s;
double h = 0;
F = 0;
For(i,0,11) if((s>>(i<<1))&3) h += 4 - ((s >> (i << 1)) & 3); //計算不處在狀態1的旋鈕的對應的h值
F = h / 2 + g[s]; //可以在h/2前乘一個玄學係數
}
bool operator<(const node &y) const{
return F > y.F; //估價函數值小的放前面
}
};
priority_queue<node>q;
int main(){
int button,Start = 0;
For(i,0,11){
button = read(); //讀入第i+1個旋鈕狀態
Start |= (button - 1) << (i << 1); //記錄初始狀態
For(j,0,3) nxt[i][j] = read()-1;
}
q.push(node(Start)); //調用構造函數，順便計算出估價函數值
g[Start] = 0;
int flag = 1;
while(!q.empty()&&flag){
int state = q.top().state;
q.pop();
int si,sNxt,nx,nextState;
For(i,0,11){
si = (state>>(i<<1))&3;
nx = nxt[i][si];
sNxt = (state>>(nx<<1))&3;
nextState = state ^ (si << (i << 1)) ^ (((si + 1) & 3) << (i << 1)) ^ (sNxt << (nx << 1)) ^ (((sNxt + 1) & 3) << (nx << 1));
//如果沒有訪問過就可以轉移新狀態了
if(!g[nextState]){
g[nextState] = g[state] + 1;
fa[nextState] = state; //用於回溯
choice[nextState] = i + 1;
if(nextState == 0) { flag = 0;break;} //到達目標狀態
q.push(node(nextState));
}
}
}
int cnt = 0,state = 0;
while(state != Start){
ans[++cnt] = choice[state];
state = fa[state];
}
printf("%d\n",cnt);
for(int i = cnt;i;i--) printf("%d ",ans[i]);
return 0;
}
對於 \(A^*\) 算法我可能有些地方描述不夠嚴謹，如果有錯誤的地方歡迎指出。做完這道題建議去做一下 P1379 八數碼難題 ,可以同時用單向 \(BFS\) ，雙向 \(BFS\) ，\(A^*\) 和 \(IDA^*\) 做這道題，如果每個方法都寫一下一定受益良多。
