Next: 4.1 迷路問題の記述
Up: ソフトウェア特論 講義資料 グラフ探索,問題解決
Previous: 3.6 ビーム探索法(beam search)
迷路を現在位置から目標位置まで移動するロボットや,積木の積み重ね手順を
考えるロボットなどを考えた場合,両方に共通のプログラムでそれぞれの問題
を解くことができれば一般的なプログラムであるといえますが,それぞれの問
題をグラフを用いて表現し,1つの関数でどちらの問題を解けることを見て
ゆきます.
- 迷路の問題
図4に迷路の例を示します.たとえば,図の点Aから点Dへ行くために
はどこを通ってゆけばたどり着けるか,といった問題が迷路の問題です.
ここで,考える問題解決プログラムは,出発地点と到達目標地点は迷路のなか
のどの点であってもよいという形のプログラムです.AからB,BからA,,,な
どと自由に問題を設定できるようにすることが目標です.また,A,B,C,D以外
の場所をも指定できるようにするにはどのような記述方法をとればよいかも考
えねばなりません.
図の例では,障害物の壁が島になっているところがありますから,グラフには
閉路ができています.探索の制御方法によってはパスが変わってくることに
なります.
- 積木の問題
図5のように,積木があって,積木を start の状態から
goal の状態へもってゆくためにはどのような手順が必要か,というのがここ
での問題です.
テーブルの上にはスペースがあり,その上には積木をいくつでもおくことがで
きるとします.そして,一度に動かせる積木はひとつとします.
ここで取り上げた問題は,手順を最終的に返すことが目的になりますが,その
手順の途中の段階は状態をもった形で表現できます.つまり,最初の状態から
いろいろな状態を経て最終状態へ遷移するということが問題を解くというプロ
セスになるということだと考えるわけです.
そこで,問題を解くということは,問題解決プロセスの途中の状態をいかに記
述するかという問題になります.そして,
前節であげた問題例を解くプログラムを作る場合に,
- (1)問題の記述をいかに一般化できるか
- (2)問題の解決法をいかに一般化できるか
という項目に注意して考えます.
generated through LaTeX2HTML. M.Inaba 平成18年5月6日