パズル問題解法のアルゴリズム講座
実践編
分割統治
１．分割統治の考え
与えられた問題をいつくかの小問題に分割し、その一つ一つについて自分を再帰的に呼び出して解を求め、それらの解を結合(統治)することにより全体の解を求めます。先ほどの階乗を求める
アルゴリズムも「分割統治」の例と言えそうです。
| Ｎの階乗を求めるには | (問題) |
| Ｎの値(これは自明)とＮ-1の階乗を求める問題に分割する | (分割) |
| Ｎ-1の階乗の解を自分を再帰的に呼び出して求める | (再帰) |
| Ｎの値とＮ-1の階乗の値をかけ合わせて全体の解を得る。 | (統治) |
２．分割統治の適用制限
幾つくかの小問題に分割出来なければ「分割統治」は使えません。さらに、自分とサイズが小さいだけの同種の問題に分割する必要があります。解かりやすい
有名な例では、「ハノイの塔」や「クイックソート」があります。
３．「ハノイの塔」
ここでは例題として「ハノイの塔」に挑戦してみます。
３本の棒が立っています。ある棒にはｎ枚の
ドーナツ型円盤が差し込んであります。
この円盤を１枚ずつ移動してｎ枚総てを他の棒に
移して下さい。ただし、小さい円盤の上に大きい
円盤を置いてはいけません。
この問題を「分割統治」で分析するとこうなります。
| ｎ-1枚を目標外の棒に移し、残り１枚は目標の棒に移す。 | (n-1の問題) |
| そして、先ほどのｎ-1枚を目標の棒に移す。 | (n-1の問題) |
| 尚、ｎ-1枚の移動方法は自分を再帰的に呼び出して求める | (再帰) |
|
Ｃ言語ソースリスト
Javaアプレットの実行 |
/* 1枚の円盤をaからbに移動するサブルーチン */
void action(int a, int b) {
省略
}
/* n枚の円盤をaからbに移動する */
void puzzle(int n, int a, int b) {
int c = 3 - a - b; /* 目標外の棒 */
if (n == 1) action(a,b);
else {
puzzle(n-1,a,c); /* n-1の問題 */
action(a,b);
puzzle(n-1,c,b); /* n-1の問題 */
}
}