摘要訊息 : 利用緩衝區, 對駛入列車的車廂進行重排.

0. 前言

一列貨運列車有 n 節車廂, 第 i 節車廂停靠在第 i 個站點. 假設列車在裝載的時候, 不一定按照順序進行裝載 (例如裝載順序為 581742963, 3 為車頭). 在列車到達終點站之前需要經過一個緩衝站點, 緩衝站點中有 k 個緩衝軌道. 當列車駛出緩衝站點之後, 要求所有車廂有序裝載 (即對於 581742963, 要求最終的順序為 123456789 或者 987654321).

更新紀錄 :

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

1. 列車重排

從第 0 節中, 我們可以大致了解列車重排問題的背景, 現在我們使用數學語言對列車重排問題進行嚴謹的描述.

定義 1. 針對某個排列 b_{1}b_{2}...b_{n}, 有一標準排列 a_{1}a_{2}...a_{n}. 要求使用 k 個緩衝區, 每一次只能將一個元素放入緩衝區, 每一次也只能從緩衝區取出一個元素. 當所有元素從緩衝中取出之後, 排列 b_{1}b_{2}...b_{n} 變為標準排列 a_{1}a_{2}...a_{n}. 其中對於任意 b_{j}, 必有一 a_{i} 與之對應, 即 a_{i} = b_{j}. 其中, i, j = 1, 2, ..., n.

根據定義 1 中的 “每一次只能有一個元素進入緩衝區, 每一次只能從緩衝區中取出一個元素”, 有兩個資料結構的性質和這樣的要求相符合, 即堆疊 (《【資料結構】堆疊》) 和佇列 (《【資料結構】佇列》).

2. 堆疊作為緩衝區

我們首先要考慮的問題是, 當列車到達緩衝站點的時候, 什麼樣的車廂需要放入緩衝站點, 什麼樣的車廂可以直接駛出緩衝站點. 第 0 節中有一個 581742963 且 3 為車頭的例子. 一般來說, 標準排列從小到大, 因此此處我們設標準排列為 123456789. 根據標準排列, 只有當進入的第一個車廂是 1 的時候, 才允許車廂直接駛出緩衝站點; 其餘情況一律需要進入緩衝區. 當 1 號車廂駛出緩衝站點後, 接著就是等待 2, 3, ..., 9 號車廂的過程.

接著, 我們需要考慮緩衝區分配車廂的問題. 對於一個空的緩衝區來說, 可以直接放入車廂; 但是如果緩衝區不為空, 那麼就需要考慮某個車廂應該放入哪一個緩衝區比較合適. 不妨考慮將大的車廂放在小的車廂後面. 那麼如果要找到這個小的車廂, 則需要移動小的車廂後面的所有車廂. 只有這樣, 小的車廂才能被取出. 這種方法當然可行, 但是不現實. 如果我們限定每一次只能從緩衝區取出期望車廂, 而不能移動其它車廂, 那麼這個方法就行不通. 因此我們考慮把小的車廂放在大的車廂後面. 在這種情況下, 就可能出現重排失敗的問題, 原因是緩衝區的數量不足. 這種特殊情況我們等一下再討論.

根據標準排列, 我們將期望車廂設為標準排列的第一個元素. 對於期望車廂, 它不是一直不變的, 當期望車廂正確排列之後, 期望車廂就需要進行更改. 一般來說, 當第一節車廂成為標準排列, 但是它已經駛出緩衝區之後, 我們通常將期望車廂改為第二節車廂. 當列車駛入緩衝區的時候, 當遇到期望車廂, 那麼就直接將車廂駛出緩衝區; 否則, 將車廂放入緩衝區. 在放入緩衝區的時候, 優先選擇空的緩衝區; 當不存在空的緩衝區的時候, 根據緩衝區的順序規則搜尋一個車廂號比駛入車廂的編號大的那一個緩衝區放入. 因為我們在選擇空的緩衝區放入的時候, 是從前到後進行選擇, 自然越靠後的緩衝區中存放的車廂編號越大. 是否能夠放入的原則就是小的車廂必須放入大的車廂之後. 每一次有車廂駛出緩衝車站的時候, 都要去緩衝軌道上尋找下一個期望車廂. 當軌道上沒有期望車廂的時候, 需要去緩衝區尋找. 只有所有能找的地方都沒有辦法找到的時候, 才繼續將軌道上的車廂放入緩衝區.

例題 1. 設駛入列車的車廂排列為 581742963, 3 為車頭. 使用堆疊作為緩衝區對列車進行重排.

解 :

我們最開始期望駛入的車廂為 1 號車廂.

現在駛入的車廂為 3 號車廂, 所以我們將 3 號車廂放入第一個緩衝區. 接下來駛入的 6 號車廂將會被放入第二個緩衝區, 因為當存在空閒緩衝區的時候, 我們更習慣於直接放入空閒緩衝區. 駛入 9 號車廂的時候, 將其放入第三個緩衝區. 現在有

2 號車廂駛入的時候, 由於不是期望車廂, 所以仍然要將其放入緩衝區, 但是現在已經沒有空的緩衝區了, 所以要搜尋合適的緩衝區放入. 我們的要求是小的車廂必須放在大的車廂之後, 我們發現第一個緩衝區就已經合適了. 4 號車廂不能放入第一個緩衝區, 所以必須放入第二個緩衝區. 7 號車廂只能放入第三個緩衝區. 當 1 號車廂駛入的時候, 我們期望的車廂來了.

