明解 Javaによるアルゴリズムとデータ構造 5_再帰的アルゴリズム

5-1 再帰の基本

メソッド内で自分を呼びだす

• 階乗
• ユークリッドの互除法
• ハノイの塔

5-2 再帰アルゴリズムの解析

• 解析
  • トップダウン
  • ボトムダウン
• 真に再帰的
  • メソッド内で自身を複数回呼び出すもの
  • 挙動が複雑
• 非再帰への書き換え
  • 末尾再帰は容易 - http://d.hatena.ne.jp/yaneurao/20051008
  • スタックを用いて過着換えることが出来る場合もあるが、一般に可能とは言い切れない

5-3 ハノイの塔

非再帰への書き下し解答があんまりしっくりこないので、あとで振り返る

5-4 8王妃問題

8x8チェス盤上に、互いに取れないように合計8クイーンを配置する問題

クイーンは縦横斜めに移動できる(飛車と角の動きを併せ持つ感じ)

列ごとに1王妃配置する場合の全配置パターン書き下しアルゴ。
なんてことない再帰なんだけど、すぐには挙動読み取れんかった。

• 分岐 branching
• 分割統治法 devide and conquer

class QueenB {
	static int[] pos = new int[8];
	
	static void print() {
		for (int i = 0; i < 8; i++) {
			System.out.printf("%2d", pos[i]);
		}
		System.out.println();
	}
	
	/**
	 * 女王のいる行数: j=0 からスタート
	 * 
	 * 女王j=0  で固定したまま列数をインクリメントして、潜る。
	 * 列i=7  まで来たら、結果を出力
	 * 列i=7 のまま 女王j++ -> j=7 まできたら、列i=7のセットは終わり。i=6にpopしてくる。
	 * 
	 * 列i=6における、j=0が完了し、j++ -> j=7 まできたら、列i=6のセットは終わり。i=5にpopしてくる。
	 * 列i=5における、j=0が完了し、j++ -> j=7 まできたら、列i=5のセットは終わり。i=4にpopしてくる。
	 * ：
	 * ：
	 * ：
	 * 列i=1における、j=0が完了し、j++ -> j=7 まできたら、列i=1のセットは終わり。done!
	 * 
	 * @param i　王妃配置対象の列
	 */
	static void set(int i) { // i は
		for (int j = 0; j < 8; j++) { // j は女王を配置する行数
			pos[i] = j;
			if (i == 7) {
				print();
			} else {
				set(i+1); // 考慮する対象列をインクリメント
			}
		}
	}
	
	public static void main(String[] args) {
		set(0);
	}
}

以下、挙動のメモ。

i=0 j=0から始まる
	1 0
		2 0
			3 0
				4 0
					// set(5)
					5 0
						// set(6)
						6 0
							// set(7)
							7 0	print
							
							7 1	print
							7 2	print
							7 3	print
							7 4	print
							7 5	print
							7 6	print
							7 7	print
						6 1	
							// set(7)
							7 0	print
							
							7 1	print
							7 2	print
							7 3	print
							7 4	print
							7 5	print
							7 6	print
							7 7	print
						6 2
							// set(7)
							7 0	print
							
							7 1	print
							7 2	print
							7 3	print
							7 4	print
							7 5	print
							7 6	print
							7 7	print
						6 3
						6 4
						6 5
						6 6
						6 7
					5 1
					：
					：
					：

8王妃問題のソルバー(解を盤面表示する)。 なお、このソルバーは

• 限定 bounding
• 分枝限定法 branching and bounding method

を用いていることに留意。

class EightQueen {
	static boolean[] flag_a = new boolean[8];
	static boolean[] flag_b = new boolean[15];
	static boolean[] flag_c = new boolean[15];
	static int[] pos = new int[8];

	static void print() {
		String[] board = new String[8];
		for (int j = 0; j < 8; j++) { // j行
			board[j] = "";
			for (int i = 0; i < 8; i++) { // i列
				board[j] += (pos[i] == j) ? "■" : "□";
			}
			System.out.println(board[j]);
		}
		System.out.println();
	}

	static void set(int i) {
		for (int j = 0; j < 8; j++) {
			if (flag_a[j] == false && flag_b[i + j] == false
					&& flag_c[i - j + 7] == false) {
				pos[i] = j;
				if (i == 7) {
					print();
				} else {
					flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
					set(i + 1);
					flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
				}
			}
		}
	}

	public static void main(String[] args) {
		set(0);
	}
}

上記ソルバーを走らせると、以下の様な盤が92面出力される。

■□□□□□□□
□□□□□□■□
□□□□■□□□
□□□□□□□■
□■□□□□□□
□□□■□□□□
□□□□□■□□
□□■□□□□□

■□□□□□□□
□□□□□□■□
□□□■□□□□
□□□□□■□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
□□■□□□□□

■□□□□□□□
□□□□□■□□
□□□□□□□■
□□■□□□□□
□□□□□□■□
□□□■□□□□
□■□□□□□□
□□□□■□□□

非再帰化、ちょっと考え中。

明解 Javaによるアルゴリズムとデータ構造