摘要訊息 : 如何讓老鼠找到從入口到出口的路?

目錄 顯示

0. 前言

迷宮是一個矩形區域, 左上角為迷宮的入口, 右下角為迷宮的出口.

Figure 1-1. 無遮擋迷宮

迷宮內部包含不可穿越的障礙物, 這些障礙物和迷宮的邊界平行. 老鼠從入口進入迷宮, 尋找一條可行路徑使得老鼠可以從迷宮中走出, 要求路徑上不能存在障礙物. 除此之外, 要求路徑上的每一個位置都位於其相鄰位置的上, 下, 左或著右, 即不存在跳躍的路徑. 這樣的問題, 我們稱之為迷宮老鼠問題.

Figure 1-2. 迷宮

本文的目錄可能影響前面章節的排版, 故本篇文章的目錄預設為隱藏不展開狀態, 需要閣下手動展開.

更新紀錄 :

  • 2022 年 5 月 12 日進行第一次更新和修正.

1. 迷宮老鼠

我們使用一個 m \times n 矩陣來表示迷宮, 不妨設為 A = (a_{ij})_{m \times n}. 其中, a_{11} 表示入口, a_{mn} 表示出口, m 和 n 分別表示矩陣的行數和列數. 那麼有 \displaystyle {a_{ij} = \begin {cases} 1 & {\text {第 } i \text { 行第 } j \text { 列處存在障礙物}} \\ 0 & {\text {第 } i \text { 行第 } j \text { 列處可以通行}}. \end {cases}} 我們在玩迷宮遊戲的時候, 當發現一條路徑行不通時, 會回到之前的某一個路口走新的路徑, 這個路口一般是我們最後遇到的那個分岔路口. 由於是回到前一個遇到過的分岔路口, 因此我們需要保存走過的路, 然後每一次從最後保存的那個入口重新走. 自然地, 我們使用堆疊 (《【資料結構】堆疊》) 作為基本的資料結構.

因為最終我們需要得到的是路徑, 而並不僅僅是走過的分岔路口, 所以我們需要將所有位置都放入到堆疊中. 首先以入口位置作為起始位置, 將其放入堆疊. 為了防止在尋路的過程中又繞回道已經走過的路徑, 對於已經到達過的路徑, 我們在每一個位置上都放置一個障礙物, 即修改 a_{ij} = 1. 其中, i = 1, 2, ..., m, j = 1, 2, ..., n. 從起始位置開始, 每到達一個新的位置都將其放入堆疊中, 並放置障礙物. 接著, 檢查四周是否存在空閑位置, 如果有, 那麼就去空閑的位置; 如果沒有, 就說明我們走進了死胡同, 那麼將這個位置從堆疊中移除, 再從堆疊中取出一個位置, 回到這個位置. 不斷重複上述步驟, 若能到達終點, 則堆疊中必定儲存了一條從入口到出口的路徑; 如果最終回溯到了起點位置, 並且起點位置四周都被放置了障礙物, 那麼迷宮無解.

在尋路的過程中, 每一個迷宮幾乎都會遇到某一個位置存在多個路口可以走. 此時, 我們可以作一個規定 : 優先檢測向下的路徑; 當向下的路徑無法到達的時候, 檢測向右的路徑; 當向右的路徑無法到達的時候, 檢測向上的路徑; 當向上的路徑無法到達的時候, 最後檢測向左的路徑. 也就是說, 對於空閑位置的檢查, 順序為下右上左. 當監測到有空閑位置可以走的時候, 不再繼續檢測, 直接走到那個空閑位置.

當來到出口的時候, 不斷從堆疊中取出位置, 就可以得到這個迷宮的一條路徑解. 但是由於堆疊每次只能從尾部取出元素, 所以最終得到的是一條反向的路徑, 即從出口到入口的一條路徑. 有需要的話, 可以再把這條路徑作反向處理.

2. 複雜度分析

由於迷宮有 m \times n 個位置, 並且堆疊中會儲存 O(mn) 個位置, 所以解決迷宮老鼠問題的最終空間複雜度為 \Theta(mn). 為了找到出口, 最壞的情況下 (如果規定了一個合理的行走方案, 最壞情況不會發生), 我們需要尋訪全部位置, 因此時間複雜度為 \Theta(mn).

3. 最短路徑

雖然我們已經找到了迷宮老鼠問題的解決方案, 但是我們可能總是希望找到最佳解, 即老鼠可以走出迷宮的最短路徑. 需要注意的是, 第 2 節中的解決方案得到的路徑解並不一定是最短路徑. 要獲得最短路徑, 我們需要借助佇列 (《【資料結構】佇列》). 在起點和終點之間尋找一條最短路徑除了需要記錄下路徑之外, 還需要記錄從入口到目前位置的距離.

