PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

いおりおとじま
6 years ago
Views:

1 幅優先探索アルゴリズム復習 Javaでの実装深さ優先探索復習 Javaでの実装 1

2 探索アルゴリズムの一覧問題を解決するための探索幅優先探索深さ優先探索深さ制限探索均一コスト探索反復深化法欲張り探索山登り法最良優先探索 2

3 Breadth-first search ( 幅優先探索 ) 探索アルゴリズムはノードやリンクからなる階層的なツリー構造で構成された状態空間を探索するアルゴリズムです幅優先探索アルゴリズムは根ノード (Root node) から隣接している全てのノードを順番に探索していきこれを繰り返すことでゴールノードをみつけますゴールノードが見つかるかすべてのノードが探索されたら探索は終了ですつまりある階層をすべて調べそれが終わるとひとつ深い階層をすべて調べることを繰り返します横型探索ともいいますアルゴリズムの流れ : 1. キューを作成しスタートノードを加える. 2. ループ : - もしキューが空なら探索失敗として探索を終了する - 先頭のノードを開きキューから取り除く - もし開いたノードがゴールならそれを解決策として探索を終了する. - 開いたノードの子ノードをキューの後ろに追加する 3

4 例 : 1-> 2->3->4->5->6 -> 4

5 子ノードを最後に追加する FIFO 型 (First In First Out) のデータ構造キューが実装に用いられる 5

6 6

7 擬似コード ( 幅優先探索 ) ArrayList queue = new ArrayLsit() ; 1 queue.add(initialnode) ; 2 while (queue.size()> 0) { 3 SearchNode testnode = (SearchNode)queue.firstElement() ; queue.remove(0) ; 3.1 if (testnode.state.equals(goalstate)) return testnode ;// ゴールを発見 3.2 if (!testnode.expanded) { testnode.expand(queue,searchnode.last); return null ;

8 public void breadthfirst() { ArrayList<Node> open = new ArrayList<Node>(); open.add(start); ArrayList<Node> closed = new ArrayList<Node>(); boolean success = false; int step = 0; g.setcolor(color.red); while (true) { System.out.println("STEP:" + (step++)); System.out.println("OPEN:" + open.tostring()); System.out.println("closed:" + closed.tostring()); if (open.size() == 0) { success = false; break; else { Node node = open.get(0); open.remove(0); if (node == goal) { success = true; break; else { ArrayList<Node> children = node.getchildren(); closed.add(node); for (int i = 0; i < children.size(); i++) { Node m = children.get(i); if (!open.contains(m) &&!closed.contains(m)) { num++; m.setpointer(node); if (m == goal) { open.add(0, m); node.gethm().get(m).draw(g, num); sleep(); break; else { open.add(m); node.gethm().get(m).draw(g, num); sleep(); if (success) { String result = printsolution(goal, ""); showdaialog(result); reset.setvisible(true); else { String result = " 探索失敗 "; showdaialog(result); reset.setvisible(true); 8

9 講義内の課題なぜ 2 つの ArrayList(open, closed) を使用するのか説明しなさい : Figure 1 Figure 1 において, open に保存されているノードを書きなさい [ ] Closed に保存されているノードを書きなさい [ ] 9

10 Depth-first search( 深さ優先探索 ) 深さ優先探索アルゴリズムはルートノード木の最初のノード (Root node) からゴールノードが見つかるか葉 ( 子の無いノード Leaf node) に行き着くまで深く掘り下げて探索を行いますもしゴールノードが見つからなかったら引き返し次のまだ通っていないノードから葉ノードに到達するまで探しますつまり深く進んでいき行き止まったら引き返してまた深く進みながらゴール目指します縦型探索ともいうアルゴリズムの流れ : 1. キューを作成しスタートノードを加える. 2. ループ : - もしキューが空なら探索失敗として探索を終了する - 先頭のノードを開きキューから取り除く - もし開いたノードがゴールならそれを解決策として探索を終了する. - 開いたノードの子ノードをキューの先頭に追加する 10

11 例 : 11

12 子ノードを先頭に追加する LIFO 型 (Last In First Out) のデータ構造キューが実装に用いられる 12

13 13

14 擬似コード ( 深さ優先探索 ) ArrayList queue = new ArrayLsit() ; 1 queue.add(initialnode) ; 2 while (queue.size()> 0) { 3 SearchNode testnode = (SearchNode)queue.firstElement() ; queue.remove(0) ; 3.1 if (testnode.state.equals(goalstate)) return testnode ;// ゴールを発見 3.2 if (!testnode.expanded) { testnode.expand(queue,searchnode.front); return null ;

15 public void breadthfirst() { ArrayList<Node> open = new ArrayList<Node>(); open.add(start); ArrayList<Node> closed = new ArrayList<Node>(); boolean success = false; int step = 0; g.setcolor(color.red); while (true) { System.out.println("STEP:" + (step++)); System.out.println("OPEN:" + open.tostring()); System.out.println("closed:" + closed.tostring()); if (open.size() == 0) { success = false; break; else { Node node = open.get(0); open.remove(0); if (node == goal) { success = true; break; else { ArrayList<Node> children = node.getchildren(); closed.add(node); for (int i = 0; i < children.size(); i++) { Node m = children.get(i); if (!open.contains(m) &&!closed.contains(m)) { num++; m.setpointer(node); if (m == goal) { open.add(0, m); node.gethm().get(m).draw(g, num); sleep(); break; else { open.add(m); node.gethm().get(m).draw(g, num); sleep(); if (success) { String result = printsolution(goal, ""); showdaialog(result); reset.setvisible(true); else { String result = " 探索失敗 "; showdaialog(result); reset.setvisible(true); 赤文字が子ノードを調べて ArrayListに追加している部分 15 どう変更すべきか?

16 講義内の課題 1. breathfirst() メソッドを理解する 2. SearchingApplet.java を実行する 3. breathfirst() メソッドと depthfirst() で異なる点を書く 4. 参考サイト 16

17 宿題プログラムのコメントを参考にして Applet 上に表示する都市の数を増やす breathfirst() メソッドを理解し depthfirst() メソッドを実装する depthfirst() メソッドのコードと説明を A4 の紙に印刷して再来週提出 ( 提出日 :10 月 24 日 ). 17

グラフの探索 JAVA での実装

グラフの探索 JAVA での実装二つの探索手法深さ優先探索 :DFS (Depth-First Search) 幅優先探索 :BFS (Breadth-First Search) 共通部分元のグラフを指定して極大木を得る探索アルゴリズムの利用の観点から利用する側からみると取り替えられる部品どちらの方法が良いかはグラフに依存操作性が同じでなければ共通のクラスの派生で作ると便利共通化を考える