ホームページへ戻る
第３章: 反復深化今度はこの問題を解いてみましょう。
この問題はどういうことかというと、バケツに半分の水をくみあげるなんてことは許されません。たとえば8リットルのバケツに8リットルの水をくみ、そのなかから5リットルぶんの水を5リットルのバケツに移せば3リットル残ります。これで3リットルの水を作れたことになります。こんなことをいろいろやって1リットルの水を作りなさい、ということです。 まず、1回の動作となるものには、どんなものがあるかを考えます。
あとはこれをどういう順序で組み合わせていくかということですが、困ったことに「動作回数」が何回なのか不明です。 例えば、１の動作と５の動作を交互に無限に繰り返すような探索ルートが存在します。 この問題点を解決するために、探索の深さに制限を付けてやります。例えば5回目の動作で解が見つからなかったあきらめるといった終着点を定めます。 ではその制限回数をいくつに設定すればよいのか。それは、最初は1回、それで解が見つからなければ2回、それで解が見つからなければ3回と解が見つかるまで探索の深さを少しずつ大きくして探索を繰り返します。これを「反復深化」といいます。 尚、反復深化は同じ探索を何度も繰り返すので、探索時間が長くなるという弱点があります。
ホームページへ戻る |
List.3-1 例題４: バケツ問題を反復深化で解く
int DEPTH; // 探索の深さ制限値
// 解答手順を表示する
BOOL Show(int depth, int a, int b)
{
printf("%d回目: 8L= %d 5L= %d\n", depth, a, b);
return TRUE;
}
// バケツ問題を解く為の再帰関数
BOOL Bucket(int depth, int a, int b)
{
// 探索が深さ制限に達したら解かどうか調べる
if (depth == DEPTH) {
if (a==1 || b==1) return Show(depth, a, b); // 解発見
} else {
//--------------------------
// 次の手を総て試してみる
//--------------------------
// 1. 8リットルのバケツいっぱいに川からくむ
if (Bucket(depth+1, 8, b)) return Show(depth, a, b);
// 2. 5リットルのバケツいっぱいに川からくむ
if (Bucket(depth+1, a, 5)) return Show(depth, a, b);
// 3. 8リットルのバケツから5リットルバケツに移す
if (a + b <= 5) {
// 全部移せる場合
if (Bucket(depth+1, 0, a+b)) return Show(depth, a, b);
} else {
// 5リットルバケツいっぱいになるまで移す
if (Bucket(depth+1, a+b-5, 5)) return Show(depth, a, b);
}
// 4. 5リットルのバケツから8リットルバケツに移す
if (a + b <= 8) {
// 全部移せる場合
if (Bucket(depth+1, a+b, 0)) return Show(depth, a, b);
} else {
// 8リットルバケツいっぱいになるまで移す
if (Bucket(depth+1, 8, a+b-8)) return Show(depth, a, b);
}
// 5. 8リットルのバケツの水を全部川に捨てる
if (Bucket(depth+1, 0, b)) return Show(depth, a, b);
// 6. 5リットルのバケツの水を全部川に捨てる
if (Bucket(depth+1, a, 0)) return Show(depth, a, b);
}
return FALSE;
}
int main(void)
{
// 深さ制限を徐々に大きくしていく(解が見つかるまで)
for (DEPTH=1; ; DEPTH++) {
if (Bucket(0, 0, 0) == TRUE) break;
}
return 0;
}
|