UVa10181 - 15-Puzzle Problem(A*搜尋 )

2021-01-09

UVa

字數統計： 5.1k | 閱讀時間≈ 19分鐘

題目大意

大家有玩過數字拼圖嗎？這題是數字拼圖，給你一個隨機生成的數字拼圖，透過上下左右的方式讓空白附近的方塊跟空白交換，操作方式如下：

如果可以在 50 步以內玩到拼圖的所有數字從左到右、從上到下都按照數字順序，那稱之為完成。並輸出從初始拼圖至最終拼圖的操作，輸出字元只能是 U,D,L,R。
P.S. 完成必須要是此圖

如果不行，輸出 “This puzzle is not solvable.”

分析

這題好噁心…，好想回去寫數學…，數學好懂很多，這個讓我痛苦了 3 天左右、近 70 次左右的 TLE，嗚嗚。

這題可以用 IDA* or A* 去解決，比較推薦前者 IDA* 來解決，A* 有很多細節要進行處理，如果你是一位熱愛被題目折磨的好友就使用 A* 吧！

注意：此題目為 NP 問題，還沒有被科學家所研究出相關公式，只有研究出是否可解。

分析棋面

首先，我們先來定義棋面的意思，此名詞為每一個拼圖狀態的樣子，只要有進行移動，即是兩個不同的棋面，相信大家看的出來這題是必須要輸出路徑至變成最終拼圖狀態，那這時最好的演算法就是 Dijkstra，但棋面的複雜度應該是 $O(16! / 2) = 1.04e13$ ，其中除 2 是左邊方塊與右邊方塊交換、右邊方塊與左邊方塊交換相同，則其道理上下也是

時間複雜度為 $O(E \log \ V ) = 1.25e13$ 、 $E = 1.04e13 , V = 16$ ，有 16 個點要找出最短路徑最短路徑，有 $1.04e13$ 個狀態(邊)，但問題是最優秀的最短路徑演算法也需要對於這題做一些小技巧，不可以透過單純的 piority_queue 去解決，必須再透過一些小技巧來優化。

儲存棋面

我們粗略的判斷一下，每一個拼圖號碼都可以放在 16 個位置，總共有 16 個拼圖，並且拼圖順序不同也算是不同的棋面那總共會有 $2e9$ 個棋面， $E = 24 * 24 = 576$ 、 $V = 16$ ，如果透過簡單的 piority_queue，要對哪個棋面優先 top queue 環節。但由於每一次的狀態都會產生出 4 個狀態，因此有一個好的函示來判斷要先取出那個狀態做 dijkstra 是非常重要的，而這函式我們稱為啟發式搜尋 heuristic search

啟發式搜尋 heuristic search

判斷每一個拼圖是否在每個正確的位置上，沒有就加 1

這樣勢必是不行的，那麼在每次判斷的時候都必須跑一次迴圈進行測試，效率太差。且如果再正確位置空白下放 1 拼圖、正確位置 1 放空白拼圖，那麼此方法沒有辦法去解決此拼圖；因為只要換了就會讓錯的數字更多。

曼哈頓距離

曼哈頓距離，是幾何學中的用語，~~幾何學的用語都很不淺顯易懂~~，簡單來說的話就是，某一個拼圖要用最短步驟才可以到達正確拼圖的位置。

例如下圖中的 3，移到正確位置是多少曼哈頓距離。

正確答案是 4，最短只需要透過 4 步就可以到達正確拼圖的位置。而這樣可以透過國中就學習過的公式來進行推導 $|x_1 - x_2 | + |y_1 - y_2 |$ 。

剛剛我們已經決定好要用曼哈頓距離，那 piority_queue 的判斷就是曼哈頓距離最小嗎？

當然不是，嗚嗚。我在這裡也犯過錯QQQ。

正確來說的公式應該是 $已經行走的步驟 + 曼哈頓距離 * x = 優先權重$ ，其中 x 為係數並且要大於等於 1，程式這裡為 10，且優先權重最小的先進行此次的 dijkstra。

