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

  • 15
    いいね
  • 3
    コメント

きっかけ

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

今回扱う問題

一般的に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; // 同じピッチャーに移すことはないからスキップ (例:8のピッチャー -> 8のピッチャー)

                // 中身を移す処理
                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$のとき、幅優先探索と同じになります。
しかし、ビームサーチは完全な探索ではないため、評価関数やビーム幅によって、探索結果が最善ではない場合があります。

方針

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

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

実装

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;

    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; // 同じピッチャーに移すことはないからスキップ (例:8のピッチャー -> 8のピッチャー)

                // 中身を移す処理
                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に状態を追加
                beam.push_back(newState);
            }
        }

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

        // ビーム幅より大きければ評価値が小さい枝を削除
        while (beam.size() > Beam) beam.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 = SolveBeamSearch();

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

    return 0;
}

実行結果

実行は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

幅優先探索の結果とは異なっており、ビームサーチで完全な回答が確実に求まらないことを示しいます。(常に求まらないわけではありません!)
これは、上で述べたとおり評価関数の精度やビーム幅に左右されます。

参考

感想

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