由於最短路徑需要計算路徑的長度, 所以我們改變 a_{ij} 的記法 : \displaystyle {a_{ij} = \begin {cases} -1 & {\text {第 } i \text { 行第 } j \text { 列處存在障礙物}} \\ 0 & {\text {第 } i \text { 行第 } j \text { 列處可以通行}} \\ d(a_{ij}) & {\text {第 } i \text { 行第 } j \text { 列距離起點 } a_{11} \text { 的最短路徑長度}}. \end {cases}} 設起點 a_{11} = 1, 那麼和起點相鄰且能夠達到的位置就被標記為 2. 類似的, 如果某個位置相鄰地位於被標記為 2 的位置, 並且這些被標記為 2 的位置可以到達的未標記位置就會被記為 3. 不斷重複, 直到沒有任何位置可以被標記 (也就是迷宮無解) 或著到達了終點的時候停止標記. 標記結束之後, 並不是從起點移動到終點, 而是從終點開始向起點移動. 每一次向比當前位置的標記小 1 的位置移動, 直到到達起點位置為止.

在距離標記的過程中, 我們需要佇列的幫助. 每一次標記完一個位置, 便將這個位置放入佇列當中. 當標記完成之後, 再從佇列中取出另外一個位置再次進行標記. 直到佇列中不再有元素可取位置.

使用佇列作為資料結構找到迷宮最短路徑的解決方案的複雜度仍然保持不變, 和使用佇列作為資料結構的解決方案相同.

4. 實作

我分別實作了使用堆疊和佇列作為資料結構解決方案的 C++ 程式碼供大家參考.

#include <vector>
#include <utility>
#include <stdexcept>

std::vector<std::pair<int, int>> find_path(bool **maze, int m, int n) {
    constexpr std::pair<int, int> start_position {0, 0};
    constexpr std::pair<int, int> end_position {m - 1, n - 1};
    std::vector<std::pair<int, int>> path {};
    std::pair<int, int> position {0, 0};
    path.push_back(position);
    maze[position.first][position.second] = true;
    while(true) {
        if(position.first + 1 < m and not maze[position.first + 1][position.second]) {
            ++position.first;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.second + 1 < n and not maze[position.first][position.second + 1]) {
            ++position.second;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.first - 1 >= 0 and not maze[position.first - 1][position.second]) {
            --position.first;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }else if(position.second - 1 >= 0 and not maze[position.first][position.second - 1]) {
            --position.second;
            maze[position.first][position.second] = true;
            path.push_back(position);
            if(position == end_position) {
                break;
            }
        }
        path.pop_back();
        position = path.back();
        if(position == start_position) {
            throw std::runtime_error("There is no way from entrance to export!");
        }
    }
    return path;
}
#include <stack>
#include <queue>
#include <utility>

int shortest_path(int **maze, int m, int n) {
    std::queue<std::pair<int, int>> q;
    maze[0][0] = 1;
    q.push({0, 0});
    while(true) {
        auto position {q.front()};
        q.pop();
        bool in {};
        if(position.first + 1 < m and maze[position.first + 1][position.second] == 0) {
            maze[position.first + 1][position.second] = maze[position.first][position.second] + 1;
            ++position.first;
            q.push(position);
            in = true;
        }
        if(position.second + 1 < n and maze[position.first][position.second + 1] == 0) {
            maze[position.first][position.second + 1] = maze[position.first][position.second] + 1;
            ++position.second;
            q.push(position);
            in = true;
        }
        if(position.first - 1 >= 0 and maze[position.first - 1][position.second] == 0) {
            maze[position.first - 1][position.second] = maze[position.first][position.second] + 1;
            --position.first;
            q.push(position);
            in = true;
        }
        if(position.second - 1 >= 0 and maze[position.first][position.second - 1] == 0) {
            maze[position.first][position.second - 1] = maze[position.first][position.second] + 1;
            --position.second;
            q.push(position);
            in = true;
        }
        if(in) {
            continue;
        }
        if(q.empty()) {
            if(maze[m - 1][n - 1] == 0) {
                throw std::runtime_error("There is no way from entrance to export!");
            }
            break;
        }
    }
    return maze[m - 1][n - 1];
}

std::stack<std::pair<int, int>> find_shortest_path(int **maze, int m, int n) {
    constexpr std::pair<int, int> start_position {0, 0};
    std::stack<std::pair<int, int>> s;
    s.push({m - 1, n - 1});
    while(true) {
        auto position {s.top()};
        if(position == start_position) {
            break;
        }
        if(position.first - 1 >= 0 and maze[position.first - 1][position.second] == maze[position.first][position.second] - 1) {
            --position.first;
            s.push(position);
        }else if(position.second - 1 >= 0 and maze[position.first][position.second - 1] == maze[position.first][position.second] - 1) {
            --position.second;
            s.push(position);
        }else if(position.first + 1 < m and maze[position.first + 1][position.second] == maze[position.first][position.second] - 1) {
            ++position.first;
            s.push(position);
        }else if(position.second < n and maze[position.first][position.second + 1] == maze[position.first][position.second] - 1) {
            ++position.second;
            s.push(position);
        }
    }
    return s;
}

5. 推廣

值得注意的是, 迷宮老鼠問題可以推廣到任意網格路徑問題. 只要問題可以化約為在網格中尋找路徑或者尋找最短路徑甚至最長路徑, 那麼都可以使用迷宮老鼠的解決方案來解決這些問題.