酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月14日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html.

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 2011年7月7日
Advertisements

2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造 2010年7月5日
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
アルゴリズムとデータ構造 2012年7月23日
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
第20章 Flyweight ~同じものを共有して無駄をなくす~
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
情報論理工学 研究室 第6回: リバーシの合法手生成.
アルゴリズムとデータ構造 2012年7月12日
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
第9章 例外処理,パッケージ 9.1 例外処理 9.2 ガーベッジコレクション.
独習JAVA 6.8 コンストラクタの修飾子 6.9 メソッドの修飾子 6.10 ObjectクラスとClassクラス 11月28日(金)
Bridge It と Connections の 必勝法について
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造 2013年7月25日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2005年7月15日
アルゴリズムとプログラミング (Algorithms and Programming)
二分探索木における要素削除 データ構造とプログラミング(10)
アルゴリズムとデータ構造1 2005年7月1日
Bridge It と Connections の 必勝法について
アルゴリズムとデータ構造 2012年7月17日
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2005年7月5日
復習+α JBuilderの使い方を思い出す。 配列とGUI 再帰とマージソート 木と二分木の探索
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
アルゴリズムとデータ構造 2011年7月21日
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
暗号技術 ~JAVAプログラム②~ (6週目)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
数値解析Ⅱ ~五目並べのプログラミング~ C班.
アルゴリズムとデータ構造 2012年6月25日
情報論理工学 研究室 第8回: ミニマックス法.
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
GUI部品とイベント処理の例 マインスィーパもどきの作成 倉敷芸術科学大学 産業科学技術学部 梶浦文夫.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年7月14日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

バックトラック法 (352ページ) 組織的かつ論理的なしらみつぶし解法 単純に全ての場合を試すのではなく、 問題の性質を考慮して無駄な計算を省く 例:n女王問題 盤面に女王を置ける場合の数は   とおり しかし、ひとつの列に女王はひとつしか置けない   とおりまで減らすことができる さらに、ひとつの行に女王はひとつしか置けない

… 1 1行目の女王の位置 2 3 n … … … … 1 2 3 4 n 1 2 3 4 n 2行目の女王の位置 … … … … × × × × × … 1 2 3 4 5 n 3行目の女王の位置 … … × × × × 深さ優先探索により、 すべての場合を調べるのではなく、 解の探索の途中で可能性の無い 枝を刈り払う → 枝刈り 図6.1.3 n女王問題の解の探索(354ページ)

各列には1個しか置けないので、horizontal[x1]=false Java (0, 0) x2 x3 x1 女王が盤面の (x1, y1)に居るとき、 array[x1]=y1 (x2, y2)に 女王は置けない ↓ y1-x1=y2-x2が 成り立たないこと minor[y1-x1]=false y3 y2 (x3, y3)に 女王は置けない ↓ x1+y1=x3+y3が 成り立たないこと major[x1+y1]=false y1

盤面そのものを表す データ構造はない! その列に置けるかどうか 左下がりの対角線上に置けるかどうか 右下がりの対角線上に置けるかどうか 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); 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 "); queen.append('|'); } 盤面そのものを表す データ構造はない! その列に置けるかどうか 左下がりの対角線上に置けるかどうか 右下がりの対角線上に置けるかどうか 1行に1個に1個しか置けない ようにしたデータ構造

すべての場合の盤面を 生成して検査するのでもない (生成後検査法ではない) 解の出力 横4文字・縦2文字で升目1つ 枝刈り 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(); } } 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; 解の出力 横4文字・縦2文字で升目1つ すべての場合の盤面を 生成して検査するのでもない (生成後検査法ではない) 枝刈り queenを置いてみる queenを置かなかったことにする (後戻りするのでバックトラック法) 新しいqueenの位置

n=8の例 8-queen問題の解の一部 public static void main(String[] args) { +---+---+---+---+---+---+---+---+ | | | | | | | | X | | | | | X | | | | | | X | | | | | | | | | | | X | | | | | | | | | | | | X | | | | | X | | | | | | | | | | | | | | X | | | | | | | X | | | | 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); n=8の例 8-queen問題の解の一部

幅優先探索 (365ページ) 深さ優先探索は有用である グラフがメモリ上に存在しないときは 深さ優先探索が使えない 閉路のあるグラフでも深さ優先探索はできる グラフがメモリ上に存在しないときは 深さ優先探索が使えない 頂点を辿ったという印を付けられない 8パズルのように探索のためのグラフを 動的生成するときは、幅優先探索する

