幅優先探索アルゴリズム 復習 Javaでの実装 深さ優先探索 復習 Javaでの実装 1
探索アルゴリズムの一覧 問題を解決するための探索 幅優先探索 深さ優先探索 深さ制限探索 均一コスト探索 反復深化法 欲張り探索 山登り法 最良優先探索 2
Breadth-first search ( 幅優先探索 ) 探索アルゴリズムはノードやリンクからなる階層的なツリー構造で構成された状態空間を探索するアルゴリズムです 幅優先探索アルゴリズムは根ノード (Root node) から隣接している全てのノードを順番に探索していき これを繰り返すことでゴールノードをみつけます ゴールノードが見つかるか すべてのノードが探索されたら探索は終了です つまり ある階層をすべて調べ それが終わるとひとつ深い階層をすべて調べることを繰り返します 横型探索ともいいますアルゴリズムの流れ : 1. キューを作成し スタートノードを加える. 2. ループ : - もしキューが空なら探索失敗として探索を終了する - 先頭のノードを開きキューから取り除く - もし開いたノードがゴールなら それを解決策として探索を終了する. - 開いたノードの子ノードをキューの後ろに追加する 3
例 : 1-> 2->3->4->5->6 -> 4
子ノードを最後に追加する FIFO 型 (First In First Out) のデータ構造キューが実装に用いられる 5
6
擬似コード ( 幅優先探索 ) 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 ;
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
講義内の課題 なぜ 2 つの ArrayList(open, closed) を使用するのか説明しなさい : Figure 1 Figure 1 において, open に保存されているノードを書きなさい [ ] Closed に保存されているノードを書きなさい [ ] 9
Depth-first search( 深さ優先探索 ) 深さ優先探索アルゴリズムはルートノード木の最初のノード (Root node) から ゴールノードが見つかるか葉 ( 子の無いノード Leaf node) に行き着くまで深く掘り下げて探索を行います もしゴールノードが見つからなかったら引き返し 次のまだ通っていないノードから葉ノードに到達するまで探します つまり 深く進んでいき 行き止まったら引き返して また深く進みながらゴール目指します 縦型探索ともいう アルゴリズムの流れ : 1. キューを作成し スタートノードを加える. 2. ループ : - もしキューが空なら探索失敗として探索を終了する - 先頭のノードを開きキューから取り除く - もし開いたノードがゴールなら それを解決策として探索を終了する. - 開いたノードの子ノードをキューの先頭に追加する 10
例 : 11
子ノードを先頭に追加する LIFO 型 (Last In First Out) のデータ構造キューが実装に用いられる 12
13
擬似コード ( 深さ優先探索 ) 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 ;
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 どう変更すべきか?
講義内の課題 1. breathfirst() メソッドを理解する 2. SearchingApplet.java を実行する 3. breathfirst() メソッドと depthfirst() で異なる点を書く 4. 参考サイト http://el-tramo.be/jsearchdemo/ 16
宿題 プログラムのコメントを参考にして Applet 上に表示する都市の数を増やす breathfirst() メソッドを理解し depthfirst() メソッドを実装する depthfirst() メソッドのコードと説明を A4 の紙に印刷して再来週提出 ( 提出日 :10 月 24 日 ). 17