幅優先探索とビームサーチでWater Jug Problemを解いてみた

# きっかけ
先日、友人にある問題を出題され、その答え合わせにプログラムで解いてみようと思ったからです。あと、ビームサーチは書いたことなかったので、練習も兼ねて書いてみました。(今回は探索空間が狭いので、わざわざビームサーチを使う理由はないです。また、評価関数が適当なので近似解しか求まりません)

# 今回扱う問題
一般的に**Water Jug Problem**と呼ばれる問題です。(間違ってたらすみません)
映画「ダイハード3」の中でも似た問題が出てきました。

## 問題概要
> ユウキ君は8dLのピッチャーに入ったヨーグルトスムージーをレイちゃんと半分にする方法を考えています。
> ユウキ君は8dL、5dL、3dL入るピッチャーを使うことができます。
> スムージーを最低何回移し替えればいいでしょうか？

というような問題です。

# 考察
1. 全探索で求まりそう
2. 最小回数を求めるなら幅優先探索が使えそう!

ということで書いていきます。

# 幅優先探索
**幅優先探索**(Breadth-First-Search)は知識なし探索に分類され、**グラフで根に近いノードから順に探索していく**アルゴリズムです。
幅優先探索についての詳しい説明は、他の方の記事を読んだほうがわかりやすいと思うので省略します。

## 方針
全探索です。

1. 訪問済みリストを初期化しておき、幅優先用キューに初期値を追加します。
2. キューの先頭を取り出して訪問済みリストに追加し、考えられる次の状態をキューに追加します。
3. 2の操作をキューが空になるor目的の値になるまでループします。

## 実装
```cpp:WaterJugProblem-BFS.cpp
// include
#include <algorithm>
#include <sstream>
#include <queue>
#include <iostream>
#include <cmath>
#include <string>

using namespace std;

// 数値を文字列に変換する
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

const int Target     = 4; // 目的の値
const int PitcherNum = 3;  // ピッチャーの数
const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値

// 終了条件を満たすか調べる
bool check(int *Pitchers)
{
    REP(i, PitcherNum)
        if (Pitchers[i] == Target) return true;
    return false;
}

// 現在の状態を保持する構造体
struct Status
{
    int p[3];
    int cnt;
    string ret;
};

// 幅優先で解く
Status SolveBFS()
{
    bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）

    // 配列の初期化
    REP(i, PitcherMax[0]+1)
        REP(j, PitcherMax[1]+1)
            REP(k, PitcherMax[2]+1)
                flag[i][j][k] = false;

    queue<Status> bfs; // 幅優先用のキュー

    Status state;
    state.p[0] = PitcherMax[0];
    state.p[1] = 0;
    state.p[2] = 0;
    state.cnt = 0;
    state.ret = toString(state.p[0]) + " " + toString(state.p[1]) + " " + toString(state.p[2]) + "\n";
    bfs.push(state); // 初期状態をキューに追加

    while (!bfs.empty()) // キューが空になるまでループ
    {
        state = bfs.front(); bfs.pop(); // キューの先頭から要素を一つ取り出す
        if (check(state.p)) break; // 終了条件を満たしていれば終わる
        if (flag[state.p[0]][state.p[1]][state.p[2]]) continue; // 訪れたことがあるならスキップ
        else flag[state.p[0]][state.p[1]][state.p[2]] = true; // 訪れたことがないなら、フラグを立てる

        Status newState; // 次の状態
        REP (i, PitcherNum)
        {
            REP (j, PitcherNum)
            {
                if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)

                // 中身を移す処理
                newState.p[i] = max(state.p[i] - (PitcherMax[j] - state.p[j]), 0);
                newState.p[j] = min(state.p[j] + state.p[i], PitcherMax[j]);
                newState.p[3 - i - j] = state.p[3 - i - j];

                // 移動した回数を1増やす
                newState.cnt = state.cnt + 1;

                // ピッチャーの状態遷移をメモする
                newState.ret = state.ret + toString(newState.p[0]) + " " + toString(newState.p[1]) + " " + toString(newState.p[2]) + "\n";

                // ピッチャーの中身が移動していない場合はスキップする
                if (newState.p[i] == state.p[i]) continue;

                // キューに状態を追加
                bfs.push(newState);
            }
        }
    }
    if (check(state.p)) return state;
    else
    {
        state.cnt = -1;
        state.ret = "目的の値になりませんでした";
        return state;
    }
}

int main()
{
    Status result = SolveBFS();

    cout << "目的の値: " << Target << endl;
    cout << "移動回数: " << result.cnt << endl;
    cout << "ピッチャーの状態遷移:" << endl;
    cout << result.ret << endl;

    return 0;
}
```

