数え上げ・探索の手法、再帰

3.1 幅優先探索 (breadth-first search)

横型探索とも言われる。
状態空間において、まず開始状態から一回遷移した状態をすべて調べる。 次に開始状態から二回遷移した状態、さらに三回遷移した状態、... のように同じ深さの状態をまとめて調べ、順次遷移の深さを増して目的状態に達するかどうかを調べていく探索法である。

幅優先探索は一般に展開中の状態のリストを記憶する必要があるため、実行時に多くのメモリが必要となる。

幅優先探索 {
    OpenList, ClosedList をともに空にする
    開始状態 S を OpenList に入れる

    繰り返し {
        OpenList が空ならば、S からゴールに至る経路はない。終了。
        OpenList の先頭を取り出し、OpenList から除く。取り出した状態を A とする。
        A がゴールなら、解が見つかったので出力し終了。
        状態 A でのすべての可能選択肢を求め、それらにより遷移する状態の集合 PA を求める。
        A を ClosedList の最後に追加する。
        PA が空ならば(すなわち A が末端状態なら)、以下をスキップし、次の繰り返しに行く。
        PA の中の各状態 c について {
            c が OpenList にも ClosedList にもなければ、c を OpenList の最後に追加する。
        }
    }
}

3.2 深さ優先探索 (depth-first search)

縦型探索とも言われる。
状態空間において、開始状態からどんどん可能遷移を続け目的状態に達するかどうかを調べていく探索法である。探索が

• 目的状態でない末端状態に来たとき
• 可能な遷移状態をすべて調べたとき

は遷移の一つ前の状態に戻って(バックトラックと言う)探索を続けていく。 開始状態のすべての遷移状態で目的状態が見つからなければ「解なし」であることがわかる。

深さ優先探索は一般に再帰で記述され、実行時に大量のメモリを必要としないという利点がある。

深さ優先探索 {
    再帰探索( 開始状態 )
    すべての状態を調べたが解がなかった場合は解なしで終了。
}

再帰探索( 状態 A ) {
    A がゴールなら、解が見つかったので出力し終了。

    A がゴールでなければ、状態 A でのすべての可能選択肢の集合 M を求める。
    集合 M の各選択肢 m について {
        状態 A から選択肢 m を進めた後の状態 Am へ遷移する。
        再帰探索( Am )
        状態 Am から選択肢 m を進める前の元の状態 A へ戻す。
    }
}

3.3 最良優先探索 (best-first search)

状態 n から目標状態に達するまでの最適順路のコストを予測するヒューリスティックな関数 h(n) ≧ 0 を使用し、まだ調べていない状態から最も h(n) の小さな状態を調べていく探索法である。

未展開状態のリスト、展開済み状態のリストが必要になるため、実行時には大量のメモリが必要となる。

※ ヒューリスティック (heuristic) な関数とは、理論的には保証はないが、経験的・直感的に、あるいは機械学習による調整によって用意されたもっともらしいと思われる関数のこと。

3.4 A*探索 (A* search)

状態 n から目標状態に達するまでの最適順路のコストを予測するヒューリスティックな関数 h(n) だけでなく、開始状態から状態 n に至るまでのコスト関数 g(n) も共に利用する。開始状態から状態 n を経て目標状態に至るまでの最適順路の予測コスト関数 f(n)

f(n) = g(n) + h(n)

を考え、最も f(n) の小さな状態を選んで展開していく探索法である。これを A*探索 (A* search) と言う。

A*探索の効率はヒューリスティック関数の出来次第で、解を見つける場合でも最適解を見つけ出す保証はない。

しかし、真のコスト関数、つまり 状態 n から目標状態に達するまでの最適順路のコスト関数 h*(n) を考えたとき、

すべての状態 n について    h(n)   ≦   h^*(n)

となるようなヒューリスティック関数 h(n) を使った場合には必ず最適解が見つけられる。 この条件を満足するヒューリスティック関数を 許容的 (admissible) であると言う。

4.1 再帰とは

再帰には、直接自身を呼び出す形式の直接再帰と、呼び出し先の別の関数(手続き、メソッドなど)から自身が呼ばれる形式の間接再帰がある。

無条件に自分自身を呼んでしまうと、無限に呼び出しが起こってしまいプログラムが止まらなくなる。無限再帰などと言われる。
※ 実際には、ある程度呼び出しが深くなるとプログラムは異常終了する。

そのため、再帰呼び出しされる関数(手続き、メソッドなど)では再帰を止めるための条件をちゃんと指定する必要がある。

再帰は、比較的新しいプログラミング言語ではほとんどすべてで利用可能である。 引数の渡し方が 値渡し (call by value) のものは問題なく再帰が利用できる。(C言語など)
プログラミング言語によっては引数が 参照渡し (call by reference) されるものもあり、再帰の利用には注意が必要である。

4.2 階乗の計算

自然数 n の階乗 n! は

n! = n * (n - 1) * (n - 2) * ... * 2 * 1

で表される。ここで n! を fact(n) で表すと

fact(n) = n * fact(n - 1)

という式が成立する。 これを基に擬似コードを書くと

関数 fact ( 引数 n ) {
	n * fact(n - 1) を計算し返す
}

となる。しかし、これは再帰の停止条件が指定されていないので上述の無限再帰が発生してしまう。
そこで

fact(1) = 1! = 1

であることを考慮して、これを停止条件にする。

関数 fact ( 引数 n ) {
	もし n が 1 なら、
		1 を返して戻る
	n * fact(n - 1) を計算し返す
}

※
演習1と演習2が独力でできない場合、授業のTeamsの「共有済み」のフォルダ「数え上げ探索再帰」にあるCプログラムのプロトタイプ fact_proto.c またはJavaプログラムのプロトタイプ Fact_proto.java をダウンロード・保存し、サクラエディタなどで変更後、(Javaファイルの場合ファイル名を Fact.java に変更して) 保存し、コンパイル・実行してみなさい。
※

