BFS 介紹

大一上學期的時候大家學過遞迴，這學期老師教倒水問題的時候也提過可以用遞迴來解這個問題。
BFS是對這類問題用不一樣的角度來思考，在某些情況下BFS會有比較好的效率；比如說要找最小值。

倒水問題

倒水問題的解法簡單來說是這樣：對於一個狀態，判斷它有沒有達到要求；如果沒有，找出所有可以從這個狀態衍生出的所有狀態，一個個遞迴下去檢查。

用倒水問題的說法來說，就是看現在的水量是不是答案；如果不是的話，對現在的這個水量進行所有倒水的操作（把A倒給B，把B倒給A，把A倒空…等），對所有新形成的水量遞迴下去問相同的問題。

BFS概念

這類問題一開始會有一個初始狀態。第一輪先把所有對初始狀態進行一次操作之後可以形成的狀態找出來檢查；第二輪把所有第一輪的狀態進行一次操作之後（從初始狀態進行兩次）可以形成的狀態找出來檢查。以此類推，一直做到找到答案為止。
如果我們在第N輪找到目標狀態，那要達到目標狀態的最少操作次數就是N。（大家可以想一下為什麼）

而在這個過程中，如果搜尋到了一個以前已經出現過的狀態，那我們可以直接跳過，不用再重複搜尋（這點和遞迴找答案的時候一樣）。

BFS 解倒水問題

初始狀態就是一開始兩個杯子A,B裏面各有多少水。
先檢查現在的水量是不是就是答案

if (A == ans) or (B == ans) :
    min_step = 0

第一輪：對一開始的狀態，窮舉所有可能的操作，對他們一一檢查。

if (A+B == ans) or (A-B == ans) or ... :
    min_step = 1

第二輪：對第一輪的每個狀態，窮舉所有可能的操作，對他們一一檢查。
…
第N輪：對第N-1輪的每個狀態，窮舉所有可能的操作，對他們一一檢查。

if ... or ... or ... :
    min_step = N

實作（C++）

STL有個container叫作queue，我們可以利用他輕鬆的達到目標。
把初始狀態放進queue。
把queue的第一個人拿出來。 看看它符不符合答案

auto x = Q.front();
Q.pop();
if (x.A == target || x.B == target) {
    min_step = x.step;
    break;
}

如果它不符合，對它窮舉所有可能的操作，一個個放進queue。

for all possible y derived from x {
    y.step = x.step + 1;
    Q.push(y);
}

持續做到queue變空為止。如果做到queue變空還是沒有找到答案，那就代表無解。

思考一下這為什麼可以work：因為把東西放進queue的順序是按照step由小到大，所以一旦發現一個step等於K的答案，step小於K的狀態一定都被檢查過了！

所以大概的程式碼可能會長這樣子：

struct S {...}; // 狀態
queue<S> Q;
Q.push(初始狀態);
while (!Q.empty()) {
    S x = Q.front();
    Q.pop();
    if (x已經出現過) continue;
    ... // 把x出現過這件事記起來
    if (x是答案）{
        min_step = x.step;
        break;
    }
    else {
        for (每個可行的操作 op) {
            S y = some_operation(x, op); // y是可以從x衍生出的一個狀態
            ...
            y.step = x.step+1;
            Q.push(y);
        }
    }
}
cout << min_step << endl;

應用

BFS 除了可以用來解倒水問題，也可以用來解走迷宮之類的問題（問最少幾步可以到終點）。
把起點當成初始狀態，終點當成目標狀態。可行的操作就是上下左右移動。
或者也可以反過來做，把終點和起點的角色互換，如果題目改成起點唯一，但終點不只一個（作業是不是跟這個有點像？），這樣會有不小的幫助~