## 実行結果
実行は[ideone](https://ideone.com/2Wk0wT)で行っています。

```text:実行結果
目的の値: 4
移動回数: 6
ピッチャーの状態遷移:
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
```
多分、結果はあってると思います..(間違っていたら、指摘していただけると助かります。) 

# ビームサーチ
**ビームサーチ**(Beam Search)は知識あり探索に分類され、幅優先探索を行いつつ、**評価値が高いノードを`ビーム幅`個保持し、 `ビーム幅`個よりノードの個数が増えたら評価値が低い枝を切り捨てる**アルゴリズムです。
ビームサーチでは、この`ビーム幅`と`評価値`が重要になってきます。
ビームサーチは探索空間は非常に大きい場合に有効です。
また、ビーム幅$=\inf$のとき、幅優先探索と同じになります。
しかし、ビームサーチは完全な探索ではないため、評価関数やビーム幅によって、探索結果が最善ではない場合があります。

## お詫び（2019/10/31追記・修正）
ビームサーチの実装に誤りがあり，実際は最良優先探索となっていたようです．
参考にされていた方，申し訳有りません．修正したコードを示します．
また，今回指摘してくださった方の記事 "[勝手に幅優先探索と最良優先探索とビーム・サーチでWater Jug Problemを解き直してみた](https://qiita.com/tail-island/items/b873b4890353b50f2eac)" のほうが解説が分かりやすく，実験が丁寧で参考になると思います．

### 方針（ビームサーチとなっている部分は最良優先探索に変更しました）
今回は、探索空間が大して広くないので、最良優先探索を使う利点が殆ど無いです。
また、評価関数は、**今までに動かした回数**と、ピッチャーのなかの**ジュースが目的値の倍数かどうか**など、を元に作成しました。
幅は`10`とします。~~(適当)~~

1. 訪問済みリストを初期化しておき、探索用dequeに初期値を追加します。
2. dequeの先頭を取り出して訪問済みリストに追加し、考えられる次の状態と、その状態の評価値のペアをdequeに追加します。
3. dequeを評価値で昇順ソートします。
4. dequeの要素数が幅より大きければ、末尾を削除していきます。
5. 2~4の操作をキューが空になるor目的の値になるまでループします。

### (最良優先探索の)実装
```cpp:WaterJugProblem-BestFirst.cpp
// include
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cmath>
#include <string>
#include <utility>
#include <deque>

using namespace std;

// 数値を文字列に変換する
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

const int Width      = 10; // 幅
const int Target     = 4; // 目的の値
const int PitcherNum = 3; // ピッチャーの数
const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値

// 終了条件を満たすか調べる
bool check(int *Pitchers)
{
    REP(i, PitcherNum)
        if (Pitchers[i] == Target) return true;
    return false;
}

// 現在の状態を保持する構造体
struct Status
{
    int p[3];
    int cnt;
    string ret;
};

// 評価関数
int Eval(Status state)
{
    int ret = 0;
    ret -= state.cnt;
    for (auto n : state.p)
    {
        if (n % Target == 0) ret += 10;
        ret -= abs(Target - n);
    }
    return ret;
}

// pairの比較(ソート用)
bool comp(pair<int, Status> lhs,  pair<int, Status> rhs)
{
    return lhs.first > rhs.first;
}

// 最良優先探索で解く
Status SolveBestFirstSearch()
{
    bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）

    // 配列の初期化
    REP(i, PitcherMax[0]+1)
        REP(j, PitcherMax[1]+1)
            REP(k, PitcherMax[2]+1)
                flag[i][j][k] = false;

    // 探索用のdeque
    deque<pair<int, Status>> nexts;

    pair<int, Status> state;
    state.second.p[0] = PitcherMax[0];
    state.second.p[1] = 0;
    state.second.p[2] = 0;
    state.second.cnt = 0;
    state.second.ret = toString(state.second.p[0]) + " " + toString(state.second.p[1]) + " " + toString(state.second.p[2]) + "\n";
    state.first = Eval(state.second);

    // 初期状態をdequeに追加
    nexts.push_front(state);

    while (!nexts.empty()) // dequeが空になるまでループ
    {
        state = nexts.front(); nexts.pop_front(); // dequeの先頭から要素を一つ取り出す
        if (check(state.second.p)) break; // 終了条件を満たしていれば終わる
        if (flag[state.second.p[0]][state.second.p[1]][state.second.p[2]]) continue; // 訪れたことがあるならスキップ
        else flag[state.second.p[0]][state.second.p[1]][state.second.p[2]] = true; // 訪れたことがないなら、フラグを立てる

        pair<int, Status> newState; // 次の状態
        REP (i, PitcherNum)
        {
            REP (j, PitcherNum)
            {
                if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)

                // 中身を移す処理
                newState.second.p[i] = max(state.second.p[i] - (PitcherMax[j] - state.second.p[j]), 0);
                newState.second.p[j] = min(state.second.p[j] + state.second.p[i], PitcherMax[j]);
                newState.second.p[3 - i - j] = state.second.p[3 - i - j];

                // 移動した回数を1増やす
                newState.second.cnt = state.second.cnt + 1;

                // ピッチャーの状態遷移をメモする
                newState.second.ret = state.second.ret + toString(newState.second.p[0]) + " " + toString(newState.second.p[1]) + " " + toString(newState.second.p[2]) + "\n";

                // ピッチャーの中身が移動していない場合はスキップする
                if (newState.second.p[i] == state.second.p[i]) continue;

                // 評価値を計算
                newState.first = Eval(newState.second);

                // dequeに状態を追加
                nexts.push_back(newState);
            }
        }

        // 評価値順にソート
        sort(nexts.begin(), nexts.end(), comp);

        // 幅より大きければ評価値が小さい枝を削除
        while (nexts.size() > Width) nexts.pop_back();
    }

    if (check(state.second.p)) return state.second;
    else
    {
        state.second.cnt = -1;
        state.second.ret = "目的の値になりませんでした";
        return state.second;
    }
}

int main()
{
    Status result = SolveBestFirstSearch();

    cout << "目的の値: " << Target << endl;
    cout << "移動回数: " << result.cnt << endl;
    cout << "ピッチャーの状態遷移:" << endl;
    cout << result.ret << endl;

    return 0;
}
```

### 実行結果
実行は~~[ideone](https://ideone.com/pJiz39)~~ [ideone](https://ideone.com/3pHUbb)で行っています。

```text:実行結果
目的の値: 4
移動回数: 7
ピッチャーの状態遷移:
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
```
~~幅優先探索の結果とは異なっており、最良優先探索で完全な回答が確実に求まらないことを示しいます。(常に求まらないわけではありません!)
これは、上で述べたとおり評価関数の精度や幅に左右されます。~~

## （修正済み）ビームサーチの実装
以前のコードとの変更点としては以下のとおりです。
- 現在のイテレーションと次のイテレーション用にキューを2つ使用
- 現在のイテレーションが終了したら次のイテレーション用のキューから評価値が高い状態をBeam幅分取り出しセット

```cpp:WaterJugProblem-Beam.cpp
// include
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cmath>
#include <string>
#include <utility>
#include <deque>

using namespace std;

// 数値を文字列に変換する
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

const int Beam       = 10; // ビーム幅
const int Target     = 4; // 目的の値
const int PitcherNum = 3; // ピッチャーの数
const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値

// 終了条件を満たすか調べる
bool check(int *Pitchers)
{
    REP(i, PitcherNum)
        if (Pitchers[i] == Target) return true;
    return false;
}

// 現在の状態を保持する構造体
struct Status
{
    int p[3];
    int cnt;
    string ret;
};

// 評価関数
int Eval(Status state)
{
    int ret = 0;
    ret -= state.cnt;
    for (auto n : state.p)
    {
        if (n % Target == 0) ret += 10;
        ret -= abs(Target - n);
    }
    return ret;
}

// pairの比較(ソート用)
bool comp(pair<int, Status> lhs,  pair<int, Status> rhs)
{
    return lhs.first > rhs.first;
}

// ビームサーチで解く
Status SolveBeamSearch()
{
    bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）

    // 配列の初期化
    REP(i, PitcherMax[0]+1)
        REP(j, PitcherMax[1]+1)
            REP(k, PitcherMax[2]+1)
                flag[i][j][k] = false;

    // ビームサーチ用のdeque
    deque<pair<int, Status>> beam;

    // 次のイテレーション用のdeque
    deque<pair<int, Status>> nexts;

    pair<int, Status> state;
    state.second.p[0] = PitcherMax[0];
    state.second.p[1] = 0;
    state.second.p[2] = 0;
    state.second.cnt = 0;
    state.second.ret = toString(state.second.p[0]) + " " + toString(state.second.p[1]) + " " + toString(state.second.p[2]) + "\n";
    state.first = Eval(state.second);

    // 初期状態をdequeに追加
    beam.push_front(state);

    while (!beam.empty()) // dequeが空になるまでループ
    {
        state = beam.front(); beam.pop_front(); // dequeの先頭から要素を一つ取り出す
        if (check(state.second.p)) break; // 終了条件を満たしていれば終わる
        if (flag[state.second.p[0]][state.second.p[1]][state.second.p[2]]) continue; // 訪れたことがあるならスキップ
        else flag[state.second.p[0]][state.second.p[1]][state.second.p[2]] = true; // 訪れたことがないなら、フラグを立てる

        pair<int, Status> newState; // 次の状態
        REP (i, PitcherNum)
        {
            REP (j, PitcherNum)
            {
                if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)

                // 中身を移す処理
                newState.second.p[i] = max(state.second.p[i] - (PitcherMax[j] - state.second.p[j]), 0);
                newState.second.p[j] = min(state.second.p[j] + state.second.p[i], PitcherMax[j]);
                newState.second.p[3 - i - j] = state.second.p[3 - i - j];

                // 移動した回数を1増やす
                newState.second.cnt = state.second.cnt + 1;

                // ピッチャーの状態遷移をメモする
                newState.second.ret = state.second.ret + toString(newState.second.p[0]) + " " + toString(newState.second.p[1]) + " " + toString(newState.second.p[2]) + "\n";

                // ピッチャーの中身が移動していない場合はスキップする
                if (newState.second.p[i] == state.second.p[i]) continue;

                // 評価値を計算
                newState.first = Eval(newState.second);

                // 次のイテレーションを管理するキューに状態を追加
                nexts.push_back(newState);
            }
        }

        // dequeが空 = 現在のイテレーションが終了
        if (beam.empty())
        {
          // 評価値順にソート
          sort(nexts.begin(), nexts.end(), comp);

          // 評価値が高いものをビーム幅分キューに追加
          for (int i = 0; i < Beam && !nexts.empty(); ++i)
          {
            beam.push_back(nexts.front());
            nexts.pop_front();
          }
          nexts.clear();
        }
    }

    if (check(state.second.p)) return state.second;
    else
    {
        state.second.cnt = -1;
        state.second.ret = "目的の値になりませんでした";
        return state.second;
    }
}

int main()
{
    Status result = SolveBeamSearch();

    cout << "目的の値: " << Target << endl;
    cout << "移動回数: " << result.cnt << endl;
    cout << "ピッチャーの状態遷移:" << endl;
    cout << result.ret << endl;

    return 0;
}
```
実行は[ideone](https://ideone.com/lRw4vl)で行っています。

```:実行結果
目的の値: 4
移動回数: 6
ピッチャーの状態遷移:
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
```


# 参考
+ [幅優先探索-Wikipedia](https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)
+ [ビームサーチ-Wikipedia(English)](https://en.wikipedia.org/wiki/Beam_search)
+ [迷路で眺める探索アルゴリズム](http://spheresofa.net/blog/?p=1044)
+ [全探索アルゴリズム入門](http://qiita.com/MasayaMizuhara/items/86099ad721a329e1d6cd)
+ [グラム探索ことはじめ - 幅・深さ優先探索 -](http://qiita.com/guicho271828/items/adba26e0772d7063b4c8)
 
# 感想
+ 幅優先の方は簡単に書けました。
+ ビームサーチの実装は初めてで、正直あまり自信がないです。
+ ほかのアルゴリズム(DFSやA*)でも書いて見ようかなと思いました。
+ 春休み中に記事を一本書くという目標を達成できました。~~実はこれが目的とは言えない~~

# 編集履歴
2019/10/31 ビームサーチの実装が誤っているとの指摘を頂いたので修正