この場合の「多い」とはメモリ容量に対して 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 1 7 8 6 5 4 3 2 12手で一巡する閉路が存在する 各状態から作れる状態の数は2から4 全ての状態をメモリに置くには多い この場合の「多い」とはメモリ容量に対して 1 7 8 6 5 4 3 2 図6.2.2と図6.2.3 8パズルのグラフの一部

初期状態 S1 S2 S3 初期状態から生成できる新しい状態S1を求める 次にS1から新しい状態S2を求める ただし余分の状態は取り除く 初期状態へ戻るものも取り除く さらにS2からS3状態を… と順に生成を続ける 解となる状態が生成できたら終了 このときSk状態を生成するためにSk-1とSk-2状態が必要 それ以前の状態はメモリにおく必要はない

パズルの盤の定義(その1) 初期状態と最終状態の生成用 途中の状態の生成用 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; パズルの盤の定義(その1) 初期状態と最終状態の生成用 途中の状態の生成用

パズルの盤の定義(その2) ハッシュテーブルを使うために equals()とhashCode()を実装 結果の表示用 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; } } // 例外処理は割愛 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'); return sb.toString(); }} パズルの盤の定義(その2) ハッシュテーブルを使うために equals()とhashCode()を実装 結果の表示用

パズルの盤の定義(その3) スペースを上に動かす スペースを下に動かす スペースを左に動かす スペースを右に動かす 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){ i = b.hole % size; if(i != 0){ PuzzleBoard new_board = new PuzzleBoard(b, b.hole - 1); if(i != (size - 1)){ PuzzleBoard new_board = new PuzzleBoard(b, b.hole + 1); パズルの盤の定義(その3) スペースを上に動かす スペースを下に動かす スペースを左に動かす スペースを右に動かす

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 step: 25 1 2 0 step: 24 1 2 5 3 4 0 step: 23 3 0 4 step: 22 0 3 4 step: 21 6 3 4 0 7 8 step: 20 1 2 5 6 3 4 7 0 8 step: 19 7 8 0 step: 18 6 3 0 7 8 4 step: 17 6 0 3 step: 16 0 6 3 step: 15 0 2 5 1 6 3 step: 14 2 0 5 step: 13 2 5 0 1 6 3 7 8 4 step: 12 2 5 3 1 6 0 step: 11 1 0 6 step: 10 0 1 6 step: 9 0 5 3 2 1 6 step: 8 5 0 3 step: 7 5 3 0 step: 6 5 3 6 2 1 0 7 8 4 step: 5 2 0 1 step: 4 2 8 1 7 0 4 step: 3 0 7 4 step: 2 0 8 1 2 7 4 step: 1 8 0 1 step: 0 8 7 1 2 0 4 探索は10秒くらい 3 1 7 2 4 8 6 5 初期状態 1 5 4 6 7 8 3 2 最終状態

ゲームの木の探索 先手番 (376ページ) 後手番 先手番 後手番 図 6.3.1 ゲームの木(の部分木だと考えてください) +1 -1 後手番 先手番 後手番 図 6.3.1 ゲームの木(の部分木だと考えてください) ミニマックス法では、バックトラック法により木の葉から評価を決めていく。 葉から根まで自分が勝つ道ができれば、完全に解析できたことになる。

+1 -1 先手番 ゲーム終了の状態に+1・0・-1を与える ゲームの途中では自分に有利なほうの枝を辿る ゲームの木の途中の頂点の値を決定できる 手番が先手・後手に応じて最大・最小を選択 全手読みができれば 先手必勝・引き分け・後手必勝がわかる 全手読みは時間的にも空間的にも困難 全手読みが不可能な場合 その局面での勝ちやすさ(負けやすさ)を求める 先手有利を正の数、後手有利を負の数… その数値を求める関数を評価関数という 先読みする深さを限定して評価する 確率的要素が入るゲームは、ここでは扱わない 完全情報ゲームのみを対象とする 先手勝ち 引き分け 後手勝ち +1 -1 後手番

数字は大きいほど先手に有利、つまり、小さいほど後手に有利 先手はより大きな数値を持つ方向を選ぶ 後手はより小さな数値を持つ方向を選ぶ 4以上 S A B G F E H 2 4 1 3 7 先手番 4以下なら打ち切り 4以下 4 3 3以下 後手番 4以上なら打ち切り 調べるだけ無駄 4 7以上 3 先手番 調べるだけ無駄 後手番 数字は大きいほど先手に有利、つまり、小さいほど後手に有利 先手はより大きな数値を持つ方向を選ぶ 後手はより小さな数値を持つ方向を選ぶ 評価関数の値について 深さ制限つきのミニマックス法 一定の深さまで読んで、最大値もしくは最小値を選ぶ α-β法 一定の深さまで読んで、最大値や最小値に貢献しない枝を刈る