Next: 10.1 探索木の表現
Up: ソフトウェア特論 講義資料 リスト，集合，グラフ，木の処理
Previous: 9.1 グラフを連結なグラフに分割する手続き
現在の状態からある状態へたどり着くという問題を解くということを考えます．
この場合，その問題はいくつかの状態が存在し，状態間で状態遷移があるとい
う形で問題空間を捉えることができ，グラフでその問題空間を表現することが
できるようになります．問題を解くということは，その最初の状態からゴール
の状態へたどり着く道を見つけるということに帰着されます．
ゴールへたどり着く場合に，同じ状態を2度と通らないと考えれば，初期状態
からゴールまでにたどり着く道をすべて含んだものは探索木として表現できま
す．
例として図1を考えることにします．この状態空間において，
出発状態をSとした場合の探索木は図2のようになります．
探索木は出発頂点が変われば変わり，出発頂点をルート（根）とする木になり
ます．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日
![\includegraphics[width=8.0cm]{/home/inaba/eps/lecture/fig/searchtree.eps}](img34.png)