稍微解釋一下公式，為甚麼曼哈頓距離需要乘以 x，是因為曼哈頓距離是我們預估的權重數量，並不是我們真正已經走的步驟，曼哈頓距離是我們尚未走的步驟。

如果沒有放大倍率那會造成已經走的步驟跟曼哈頓距離其實是一樣的概念，但其實並不是，已經走的步驟必定是當前最佳解且已經走過路徑，但曼哈頓路徑還不確定路徑需要去嘗試，因此最好的方法就是讓
必曼哈頓距離乘以 x 來讓他在權重中的影響力降低，在我們先將優先權重最小的點拿出的情況下。

struct 使用 priority_queue 重點提醒

由於本人我在寫 pioirity_queue 犯過一個錯誤，其實是作者自己記憶力不好一直忘記QQ，因此寫在這邊稍微複習一下。

pioirity_queue 是 queue 的強化版，透過 heap sort 來強化權重的價值，預設情況下是遞減，因此如果我們特別自定一個 struct 時，C++ 並不清楚大小排序是如何？因此我們要自己寫一個 operator 來告知判斷大小的依據。

當要自己寫一個 operator 時，由於 pioirity_queue 是遞減，因此我們可以用一種偷懶的寫法，只要右邊的 struct 變數 A 小於左邊的 sturct 變數 st 依據是 A 的 h + step 要大於 st.h + st.step，透過此模式就可以在 priority_queue 遞減的情況下 struct 輸出的資料則是遞增。

