Next: 5.1 迷路問題の記述 Up: ソフトウェア第三　講義資料行列，リスト操作，グラフ，探索表現 Previous: 4.7 関数定義の編集例

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

迷路を現在位置から目標位置まで移動するロボットや，積木の積み重ね手順を考えるロボットなどを考えた場合，両方に共通のプログラムでそれぞれの問題を解くことができれば一般的なプログラムであるといえるが，それぞれの問題をグラフを用いて表現し，１つの関数でどちらの問題を解けることを見てゆく．

迷路の問題

図 1: 迷路の問題

初期状態目標状態

図1に迷路の例を示す．左側の図の位置にある円柱が右側の図の位置へ移動するという例である．この問題を記号で示せば，図2のようになり，図の点Aから点Dへ行くためにはどこを通ってゆけばたどり着けるか，という問題である．図の例では，障害物の壁が島になっているところがあり，閉路をもつグラフとなり，探索の制御方法によっては通り道が変わる．

図 2: 迷路問題の記述

$\includegraphics[width=4.5cm]{/home/inaba/eps/lecture/fig/maze.eps}$
積木の問題

図 3: 積木の問題

初期状態目標状態

図3のように，積木があって，左側の状態から右側の状態へもってゆくためにはどのような手順が必要か，というのがここでの問題である．テーブルの上にはスペースがあり，その上には積木をいくつでもおくことができる．そして，一度に動かせる積木はひとつとする．この問題も，図4のように，３つの積木に記号を割付，その記号で問題を記述することにする．

図 4: 積木問題の記述

$\includegraphics[width=8cm]{/home/inaba/eps/lecture/fig/blocksproblem.eps}$

**図 1:** 迷路の問題
初期状態目標状態

**図 2:** 迷路問題の記述
$\includegraphics[width=4.5cm]{/home/inaba/eps/lecture/fig/maze.eps}$

**図 3:** 積木の問題
初期状態目標状態

**図 4:** 積木問題の記述
$\includegraphics[width=8cm]{/home/inaba/eps/lecture/fig/blocksproblem.eps}$

ここで取り上げた問題は，手順を最終的に返すことが目的になるが，その手順の途中の段階は状態をもった形で表現できる．つまり，最初の状態からいろいろな状態を経て最終状態へ遷移する道を探索するということが問題を解くというプロセスになる．

（１）問題に依存しない問題解決機構の一般化問題ごとに個別の問題解決プログラムを作るのではなく，共通となる問題解決の機構と問題記述とを分離する．迷路でも，積み木でも同じ記述法で問題を記述すれば，共通の問題解決機構へ適用すれば問題がとけるようにする．
（２）問題解決のための探索のための状態記述の一般化共通の問題解決機構は状態空間探索機構とし，状態空間の記述を問題に依存しない形で行う．状態空間の状態(ノード)と状態間の遷移(アーク)からなるグラフとして問題空間を表現する．迷路空間が広がったり，積み木の数が増えた場合でも同じ探索手続きで解けるようにする．
（３）問題と探索戦略の切り分け探索手続きの中の次の遷移を決めるための戦略と，問題記述とを分離し，ひとつの問題に対しても異なる戦略を適用できるような一般化を考える．

ここでは，問題空間の状態と遷移をグラフのデータとして表現してしまい，そのグラフ，初期状態，目標状態を指定して汎用の探索プログラムに与える形で問題解決プログラムを作る例を示す．また，（１）のノード状態を表現するのに，集合を使う例，（２）グラフで問題空間を与えるのではなく，状態遷移を計算する手続きを与える例を積み木の例で紹介し，（３）探索手法として，評価関数を使わないもの，使うもの，見込みの評価で探索を行うものなどを同じ問題記述グラフに対して適用できる例を示す．

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