對於期望的車廂, 我們直接將它們駛入終點站中等候, 然後更改期望駛入車廂為 2 號車廂. 然後我們不再直接駛入車廂, 而是在緩衝區中檢查是否存在可以駛入終點站中的車廂. 第一個緩衝區中 2 號車廂是我們期望的車廂, 將其駛入終點站, 並將期望駛入車廂改為 3 號車廂. 第一個緩衝區中的 3 號車廂是我們期望的車廂, 將其駛入終點站之後將期望駛入車廂改為 4 號車廂. 第二個緩衝區中的 4 號車廂是我們的期望車廂, 將其駛入終點站之後把期望駛入車廂改為 5 號車廂. 現在緩衝區中沒有期望車廂的編號, 因此繼續從軌道上駛入車廂.

當前駛入的是 8 號車廂, 將其放入第一個空的緩衝區. 繼續駛入的是 5 號車廂, 為我們期望的車廂, 所以將其直接駛入終點站. 等到期望車廂之後, 我們不斷在緩衝區中找到接下來期望的車廂, 最終列車重排完成.

\blacksquare

剛才我們提到可能因為緩衝區的數量不足導致重排失敗. 這個情況出現在所有緩衝區中都有正在等待重排的車廂, 但是當前駛入車廂的編號比所有緩衝區中最後一個車廂的編號都要大, 從而導致根據大編號車廂必須排在小編號車廂之前的原則, 當前駛入的車廂無法進入緩衝區, 最終就會導致重排失敗.

3. 佇列作為緩衝區

如果將緩衝區換成佇列, 每次就只能從緩衝區頭部取出車廂. 此時, 我們只需要更改一個原則 : 每次將編號大的車廂放入到編號小的車廂之後就可以了.

4. 複雜度分析

列車重排問題中, 如果有 n 個車廂和 k 個緩衝區, 那麼空間複雜度就是 \Theta(k + n). 需要注意的是, 我們不能簡單地認為, 列車重排問題的空間複雜度是 \Theta(n) 或者 O(k). 因為 k 和 n 沒有絕對的關係, 車廂數量可以遠遠大於緩衝區數量, 也可以遠遠少於緩衝區數量.

在最壞的情況下, 除了最後一節期望車廂之外, 剩餘車廂經過一次尋訪全部被放入緩衝區. 這個時候把最後一節車廂駛入終點站之後, 不斷搜尋緩衝區中的車廂, 將這些車廂不斷駛入終點站. 每一次搜尋緩衝區的時候, 最少的搜尋次數為 1 次, 最多 k 次, 總共進行 n - 1 次搜尋. 那麼, 時間複雜度就是 (n - 1)\Theta(k) = \Theta(kn). 在最好的情況下, 每一次都遇到了期望車廂, 但是我們仍然要去緩衝區中進行搜尋, 總共搜尋的次數為 k \cdot n 次, 即空間複雜度仍然為 \Theta(kn). 因此平均情況下, 列車重排問題解決方案的時間複雜度為 \Theta(kn).

當然, 我們可以用一個額外的標記來標識所有緩衝區是否都為空, 來加速最好情況下的時間複雜度, 使得最好情況下的時間複雜度降為 \Theta(n). 但是這不會影響平均情況下的時間複雜度 \Theta(kn).

5. 實作

以堆疊作為緩衝區為例, 我使用了 C++ 實作了列車重排的解決方案 :

#include <stack>
#include <stdexcept>

void train_rearrangement(int train[], const int standard[], int n, int buffer_size) {
    int excepted {};
    std::stack<int> buffer[buffer_size] {};
    int cursor {};
    int rearrangement_cursor {};
    while(excepted < n) {
        if(arr[cursor] == standard[excepted]) {     // 檢查進入的車廂編號是否為我們期望的車廂
            arr[rearrangement_cursor++] = arr[cursor];      // 駛出
            ++excepted;
            ++cursor;
            bool find {};
            do {        // 尋找緩衝區中, 是否存在我們期望的車廂
                find = false;
                for(auto i {0}; i < buffer_size; ++i) {
                    if(buffer[i].empty()) {
                        continue;
                    }
                    if(buffer[i].top() == standard[excepted]) {
                        arr[rearrangement_cursor++] = buffer[i].top();
                        ++excepted;
                        buffer[i].pop();
                        find = true;
                        break;
                    }
                }
            }while(find);
            continue;
        }
        /* 駛入的車廂並不是我們期望的車廂 */
        bool pushed {};
        for(auto i {0}; i < buffer_size; ++i) {
            if(buffer[i].empty()) {     // 如果緩衝區為空, 說明之前緩衝區中的車廂編號都比現在的車廂編號要小
                buffer[i].push(arr[cursor++]);
                pushed = true;
                break;
            }
            if(buffer[i].top() > arr[cursor]) {     // 緩衝區中的車廂編號比現在的車廂要大
                buffer[i].push(arr[cursor++]);
                pushed = true;
                break;
            }
        }
        if(not pushed) {        // 所有緩衝區都不為空, 而且所有緩衝區頂部的車廂編號都比現在的車廂要小, 說明緩衝區數量不足
            throw std::runtime_error("Too few buffers!");
        }
    }
}

如果標準排列是無序的, 那麼上述程式碼就沒有辦法適用, 這是因為我們採用小於或著大於進行比較, 而無序的標準排列只有等於或著不等於的比較. 因此, 此時只有依靠足夠的緩衝區才可以完成重排.