人工知能 2001
Artificial Intelligence 2001


人工知能 2001 のページへ戻る (back to AI lecture 2001 index page)

, , updated

３章　探索 3.1 ブラインド探索(その２)，3.1.2　横型探索，3.1.4 反復深化法，pp.38-43


注)赤字は山口の加筆修正部分です．
配布資料 3.1 ブラインド探索(その２)，横型探索，反復深化法，pp.38-43

　　　　 3.2 ヒューリスティック探索(その１)，pp.43-46
-------------------------------------------------------------
２００１年　７月１１日 (水) 講義ノート (by 山口研 中尾友圭子)


７月４日（水）晴れ
3.1.2　横型サーチ

横型サーチアルゴリズムの実行過程
 |　ループ回数　 |    step    |  　 L1	   |  　L2    	 |
 |	0	|      1     |    [S]     |   φ=[ ] 	|
 |	1	|      3     |     φ     |    [S] 	|
 |		|      5     |    [a,b]   |  　〃　 	|
 |	2	|      3     |     [b]    |   [a,S] 	|
 |		|      5     |   [b,c,d]  |    〃    	|
 | 	3	|      3     |    [c,d]   |  [b,a,S] 	|
 |		|      5     |  [c,d,e,f] | 　 〃    	| 	
 |	4	|      3     |   [d,e,f]  | [c,b,a,S]	|
 |		|      5     |　  [〃]	  |    〃    	|
                                    ↑ 　　　  ↑
                              未展開ノード　展開済ノード

・横型サーチのサーチ順序
P.37の図3.1より、Sからスタートし、深さ１のa,bの順でノードを調べ、
続いて深さ2のc,d,e,fを順に調べ・・・というように探索は行われる。
gを展開するまでのループ回数は8である。
最終的に全サーチを終了するには、9回ループしなければならない。

・サーチ木とは？
「サーチすべき空間」を木構造で表したもの。


3.1.4 反復深化探索アルゴリズム
  AI概論2000講義ノート3.1の最後の「課題」（cutoff = 2の終了まで、Sの深さ＝0）
|ループ回数|  step  |    L1     |        L2            |          cutoff      |
|    0    |    2   |    [S]    |           φ         |              1        |
|    1    |    4   |    [   ]  |          [S]         |              〃       |
|         |    6   |   [a,b]   |          [S]         |              〃       |
|    2    |    4   |    [b]    |        [a,S]         |    aの深さ >= cutoff  |
|         |    6   |    〃     |          〃          |    だから展開しない    |
|    3    |    4   |    [   ]  |        [b,a,S]       |              〃       |
|         |    6   |    〃     |            〃        |              〃       |
|    4    |    4   |    [   ]  |      [S,b,a,S]       |              2        |
|         |    6   |   [a,b]   |            〃        |              〃       |
|    5    |    4   |    [b]    |     [a,S,b,a,S]      |              〃       |
|         |    6   |  [c,d,b]  |            〃        |              〃       |
|    6    |    4   |   [d,b]   |    [c,a,S,b,a,S]     |             〃        |
|         |    6   |    〃     |           〃         |             〃        |
|    7    |    4   |    [b]    |   [b,c,a,S,b,a,S]    |             〃        |
|         |    6   |     〃    |           〃         |             〃        |
|    8    |    4   |     φ　  |  [b,d,c,a,S,b,a,S]   |             〃　      |
|         |    6   |   [e,f]   |           〃         |             〃        |
|    9    |    4   |     [f]   |  [e,b,d,c,a,S,b,a,S] |             〃        |
|         |    6   |     〃    |           〃         |             〃        |
|   10    |    4   |     φ　  |[f,e,b,d,c,a,S,b,a,S] |             〃        |
|         |    6   |     〃    |           〃         |             〃        |


yamaguch@info.nara-k.ac.jp

人工知能 2001 のページへ戻る (back to AI lecture 2001 index page)
山口の担当講義のページへ戻る (back to tomo's lectures page)
Tomo's Top Page へ戻る