©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A （ A* ）アルゴリズム.

Presentation on theme: "©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A （ A* ）アルゴリズム."— Presentation transcript:

1 ©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A （ A* ）アルゴリズム

2 ©2008 Ikuo Tahara状態空間の探索 問題 規則前提条件追加リス ト ＃１ SA ＃２ SB ＃３ AB ＃４ AG ＃５ BC ＃６ CA ＃７ CD ＃８ CG A B C G S D ＃１＃２＃２ ＃３＃３ ＃４ ＃６ ＃８＃８ ＃５ ＃７＃７ 状態空間

3 ©2008 Ikuo Tahara状態空間の探索 状態空間 AB C G S D ＃１＃２＃２ ＃３＃３ ＃４ ＃６ ＃８＃８ ＃５ ＃７＃７ 初期状態 目標状態 S A B C D G BG C A D G G 探索木

4 ©2008 Ikuo Tahara探索における基本的処理 局所的情報 → 大局的な情報 節点の選択： 展開すべき節点を選択する． 節点の展開： 子節点をすべて求める． ※循環路を作らない．

5 ©2008 Ikuo Tahara主な探索技法 基本的な探索法 横形（幅優先）探索（ Breadth-first search ） 縦形（深さ優先）探索（ depth-first search ） 評価関数を利用した探索法 分岐限定法（ Branch and bound search ） 山登り法（ Hill-climbing search ） 最良優先探索（ Best-first search ） A （ A* ）アルゴリズム（ Algorithm A star ）

6 ©2008 Ikuo Tahara横形探索と縦形探索 節点の選択の制御 S S 展開すべき節点のリス ト 次に展開する節点

7 ©2008 Ikuo Tahara横形探索と縦形探索 節点の選択の制御 S ABC 展開すべき節点のリス ト S

8 ©2008 Ikuo Tahara横形探索と縦形探索 節点の選択の制御 S ABC 展開すべき節点のリス ト ABS

9 ©2008 Ikuo Tahara横形探索と縦形探索 節点の選択の制御 S ABC 展開すべき節点のリス ト ABC 次に展開する節点

10 ©2008 Ikuo Tahara 横形探索と縦形探索 節点の選択の制御 S ABC DE 展開すべき節点のリス ト ABC

11 ©2008 Ikuo Tahara 横形探索と縦形探索 節点の選択の制御 S ABC DE 展開すべき節点のリス ト ABC 横形（幅優先）探 索 （待ち行 列）

12 ©2008 Ikuo Tahara横形探索と縦形探索 節点の選択の制御 S ABC DE 展開すべき節点のリス ト ABC 縦形（深さ優先）探 索 （スタッ ク）

13 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S OPEN : (S) CLOSED: [ ]

14 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B OPEN : (A B) CLOSED: [S]

15 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B F F OPEN : (B F) CLOSED: [S A]

16 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B C C F F OPEN : (F C H) CLOSED: [S A B] H H

17 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B C C E E F F OPEN : (C H E) CLOSED: [S A B F] H H

18 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B C C D D E E F F I I OPEN : (H E D I) CLOSED: [S A B F C] H H

19 ©2008 Ikuo Tahara横形探索 S S A A B B C C D D E E F F H H I I G G S S A A B B C C D D E E F F H H I I G G OPEN : (E D I G) CLOSED: [S A B F C H]

20 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (S) CLOSED: [ ] S S

21 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (A B) CLOSED: [S] S S A A B B

22 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (F B) CLOSED: [S A] S S A A B B F F

23 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (E H B) CLOSED: [S A F] S S A A B B E E F F H H

24 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (H B) CLOSED: [S A F E] S S A A B B E E F F H H

25 ©2008 Ikuo Tahara縦形探索 S S A A B B C C D D E E F F H H I I G G OPEN : (G I B) CLOSED: [S A F E H] S S A A B B E E F F H H I I G G

26 ©2008 Ikuo Tahara横形探索と縦形探索の比較 探索木 各節点の分岐数： 深さ の節点を生成しようとしていると き

27 ©2008 Ikuo Tahara （１） OPEN リストのメモリ量 横形探索 OPEN リスト内の節点数は少なくとも OPEN リストとして 保持している （ の指数オー ダー）

28 ©2008 Ikuo Tahara （１） OPEN リストのメモリ量 縦形探索 OPEN リスト内の節点数は少なくとも OPEN リストとして 保持している （ の線形オー ダー）

29 ©2008 Ikuo Tahara（２）計算量 探索する節点数 縦形でも横形でも最悪の場合 （ ） （ の指数オー ダー）

30 ©2008 Ikuo Tahara縦形探索の特徴 縦形探索 メモリ量に関しては効率がよい． 再帰呼び出しによる実現が容易である． 問題点 目標状態が探索木の右上にくるような場合 は横形と比して非常に効率が悪い． 特に，目標状態が有限な深さに存在するに もかかわらず深さが無限な探索木に対して 探索が終了しない場合がある．

31 ©2008 Ikuo Tahara再帰呼出しによる縦形探索 Procedure S(n,R) 1.if n=G then flag:=T, print(R), exit. 2.c:=children(n). 3.if c=  then flag:=F, exit. 4.n’:=top(c), c:=c-{n’}. 5.if n’  R then goto 3. 6.R’:=R+{n’}. 7.S(n’,R’). 8.if flag=F then goto 3 else exit.

32 ©2008 Ikuo Tahara評価関数の導入 最適順路のコスト： 節点 n の評価 a b S n G