int64_t ii;
uint64_t uu;

.....

ii = ... (何らかの値を代入)

uu = ... (何らかの値を代入)

.....

printf( "ii = %" PRId64 "\n", ii);
printf( "uu = %" PRIu64 "\n", uu);

4.3 フィボナッチ数列の計算

フィボナッチ数列 fibo(n) は

fibo(1) = fibo(2) = 1
n ≧ 3 の時、fibo(n) = fibo(n - 1) + fibo(n - 2)

で表される。

これを基に擬似コードを書くと以下のようになる。

関数 fibo ( 引数 n ) {
	もし n が 1 または 2 なら、
		1 を返して戻る
	fibo(n - 1) + fibo(n - 2) を計算し返す
}

※
独力でできない場合、授業のTeamsの「共有済み」のフォルダ「数え上げ探索再帰」にあるCプログラムのプロトタイプ fibo_proto.c またはJavaプログラムのプロトタイプ Fibo_proto.java をダウンロード・保存し、サクラエディタなどで変更後、(Javaファイルの場合ファイル名を Fibo.java に変更して) 保存し、コンパイル・実行してみなさい。
※

下に、n = 6 で再帰版 fibo を呼び出した時の再帰呼び出しの様子を木構造で示す。

上図からも、n が大きくなると再帰の呼び出し回数が爆発的に増えていくことが予想できる。
実際、上記単純な再帰版の計算では、理論的解析から、関数(メソッド)が下記に比例した回数呼ばれることが知られている。

fibo(n) に対して、
((1 + √5)/2)^{(n - 1)}

(1 + √5)/2 = 1.61803... は 黄金比 (golden ratio) と言われる定数であり、計算量がこの定数のべき乗で表される効率の悪い計算法となる。

4.4 ハノイの塔

ハノイの塔は再帰プログラムでよく例に出されるパズルである。

パズルの開始状態

パズルのゴール状態

この問題は、再帰の考え方を使うときわめてすっきり解ける。解答手順を模式的に表した図を下に示す。

上図では移動を表す矢印が二種類ある。①③にある、細い方の矢印はドーナツ盤の (n - 1) 枚の塊 (山) のマクロ的な移動を表しており、実際の個々のドーナツ盤の移動がどのように構成されるかは気にしていない。一方、②にある、太い方の矢印は実際の一つのドーナツ盤の移動を表している。

ドーナツ盤の数を n とし、ルールを守ってそれらを A から C に移動させる処理を

hanoi( n, A, C )

と書くと決める。解答手順の途中で、

n 枚のうち、上の (n - 1) 枚のドーナツ盤が A から B に移動している状態

が考えられる。この場合、一番下の一枚は移動には関係ないので無視してよい。

「①初期状態」から「②上の (n - 1) 枚のドーナツ盤が A から B に移動している状態」へ移行させる手順は

hanoi( n - 1, A, B )

と表すことができる。

「②上の (n - 1) 枚のドーナツ盤が A から B に移動している状態」では、一番大きいドーナツ盤だけが A に残っている。 これを空の C に移動させる。

「A のドーナツ盤を C に移動させる」

この結果、「③上の (n - 1) 枚のドーナツ盤が A から B に移動し、一番下の1枚が A から C に移動した状態」になる。

この状態から、B に積まれている (n - 1) 枚のドーナツ盤を B から C へ移動させれば、手順は完結する。この処理は

hanoi( n - 1, B, C )

と表すことができる。

以上をまとめて、n 枚のドーナツ盤を A から C に移動させる処理 hanoi( n, A, C ) は

処理 hanoi( n, A, C ) {
	hanoi( n - 1, A, B )
	A のドーナツ盤を C に移動させる
	hanoi( n - 1, B, C )
}

と擬似コードで記述できる。実際には、上の擬似コードの A, B, C に相当する部分が変化するので、移動位置を一般化して以下のような擬似コードになる。

擬似コード(A)

処理 hanoi( n, 移動元, 移動先 ) {
	「移動元」「移動先」以外の「もう一つの棒」を求める
	hanoi( n - 1, 移動元, もう一つの棒 )
	「移動元」のドーナツ盤を「移動先」に移動させる
	hanoi( n - 1, もう一つの棒, 移動先 )
}

なお、上記擬似コードではなく、「もう一つの棒」も hanoi のパラメータとして渡す書き方もできる。その場合は「もう一つの棒」を求める処理はいらなくなるので、以下のような擬似コードになる。

擬似コード(B)

処理 hanoi( n, 移動元, 移動先, もう一つの棒 ) {
	hanoi( n - 1, 移動元, もう一つの棒, 移動先 )
	「移動元」のドーナツ盤を「移動先」に移動させる
	hanoi( n - 1, もう一つの棒, 移動先, 移動元 )
}

4.5 移動制限つきのハノイの塔

ハノイの塔の変種問題として、移動が必ず真ん中の棒 B を介さなければいけないという制限をつけた問題を解く。

この制限により、各ドーナツ板の

は禁止されるので、元の問題より複雑な手順が要求される。
考え方としては、元問題と同様に、n 枚のドーナツ板を上の (n - 1) 枚と一番下の1枚に分けて考えて、再帰的に考えて解く。解答手順は下図のようになる。

なお上図の③⑤を見ると、(n - 1)枚の山のマクロ的な移動は A → C あるいは C → A に限られていることが分かる。これらはマクロ的な移動なので制限されていない。
従って、移動制限つきのハノイの塔では、再帰関数(メソッド)の中での「もう一つの棒」は必ず B になるので、コード上で固定してしまってもよい。