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

きっかけ

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

今回扱う問題

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

問題概要

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

というような問題です。

考察

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

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

幅優先探索

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

方針

全探索です。

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

実装

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で行っています。

実行結果

目的の値: 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を解き直してみた" のほうが解説が分かりやすく，実験が丁寧で参考になると思います．

方針（ビームサーチとなっている部分は最良優先探索に変更しました）

今回は、探索空間が大して広くないので、最良優先探索を使う利点が殆ど無いです。
また、評価関数は、今までに動かした回数と、ピッチャーのなかのジュースが目的値の倍数かどうかなど、を元に作成しました。
幅は10とします。(適当)

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

(最良優先探索の)実装

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 ideoneで行っています。

実行結果

目的の値: 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幅分取り出しセット

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で行っています。

実行結果

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

参考

• 幅優先探索-Wikipedia
• ビームサーチ-Wikipedia(English)
• 迷路で眺める探索アルゴリズム
• 全探索アルゴリズム入門
• グラム探索ことはじめ - 幅・深さ優先探索 -

感想

• 幅優先の方は簡単に書けました。
• ビームサーチの実装は初めてで、正直あまり自信がないです。
• ほかのアルゴリズム(DFSやA*)でも書いて見ようかなと思いました。
• 春休み中に記事を一本書くという目標を達成できました。実はこれが目的とは言えない

編集履歴

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