33 ©2008 Ikuo Tahara評価関数の導入 の推定値： ：その探索時点で最適な順路の評 価値 ：ヒューリスティック関数

34 ©2008 Ikuo Tahara評価関数を利用した探索法 分岐限定法（ Branch and bound search ） 山登り法（ Hill-climbing search ） 最良優先探索（ Best-first search ） A （ A* ）アルゴリズム（ A star algorithm ）

35 ©2008 Ikuo Taharaコストの導入 S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 5 5 2 2 46 6 6 7 72

36 分岐限定法 OPEN リストから 値が最小の節点を選び展開する． n m S m への最適順路は発見済み → 無視 無視

37 ©2008 Ikuo Tahara分岐限定法 SS OPEN : (S(0)) CLOSED: [ ] S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 0

38 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (A(1) B(3)) CLOSED: [S] A A B B 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 13

39 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (B(2) F(7)) CLOSED: [S A] A A B B B B F F 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 3 2 7

40 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (H(5) F(7) C(8)) CLOSED: [S A B] A A B B F F C C H H 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 7 58 8

41 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (I(6) F(7) C(8) G(12)) CLOSED: [S A B H] A A B B F F C C H H G G I I 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 7 8 12 6

42 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (F(7) C(8) G(11)) CLOSED: [S A B H I] A A B B F F C C H H G G I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 7 8 12 11

43 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (C(8) G(11) E(14)) CLOSED: [S A B H I F] A A B B F F C C H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 8 11 E E 14 9

44 ©2008 Ikuo Tahara分岐限定法 S S A A B B C C D D E E F F H H I I G G S S OPEN : (G(11) D(13) E(14)) CLOSED: [S A B H I F C] A A B B F F C C H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 11 E E 14 D D 13 10 12 最適順路！

45 ©2008 Ikuo Tahara ヒューリスティック値の導入 S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 5 5 22 4 6 6 6 7 72 7 46 4 2 34 2

46 ©2008 Ikuo Tahara山登り法 展開して得られた子節点にのみに着目し， 値の最 小の節点を選択する． S S A A B B C C H H E E H H A A B B F F F F S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦④ ⑥ ③ ④ ②④ ⑦ ④ ③ ・ ・循環路に陥る ・局所解に陥る

47 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② OPEN : (S) CLOSED: [ ]

48 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S A A B B S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦ ④ OPEN : (B(4) A(7)) CLOSED: [S]

49 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S A A B B C C H H F F S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦ ⑥ ③ ④ OPEN : (F(3) H(4) C(6) A(7)) CLOSED: [S B]

50 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S A A B B C C H H E E F F S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦ ⑥ ④ ② OPEN : (E(2) H(4) C(6) A(7)) CLOSED: [S B F]

51 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S A A B B C C H H E E F F S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦ ⑥ ④ OPEN : (H(4) C(6) A(7)) CLOSED: [S B F E]

52 ©2008 Ikuo Tahara最良優先探索 OPEN リストのすべての節点に着目し， 値の最小 の節点を選択する． S S A A B B C C H H E E F F S S A A B B C C D D E E F F H H I I G G ④⑦⑥④ ②③④② ⑦ ⑥ G G I I ② OPEN : (G(0) I(2) C(6) A(7)) CLOSED: [S B F E H]

53 ©2008 Ikuo Tahara最良優先探索 有限グラフの場合，必ず成功する． 無限グラフの場合，探索が終了しないことがある． ① ② ② 無限ループ ① 証明に要するコストの予測 値

54 ©2008 Ikuo Tahara A （ A* ）アルゴリズム 評価関数 を用いる． OPEN リストから 値が最小の節点を選び展開する． 子節点について CLOSED リスト内の節点とも比較する． x S m n のため に となり ならば について

55 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (S(0)) CLOSED: [ ]

56 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② 8 7 OPEN : (B(7) A(8)) CLOSED: [S(0)]

57 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B C C H H F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② 15 12 10 OPEN : (A(8) H(10) F(12) C(15)) CLOSED: [S(0) B(7)] 8 7

58 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B C C H H F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (B(6) F(10) H(10) C(15)) CLOSED: [S(0) A(8)] 7 12 10 B B 6 1510 8

59 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (H(9) F(10) C(14)) CLOSED: [S(0) A(8) B(6)] 6 10 C C H H 149 11 8

60 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (I(8) F(10) G(12) C(14)) CLOSED: [S(0) A(8) B(6) H(9)] 10 C C H H 14 G G I I 128 9 6 8

61 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (F(10) G(11) C(14)) CLOSED: [S(0) A(8) B(6) H(9) I(8)] 10 C C H H 14 G G I I 128 G G 11 9 8 6

62 ©2008 Ikuo Tahara A （ A* ）アルゴリズム S S A A B B F F S S A A B B C C D D E E F F H H I I G G 1 1 1 1 3 3 6 6 7 7 2 2 6 5 4 5 2 ④⑦⑥④ ②③④② OPEN : (G(11) C(14) E(16)) CLOSED: [S(0) A(8) B(6) H(9) I(8) F(10)] C C H H 14 I I G G 11 E E 169 13 最適順路！ 6 8 10 8

63 ©2008 Ikuo Tahara A （ A* ）アルゴリズムの性質 評価関数 の効果 G S

64 ©2008 Ikuo Tahara A （ A* ）アルゴリズムの性質 ： A* アルゴリズム 最適順路を必ず見つけることができる． ならば分岐限定法に他な らない． としたとき ならば で展開された節点の集 合