next up previous
Next: 4.1 迷路問題の記述 Up: ソフトウェア特論 講義資料 グラフ探索,問題解決 Previous: 3.6 ビーム探索法(beam search)

4 状態空間探索による問題解決

迷路を現在位置から目標位置まで移動するロボットや,積木の積み重ね手順を 考えるロボットなどを考えた場合,両方に共通のプログラムでそれぞれの問題 を解くことができれば一般的なプログラムであるといえますが,それぞれの問 題をグラフを用いて表現し,1つの関数でどちらの問題を解けることを見て ゆきます. ここで取り上げた問題は,手順を最終的に返すことが目的になりますが,その 手順の途中の段階は状態をもった形で表現できます.つまり,最初の状態から いろいろな状態を経て最終状態へ遷移するということが問題を解くというプロ セスになるということだと考えるわけです. そこで,問題を解くということは,問題解決プロセスの途中の状態をいかに記 述するかという問題になります.そして, 前節であげた問題例を解くプログラムを作る場合に, という項目に注意して考えます.



generated through LaTeX2HTML. M.Inaba 平成18年5月6日