アルゴリズムとデータ構造

アルゴリズムとデータ構造
2012年7月23日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html
バックトラック法
（３５２ページ）
•  組織的かつ論理的なしらみつぶし解法
•  単純に全ての場合を試すのではなく、
問題の性質を考慮して無駄な計算を省く
•  例：ｎ女王問題
C
–  盤面に女王を置ける場合の数は とおり
n2 n
–  しかし、ひとつの列に女王はひとつしか置けない
n
•  n
とおりまで減らすことができる
–  さらに、ひとつの行に女王はひとつしか置けない
!
•  n
とおりまで減らすことができる
2
１
２
１行目の女王の位置
３
…
１
２
×
×
４ … ｎ
３
…
１
２
３
４
×
×
×
×
…
５ … ｎ
…
…
１
２
３
×
×
×
…
ｎ
…
４ … ｎ ２行目の女王の位置
…
…
３行目の女王の位置
深さ優先探索により、
すべての場合を調べるのではなく、
解の探索の途中で可能性の無い
枝を刈り払う → 枝刈り
図６.１.３ ｎ女王問題の解の探索（３５４ページ）
3
Ｊａｖａ
（０, ０）
各列には１個しか置けないので、ｈｏｒｉｚｏｎｔａｌ［ｘ１］＝ｆａｌｓｅ
ｘ２
ｘ１
ｘ３
女王が盤面の
（ｘ１, ｙ１）に居るとき、
ａｒｒａｙ［ｘ１］＝ｙ１
（ｘ２, ｙ２）に
女王は置けない
↓
ｙ３
ｙ１‐ｘ１＝ｙ２‐ｘ２が
成り立たないこと
ｙ２ ｍｉｎｏｒ［ｙ１‐ｘ１］＝ｆａｌｓｅ
（ｘ３, ｙ３）に
女王は置けない
↓
ｙ１ ｘ１＋ｙ１＝ｘ３＋ｙ３が
成り立たないこと
ｍａｊｏｒ［ｘ１＋ｙ１］＝ｆａｌｓｅ
4
public class BackTrack { private final boolean[] horizontal; 盤面そのものを表す
private final boolean[] major; 特別なデータ構造はない！
private final boolean[] minor; private final int[] array; private final StringBuffer hr = new StringBuffer(); private final StringBuffer queen = new StringBuffer(); public BackTrack(int n){ その列に置けるかどうか
horizontal = new boolean[n]; major = new boolean[2*n - 1]; 左下がりの対角線上に置けるかどうか
minor = new boolean[2*n - 1]; array = new int[n]; 右下がりの対角線上に置けるかどうか
Arrays.fill(horizontal, true); Arrays.fill(major, true); 1行に1個しか置けない
Arrays.fill(minor, true); ようにしたデータ構造
for(int i = 0; i < n; i++) hr.append("+---"); hr.append('+'); for(int j = 0; j < n - 1; j++) queen.append("| "); queen.append("| X "); for(int j = 0; j < n - 1; j++) queen.append("| "); queen.append('|'); } } 5
private void backtrack(int level){ if(level >= horizontal.length){ 解の出力
for(int x: array){ 横４文字・縦２文字で升目１つ
System.out.println(hr); System.out.append(queen, 4*x, 4*x + 4*array.length + 1); System.out.println(); すべての場合の盤面を
} System.out.println(hr); 生成し検査するのでもない
} else { （生成後検査法ではない）
int row_a = level; int row_i = level + horizontal.length - 1; for(int i = 0; i < horizontal.length; i++){ if(horizontal[i] && major[row_a + i] && minor[row_i - i]){ horizontal[i] = false; 枝刈り
major[row_a + i] = false; minor[row_i - i] = false; ｑｕｅｅｎを置いてみる
array[row_a] = i; backtrack(level + 1); horizontal[i] = true; major[row_a + i] = true; ｑｕｅｅｎを置かなかったことにする
minor[row_i - i] = true; （後戻りするのでバックトラック法）
} } } 新しいｑｕｅｅｎの位置
} 6
public static void main(String[] args) { for(String a: args){ int n; try { n = Integer.parseInt(a); }catch(IllegalArgumentException e){ continue; } new BackTrack(n).backtrack(0); } } ｎ＝８の例
８-ｑｕｅｅｎ問題の解の一部
+---+---+---+---+---+---+---+---+ | | | | | | | | X | +---+---+---+---+---+---+---+---+ | | | | X | | | | | +---+---+---+---+---+---+---+---+ | X | | | | | | | | +---+---+---+---+---+---+---+---+ | | | X | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | X | | | +---+---+---+---+---+---+---+---+ | | X | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | X | | +---+---+---+---+---+---+---+---+ | | | | | X | | | | +---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+ | | | | | | X | | | +---+---+---+---+---+---+---+---+ | | | X | | | | | | +---+---+---+---+---+---+---+---+ | X | | | | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | | X | +---+---+---+---+---+---+---+---+ | | | | | X | | | | +---+---+---+---+---+---+---+---+ | | X | | | | | | | +---+---+---+---+---+---+---+---+ | | | | X | | | | | +---+---+---+---+---+---+---+---+ | | | | | | | X | | +---+---+---+---+---+---+---+---+ 7
幅優先探索
（３６５ページ）
•  深さ優先探索は有用である
–  閉路のあるグラフでも深さ優先探索はできる
•  グラフがメモリ上に存在しないときは
深さ優先探索が使えない
–  頂点を辿ったという印を付けられない
•  ８パズルのように探索のためのグラフを
動的生成するときは、幅優先探索する
8
1 2 3
4 5 6
7 8
1 2 3
4 5 6
7
8
1 2 3
4
6
7 5 8
1 2 3
4 5
7 8 6
1 2 3
4 8 5
7 6
1 2 3
4 6 8
7 5
1 2 3
4 6 8
7
5
1 2 3
4
5
7 8 6
1 2 3
4 8 5
7
6
1 2 3
4 6
7 5 8
1 2 3
4
8
7 6 5
1 2 3
4 8
7 6 5
• １２手で一巡する閉路が存在する
• 各状態から作れる状態の数は２から４
• 全ての状態をメモリに置くには多い
• この場合の「多い」とはメモリ容量に対して
図６.２.２と図６.２.３ ８パズルのグラフの一部
9
初期状態
Ｓ１
Ｓ２
Ｓ３
• 初期状態から生成できる新しい状態Ｓ１を求める
• 次にＳ１から新しい状態Ｓ２を求める
• ただし余分の状態は取り除く
• 初期状態へ戻るものも取り除く
• さらにＳ２からＳ３状態を… と順に生成を続ける
• 解となる状態が生成できたら終了
• このときＳｋ状態を生成するためにＳｋ-１とＳｋ-２状態が必要
• それ以前の状態はメモリにおく必要はない
10
public class PuzzleBoard { private final int[] board; パズルの盤の定義（その１）
private int hole = -1; private static int size; private final PuzzleBoard parent; public PuzzleBoard(int[] new_board){ 初期状態と最終状態の生成用
if(size == 0){ size = (int)Math.sqrt((double)new_board.length); } // 例外処理は割愛 this.board = new_board; for(int i = 0; i < new_board.length; i++){ if(new_board[i] == 0){ hole = i; } } // 例外処理は割愛 this.parent = null; } private PuzzleBoard(PuzzleBoard current, int new_hole){ 途中の状態の生成用
this.board = current.board.clone(); this.board[current.hole] = this.board[new_hole]; this.board[new_hole] = 0; this.hole = new_hole; this.parent = current; } } 11
public boolean equals(Object obj) { PuzzleBoard in = (PuzzleBoard)obj; パズルの盤の定義（その２）
int[] array = in.board; for(int i = 0; i < this.board.length; i++){ if(array[i] != this.board[i]){ ハッシュテーブルを使うために
return false; equals()とhashCode()を実装
} } // 例外処理は割愛 return true; } public int hashCode() { return board[0] * board[1] + this.hole; // 実行時間に大きく影響する } public PuzzleBoard getParent() { return parent; } public String toString(){ 結果の表示用
StringBuffer sb = new StringBuffer(); int k = 0; for(int i = 0; i < size; i++){ for(int j = 0; j < size; j++){ sb.append(this.board[k++]).append(' '); } sb.append('\n'); } sb.append('\n'); 12
return sb.toString(); }} public static void generate(Collection<PuzzleBoard> from, Collection<PuzzleBoard> to,
Collection<PuzzleBoard> other){
for(PuzzleBoard b: from){
パズルの盤の定義（その３）
int i = b.hole - size;
スペースを上に動かす
if(0 <= i){
PuzzleBoard new_board = new PuzzleBoard(b, i);
if(!from.contains(new_board)&&!to.contains(new_board)&&!other.contains(new_board))
to.add(new_board);
}
i = b.hole + size;
スペースを下に動かす
if(i < b.board.length){
PuzzleBoard new_board = new PuzzleBoard(b, i);
if(!from.contains(new_board)&&!to.contains(new_board)&&!other.contains(new_board))
to.add(new_board);
}
i = b.hole % size;
スペースを左に動かす
if(i != 0){
PuzzleBoard new_board = new PuzzleBoard(b, b.hole - 1);
if(!from.contains(new_board)&&!to.contains(new_board)&&!other.contains(new_board))
to.add(new_board);
}
スペースを右に動かす
if(i != (size - 1)){
PuzzleBoard new_board = new PuzzleBoard(b, b.hole + 1);
if(!from.contains(new_board)&&!to.contains(new_board)&&!other.contains(new_board))
to.add(new_board);
}
}
}
public class Puzzle {
private static int[] initial_state = {5,3,6, 8,7,1, 2,0,4};
private static int[] final_state = {0,1,2, 3,4,5, 6,7,8};
private static PuzzleBoard initial_board = new PuzzleBoard(initial_state);
private static PuzzleBoard final_board = new PuzzleBoard(final_state);
public static void main(String[] args) {
HashSet<PuzzleBoard> set1 = new HashSet<PuzzleBoard>();
HashSet<PuzzleBoard> set2 = new HashSet<PuzzleBoard>();
HashSet<PuzzleBoard> set3 = new HashSet<PuzzleBoard>();
HashSet<PuzzleBoard>[] aspect = new HashSet[]{set1, set2, set3}; // from, to, other
aspect[1].add(initial_board); // 初期状態
int step;
for(step = 1; !aspect[1].contains(final_board); step++){ // 最終状態に到達するまで探索
HashSet<PuzzleBoard> tmp = aspect[0];
aspect[0] = aspect[1]; aspect[1] = aspect[2]; aspect[2] = tmp;
aspect[1].clear();
PuzzleBoard.generate(aspect[0], aspect[1], aspect[2]);
System.out.print(step + ": ");
System.out.println(aspect[1].size());
}
aspect[2].clear(); // ここから結果の表示
aspect[2].add(final_board); // 最終状態だけからなるコレクション
aspect[1].retainAll(aspect[2]); // 最終局面で最終状態だけ残す。
for(PuzzleBoard board: aspect[1]){
for(PuzzleBoard current = board; current != null; current = current.getParent()){
System.out.println("step: " + --step);
System.out.print(current.toString());
}}}}
探索は１０秒くらい
５ ３ ６
８ ７ １
２
４
初期状態
１ ２
３ ４ ５
６ ７ ８
最終状態
1: 3 2: 5 3: 10 4: 14 5: 28 6: 42 7: 80 8: 108 9: 202 10: 278 11: 524 12: 726 13: 1348 14: 1804 15: 3283 16: 4193 17: 7322 18: 8596 19: 13930 20: 14713 21: 21721 22: 19827 23: 25132 24: 18197 25: 18978 26: 9929 27: 7359 step: 27 0 1 2 3 4 5 6 7 8 step: 26 1 0 2 3 4 5 6 7 8 step: 25 1 2 0 3 4 5 6 7 8 step: 24 1 2 5 3 4 0 6 7 8 step: 23 1 2 5 3 0 4 6 7 8 step: 22 1 2 5 0 3 4 6 7 8 step: 21 1 2 5 6 3 4 0 7 8 step: 20 1 2 5 6 3 4 7 0 8 step: 19 1 2 5 6 3 4 7 8 0 step: 18 1 2 5 6 3 0 7 8 4 step: 17 1 2 5 6 0 3 7 8 4 step: 16 1 2 5 0 6 3 7 8 4 step: 15 0 2 5 1 6 3 7 8 4 step: 14 2 0 5 1 6 3 7 8 4 step: 13 2 5 0 1 6 3 7 8 4 step: 12 2 5 3 1 6 0 7 8 4 step: 11 2 5 3 1 0 6 7 8 4 step: 10 2 5 3 0 1 6 7 8 4 step: 9 0 5 3 2 1 6 7 8 4 step: 8 5 0 3 2 1 6 7 8 4 step: 7 5 3 0 2 1 6 7 8 4 step: 6 5 3 6 2 1 0 7 8 4 step: 5 5 3 6 2 0 1 7 8 4 step: 4 5 3 6 2 8 1 7 0 4 step: 3 5 3 6 2 8 1 0 7 4 step: 2 5 3 6 0 8 1 2 7 4 step: 1 5 3 6 8 0 1 2 7 4 step: 0 5 3 6 8 7 1 2 0 4 15
先手番
ゲームの木の探索
+1
（３７６ページ）
後手番
-1
+1
-1
-1
先手番
-1
+1
-1
+1
-1
+1
後手番
+1
+1
+1
図 ６.３.１ ゲームの木（の部分木だと考えてください）
ミニマックス法では、バックトラック法により木の葉から評価を決めていく。
葉から根まで自分が勝つ道ができれば、完全に解析できたことになる。
16
+1 先手番
0
-1
先
手
勝
引
分
後
手
勝
+1
-1 後手番
+1
0
• ゲーム終了の状態に＋１・０・‐１を与える
• ゲームの途中では自分に有利なほうの枝を辿る
• ゲームの木の途中の頂点の値を決定できる
• 手番が先手・後手に応じて最大・最小を選択
• 全手読みができれば
• 先手必勝・引き分け・後手必勝がわかる
• 全手読みは時間的にも空間的にも困難
• 全手読みが不可能な場合
• その局面での勝ちやすさ（負けやすさ）を求める
• 先手有利を正の数、後手有利を負の数…
• その数値を求める関数を評価関数という
• 先読みする深さを限定して評価する
• 確率的要素が入るゲームは、ここでは扱わない
• 完全情報ゲームのみを対象とする
-1
17
４以上 S
先手番
４以下なら打ち切り
４以下 A ４
４以上なら打ち切り
３以下 B ３
E ４
G ３
F ７以上
後手番
調べるだけ無駄
H
先手番
調べるだけ無駄
2
4
1
3
7
1
2
3
後手番
• 数字は大きいほど先手に有利、つまり、小さいほど後手に有利
• 先手はより大きな数値を持つ方向を選ぶ
• 後手はより小さな数値を持つ方向を選ぶ
• 評価関数の値について
• 深さ制限つきのミニマックス法
• 一定の深さまで読んで、最大値もしくは最小値を選ぶ
• α-β法
• 一定の深さまで読んで、最大値や最小値に貢献しない枝を刈る
18