struct state{
    int graph[4][4] ;
    int x,y;
    int h=-1 , step=0 ;
    string path ="" ;
    bool operator <(state st) const{
        return h + step > st.h + st.step ; 
        //因此在這邊 st 要大於 state 的依據就是， state 的 h + step 要大於 st，
        //如果有符合此條件，那 heap sort 就會往上一層去比較，以達到 heap 遞減。
        //如果 st 沒有大於 state，那 st 的 h + step 就比 state 大
    }

可閱讀此篇來進行更好的理解STL 之优先队列(priority_queue) Enstein_Jun

這裡我們就不使用 map or set 紀錄棋面，而是用 priority_queue 去找優先權重最小，如果找到重複也沒關係

為甚麼我們會這樣寫呢，根據上面的分析，棋面真的太多了，如果用 set or unorder_map 每次不斷去查詢是否有重複的棋面，那複雜度則會大幅上升。map 時間複雜度是 $o(log \ n )$ ，每次進行查詢與插入(新增棋面) 兩次的 $o(log \ n )$ ，會讓程式笨重許多。因此建議就是不進行記錄，我們透過 priority_queue 最小的取出的方式，直接取出最小值，只要我們能夠不斷取出最小值，小到 0 就會是答案。

可能會有人想問 priority_queue 複雜度也是 $o(log \ n )$ ，為甚麼就可以用它呢？那是因為我們一定要用到他，不然 dijkstra 就寫不出來了XD。

但注意的是，我們還是要禁止他不斷的左右交換、上下交換

由於我們缺少了紀錄棋面，因此在 Dijkstra 當下的棋面會不斷的嘗試進行上下左右交換，但假如剛剛我們才讓空白拼圖與某一數字交換，現在又在交換回來不就徒勞無功了嗎？因此我們要拒絕這種可能性，而解決此問題就是紀錄剛剛的 Path，如果剛剛從左來，那我們就禁止往右、剛剛從上來，就禁止往下.、剛剛從下來，就禁止往上、剛剛從右來，就禁止往左。

判斷拼圖有沒有解

在數字拼圖中是有無解的情況發生，舉個例子， n = 2，透過 (1,1) = 1, (1,2) = 3 , (2,1) = 2，讀者嘗試看看是否能夠解出XD。

一定沒有辦法解出。能解出還請私密我XD，你太強了www。在數字拼圖的論文中則有講到先將數字拼圖展開成一維陣列，之後透過下述規則判斷是否可解。

N 為奇數，那遞減數對為偶數時可以被解出
N 為偶數
- 如果空白拼圖是出現在由底部開始數的奇數時，則遞減數對在偶數時可解
- 如果空白拼圖是出現在由底部開始數的偶數時，則遞減數對在奇數時可解
遞減數對是甚麼？
如上面的 n = 2 例子，展開成一維陣列即是 1,3,2，那 3,2 就是遞減數對，數對定義為只要兩個數字且前面數字大於後面數字就代表一組數對，但必須維持原本一維陣列的順序。
更好的解釋請查看 How to check if an instance of 15 puzzle is solvable? GeeksforGeeks

證明

我們先將拼圖變成一維陣列後，可以知道在水平移動時一維陣列並不會被更動，空白拼圖不可以被當作數字，因此不會用 (數字,空白) 的遞減數對發生；但在垂直移動時一維陣列的值就會被改動，且影響的方式是將某一數字與另一數字位置交換，我們稱之為對調。

由於數字拼圖的每一步可以想像成每一組數字的排列，我們只是將她重新排列成某一狀態，這時我們可以將題目理解成將 1,2,3,4,5 轉換成 4,2,1,3,5，只需要將 4 移動到 1 前面再來讓 1 移動到 3 前面即可得到答案。

再來讓 4 移動到 1 前面總共移動了 3 步，讓 1 移動到 3 前面總共移動了 2 步，因此每次的移動就會是 $n-1$ ，n 為中間有多少數字。

再來我們要怎麼用奇偶數來解決是否可以解出來呢？

如果我們假設綠色格子是奇數，紅色格子是偶數，那我們要能夠將空白拼圖從紅色格子移到綠色格子時，奇偶數一定會產生變化，根據上方遞減數對的交換的說明。

因此我們就可以得知一個結論，透過舉例說明：

一開始的狀態，紅色的格子(3,3)為空白區塊，且目前為奇數。
最終狀態，綠色的格子(4,4)為空白區塊，且為偶數。
這樣一定可以達到，對八，因為只要進行一次交換那奇偶數就會交換。
那我們把最終型態改變一下，綠色的格子(4,4)為空白區塊，且為奇數。
這樣就勢必沒有辦法達到，因為紅色格子在跟綠色格子交換時奇偶數就會被改變，因此我們永遠不可能達到此情況。

題目要求我們的最終棋面的遞減數對為 0，因此空白最下方並且遞減數對為偶數。

更好的解釋請看你解不開！數字華容道 (15 puzzle) 與奇偶性 - 方塊轉不快，但要注意這裡有將空白拼圖當作 16 但此證明沒有，但他的動畫很棒，因此建議大家觀看。

再來我們可以得知，如果是水平互換時，遞減數對不變，垂直互換時則遞減數對則增加或減少 $N-1$ ，在沒有 16 的情況下。

如果 n 是偶數，那麼在此公式下 N−1 出來必定會是奇數，因此每次的遞減數對都會少了奇數
- 因此如果空白為底部開始數的第一行時，那麼遞減數對在偶數時可解
- 因此如果空白為底部開始數的第二行時，那麼遞減數對在奇數時可解
  因為每次的遞減數對都會增加或減少 $N-1$ ，N 為 puzzle 寬度
根據上面兩個重點就可以得知 N 為偶數且空白拼圖是出現在由底部開始數的奇數時，則遞減數對在偶數時可解
如果空白拼圖是出現在由底部開始數的偶數時，則遞減數對在奇數時可解
如果 n 是奇數，那麼垂直移動時遞減數對會減少 $N-1$ ，但由於 N 為奇數因此公式下來必定是偶數，但偶數減偶數還是偶數XD，好饒舌www，因此我們只需要判斷遞減數對為偶數即可。

透過此結論就可以知道

如果 N 為奇數，則能夠被解出的狀態只有遞減數對為偶數
如果 N 為偶數
- 如果空白拼圖是出現在由底部開始數的奇數時，則遞減數對在偶數時可解
- 如果空白拼圖是出現在由底部開始數的偶數時，則遞減數對在奇數時可解

判斷 puzzle 是否可被解的小優化

cnt = 遞減數對、x 為一般我們在計算時的方向位置，舉例：(3,2) = 空白，那 x 就等於 3。
如果 x 等於奇數時，就表示由底部開始算就會是偶數，因為 N = 4，當 n = 4 那從底部算就會是 1，因此剛好符合條件底部為偶數時，遞減數對在奇數是可解，所以我們就直接 $+x$ ，因為奇數加偶數還是等於奇數。

反之，那 x 等於偶數時，底部就會是奇數，相加時狀態不會改變，如果 cnt = 奇數，那加上偶數還是奇數，如果 cnt = 偶數，那加上偶數還是偶數，因此只要 mod 2 == 0 就表示不可解。

1
2
3

if((cnt+x)%2 ==0) //判斷是否可解，這裡用了小優化，可看上面文章理解
    return false;
return true ;

小優化 string

string 用平常的 +=，時間複雜度比較高，因此這裡我們使用 string.push_back(char)，會更好些，因為我們要不斷的做在字串尾巴中加入方向，如果一直不段使用 += 會拖累我們的效能，因此用string.push_back(char)會更為優秀些。

觀念重點

A* 用法使用得宜
piority_queue struct 寫 operator
puzzle 是否可以被解出
- 核心推理證明
- 遞減數對與空白在哪個位置要判斷奇偶數的小優化
不可以使用 map or set 紀錄
跑 dijkstra 拒絕回到上一步
紀錄正確位置的寫法
string 小優化

參考來源

心得

這題好難…，可能是我第一次學 A* 在寫這份題目中我獲得了許多痛苦的感覺XD，畢竟在還沒有辦法把題目解開之前人都不會是開心的八，歷經了 4 次程式版本，看了許多網路上大佬的程式碼仔細研究分析，終於找到適合我學習的程式碼好開心><。題外話：我寫了 4 個版本，結果都 TLE 卡住

就算通關後還是為了要能夠讓我完整了解此題的運作，我又花了很多時間不斷去理解、嘗試，最終理解至現在，不得不說學習到了很多觀念與事物，但在了解的過程中也獲得了很多絕望感XD，因為想不出來嘛，就很容懷疑自己到底為甚麼要走演算法，讓自己過的那麼不開心。但其實通關後的成就感以及讓我學習到的思維，我認為是不會愧對於前面的痛苦地。

但每次想到要寫演算法，心還是會揪一下XD。

不過這裡還是要謝謝齊芫，他在我學習這題的過程中不斷指出我的邏輯問題，也退回我的邏輯概念讓我有機會可以去重新學習此題，減少了我在未來中可能會因為這次的學習瑕疵而犯的漏洞，很謝謝他。

要是沒有他每次給我一個邏輯壓制，我可能現在還覺得我很會寫演算法呢XD。

也謝謝在網路上提供資料的大神們，沒有你們我連學習的機會都沒有…，然後農場文章真的不要那麼氾濫，Google 管一下拉。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
int n ;
//unordered_map<string,int> visit ;
//set<string> visit ; // no set will be AC
int direct[4][4] = {{0,1},{0,-1},{1,0},{-1,0}}; //方向
int place[18][2] ; //紀錄最終棋面每一個數字的 x,y 座標
char dname[4] = {'R' , 'L' , 'D' , 'U'}; // 方向

struct state{
    int graph[4][4] ;
    int x,y;
    int h=-1 , step=0 ;
    string path ="" ;
    bool operator <(state st) const{ //priority_queue 使用
        return h + step > st.h + st.step ; //輸出最小
    }

    void print(){ //debug 測試用
        for(int i = 0 ; i < 4 ; i++){
            for(int j = 0 ; j < 4 ; j++)
                cout << graph[i][j] << ' ' ;
            cout << '\n' ;
        }
        cout << '\n' ;
    }

};

int h(int graph[][4]){ //曼哈頓距離
    int cnt = 0 ;
    for(int i = 0 ; i < 4 ; i++){
        for(int j = 0 ; j < 4 ; j++){
            if(graph[i][j] == 0 || (i == place[graph[i][j]][0] && \
                                      j == place[graph[i][j]][1]  ))
                continue ;
            cnt += abs(place[graph[i][j]][0] - i) + abs(place[graph[i][j]][1] - j ) ;
        }
    }
    return cnt * 10  ;
}

bool isboard(int x , int y ){ //判斷邊界
    if(x >= 0 && x < 4 && y >= 0 && y < 4)
        return true ;
    return false ;
}

bool isback(string path , char nxtD ){ //拒絕回到上一步的棋面
    if(path.size() == 0) return false ; 
    char D = path[path.size()-1] ;
    if(D == 'L' && nxtD == 'R' ) return true ;
    if(D == 'R' && nxtD == 'L' ) return true ;
    if(D == 'U' && nxtD == 'D' ) return true ;
    if(D == 'D' && nxtD == 'U' ) return true ;
    return false ;
}

bool Astar(state input ){ // Astar 核心
    priority_queue<state> q ;
    //visit.clear() ;
    int x , y;
    state now , next ;
    q.push(input);
    while(!q.empty()){
        now = q.top() ; q.pop() ;
        //now.print();
        for(int i = 0 ; i < 4 ; i++){ //方向選擇
            x = now.x + direct[i][0] ;
            y = now.y + direct[i][1] ;
            if(!isboard(x,y)) continue ; //判斷邊界
            if(isback(now.path,dname[i])) continue ; //判斷是否回到上一步
            next = now ; //TLE key because this line go to 85 before.
            next.step = now.step + 1 ;
            if(next.step > 50 ) continue ; //判斷是否超過 50 步
            swap(next.graph[x][y] , next.graph[now.x][now.y]);
            //now.print() ;
            //cout << x << ' ' << y << '\n' ;
            //next.print();
            next.x = x ; next.y = y ;
            next.h = h(next.graph) ;
            next.path.push_back(dname[i]) ;
            q.push(next);
            if(next.h == 0 ){ // 判斷是否已走到正確答案
                cout << next.path << '\n' ;
                return true ;
            }
            //cout << next.path << '\n' ;
            //next.print();
        }
    }
    return false ;
}

bool issolve(int graph[][4]){ //此拼圖是否可以被解出
    int cnt = 0 , x , y  ;
    int num[16] = {};
    for(int i = 0 ; i < 4 ; i++){ //一維陣列化
        for(int j = 0 ; j < 4 ; j++){
            num[cnt++] = graph[i][j] ;
            if(graph[i][j]==0) x = i , y = j ;
        }
    }
    cnt = 0 ;
    for(int i = 0 ; i < 16 ; i++){ //有多少遞減數對
        for(int j = i+1 ; j < 16 ; j++){
            if(num[j] && num[j] < num[i]) cnt++ ;
        }
    }
    if((cnt+x)%2 ==0) //判斷是否可解，這裡用了小優化，可看上面文章理解
        return false;
    return true ;
}

int32_t main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    int cnt = 1;
    for(int i = 0 ; i < 4 ; i++){ //紀錄正確答案位置
        for(int j = 0 ; j < 4 ; j++){
            place[cnt][0] = i ;
            place[cnt++][1] = j ;
        }
    }

    cin >> n ;
    while(n--){ //測資開始
        state input ;
        for(int i = 0 ; i < 4 ; i++){
            for(int j = 0 ; j < 4 ; j++){
                 cin >> input.graph[i][j] ;

                 if(input.graph[i][j] == 0)
                    input.x = i , input.y = j ;
            }
        }
        if(!issolve(input.graph) || !Astar(input))
            cout << "This puzzle is not solvable.\n" ;
    }
    return 0 ;
}