3　探索による問題解決Solving Problems by Searching

3.1　問題解決エージェントProblem-Solving Agents

3.1.0　（冒頭）

この章で論じられる問題解決エージェントとは、目標ベース型エージェントの一種であり、原子的表現を用いる。
問題解決のためには、まず現在の状態と成績測定から目標の定式化goal formulationを行い、その目標に基づいてどんな行動や状態を考慮するのかという問題の定式化problem formulationを行う。

Figure 3.2


このルーマニアの地図に基づいて現在位置からBucharestまで進むことを目標とする（目標の定式化）。
そして、現在位置から線で結ばれた隣接都市のうち、どの都市に移動するかを都度判断することにする（問題の定式化）。

Aradから出発するとすると、隣接するどの都市も目標地点であるBucharestではないのでそれだけ見たのではどこに進むべきか分からないが、地図を見ることで各都市に進んだ後にさらにどう進めるかをシミュレートしBucharestまでの経路を見つけることができ、これによって適切な進路を判定することができる。
一般に、直近の選択肢についてその結果が分からない場合でも、その後の行動をシミュレートしていって既知の状態に到達できる場合は、その選択肢のどれを選べばよいかを判定することができる。

この課題環境は、現在位置を常に知ることができるので観測可能であり、都市の数は有限でかつ都市間の移動の途中の状態は考えないので離散的であり、地図に間違いはなく行動の結果は正しく予想できるので既知であり、行動の結果が確率的な変動を含むことはないので決定論的。
なお、状態としては現在位置がどの都市かというだけしか持たないので原子的。
この前提であれば、特定の問題に対する解は特定の行動シーケンスということになる。

目標に達する行動シーケンスを探す過程のことを探索searchという。
探索アルゴリズムは、問題を受けとり、行動シーケンスという形で解solutionを返す。
解が得られれば、後はそれを実行executeすればよい。

この「定式化→探索→実行」の流れは以下のようになる。
function Simple-Problem-Solving-Agent(percept) returns an action
persistent:
seq, an action sequence, initially empty // 行動シーケンス。初期状態では空
state, some description of the current world state // 現在の世界の状態
goal, a goal, initially null // 目標。初期状態では未設定
problem, a problem formulation // 定式化された問題
state ← Update-State(state, percept)
if seq is empty then
goal ← Formulate-Goal(state) // 目標の定式化
problem ← Formulate-Problem(state, goal) // 問題の定式化
seq ← Search(problem) // 探索
if seq = failure then return a null action
action ← First(seq)
seq ← Rest(seq)
return action

この例では、行動シーケンスの実行中は入力された知覚を無視して盲目的に実行しているが、制御理論ではこれを開ループシステムopen-loop systemという。

3.1.1　明確に定義された問題と解Well-defined problems and solutions

問題は、以下の5つの要素で正式に定義できる。
エージェントがその状態から開始するところの初期状態initial state
たとえば、Aradから開始する場合は、初期状態は \(In(Arad)\) と表される。

エージェントにとって可能な行動
状態が \(s\) の場合に可能な行動の集合は、Actions\((s)\) で求められる。
たとえば、In(Arad) という状態での可能な行動の集合は \(\{ Go(Sibiu), Go(Timisoara), Go(Zerind) \}\) となる。

それぞれの行動がどのような結果をもたらすかという、遷移モデルtransition model
状態\(s\)で行動\(a\)をとった場合の結果としての状態は Result\((s, a)\) で求められる。
たとえば、Result\((In(Arad), Go(Zerind)) = In(Zerind)\) ということになる。

初期状態、各状態での可能な行動、遷移モデルが与えられると、その問題における到達可能な状態の集合である状態空間state spaceが定まる。
状態空間は、各ノードが状態、ノード間を結ぶ線分が行動となるような有向ネットワークdirected networkやグラフgraphと呼ばれる図で表現することができる。
上のルーマニアの地図もそのような状態空間（無向グラフ）となっている。
状態空間における互いに結ばれたノード同士のつながりからなる経路pathは、行動シーケンスによる一連の状態の遷移を意味する。

目標に到達した状態かどうかを判定するゴールテストgoal test

その経路にかかるコストである経路コストpath costを算定する関数
経路コストは、各行動における個々の状態遷移のコストである段階コストstep costの総和となる（この章ではそう想定する）。
状態 \(s\) で行動 \(a\) をとった結果、状態 \(s'\) に移ったという場合の段階コストは \(c(s, a, s')\) と表される。

とりあえず段階コストはゼロ以上と想定する。
初期状態から目標に到達する解は複数あり得るが、その中で経路コストが最も低い解が最適解optimal solutionとなる。

3.1.2　問題の定式化Formulating problems

問題の定式化にあたっては、必要以上の詳細を無視して適切に抽象化abstractionすることが必要となる。
詳細を無視しても、そこからまた詳細な世界に拡張できるかたちになっていれば、その抽象化は有効valid。
抽象化によって元の問題よりも解に含まれる行動を実行することが容易になるのであれば、その抽象化は有用useful。

抽象化の際には、有効性を保持しながらできるだけ有用性を高めるようにする。

3.2　問題の例Example Problems

3.2.1　単純化された問題Toy problems

掃除機問題

Figure 3.3

状態
掃除機の位置、それぞれのマス内がきれいか汚れているかの組み合わせ。したがって 2^3=8 通りの状態がある。
初期状態
8通りの状態のうち、全てが初期状態となりうる。
行動
左に進む、右に進む、吸うの3つがある。
遷移モデル
右のマスにいる場合は、左に進むと左のマスに移動する。左のマスにいる場合は、右に進むと右のマスに移動する。マスが汚れている場合は、吸うとマスがきれいになる。それ以外の場合は、状態は変化しない。
ゴールテスト
全てのマスがきれいになっているうかどうかで判定する。
経路コスト
全ての段階コストは 1。なので、何回行動したか。
8パズル8-puzzle

Figure 3.4

3×3で9マスの板に8つのタイルは入っている。左図の状態から空のマスにタイルをスライドさせながら右図の状態に持っていくというパズル（→Wikipedia）。
状態
8つのタイルの配置。
初期状態
全ての状態が初期状態となりうる。ただし、全ての初期状態から全ての目標に到達できるわけではない。
行動
空のマスの動きの上下左右とすればよいが、それ以外の構成も考えられる。
遷移モデル
左図で空のマスを左に動かした場合は 5 のタイルと空のマスが入れ替わる。このように、状態と行動で結果が定まる。
ゴールテスト
タイルの配置が目標状態（右図）と一致しているかどうか。
経路コスト
全ての段階コストは1。なので、何回行動したか。

これはスライディング・ブロック・パズルの一種であり、NP完全NP-complete問題である。

8クイーン問題8-queens problem

Figure 3.5

チェス盤の上に8つのクイーンを、どれも同じ縦・横・ななめのならびに来ないように配置するというパズル。図の例では左上と右下のクイーンがぶつかっているので、失敗ということになる。
この問題の解決には主に、増加による定式化incremental formulationと完全状態からの定式化complete-state formulationの2種類があるが、ここでは前者について考える。
状態
盤上へ0～8個のクイーンを配置する、全ての可能な配置。
初期状態
盤上にクイーンが乗っていない。
行動
空のマスにクイーンを置く。
遷移モデル
クイーンが置かれたマスにクイーンが配置された状態を返す。
ゴールテスト
8つのクイーンが全てぶつからないような状態で盤上に配置されているかどうか。
経路コスト
最終状態のみが重要なので、特に問題とならない。

上の定式化だと、行動シーケンスは約1.8×10^14通りという途方もない数になるが、以下のように改善できる。
状態
盤上に0～8個のクイーンを左の列から順にぶつからないように配置していく、全ての可能な配置。
行動
n番目のクイーンを左からn列目に、既存のクイーンとぶつからないように置く。

このように改善すると、行動シーケンスはたったの2,057通りにすることができる。
しかしこの方法でも、100クイーン問題とかは計算量が膨大で太刀打ちできない。

Donald Knuth（1964）が提示した問題
\(4\) という数に階乗、平方根、小数切捨てという操作を任意の回数行うことで、目的の自然数にするというもの。
たとえば、\(\lfloor \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{(4!)!}}}}} \rfloor = 5\)。
状態
正の数。
初期状態
\(4\)。
行動
階乗（整数にのみ）、平方根、小数切捨て。
遷移モデル
数学的な定義どおり。
ゴールテスト
状態が目的の自然数と一致しているかどうか。

この問題では状態空間の大きさは無限大となる。

3.2.2　現実世界の問題Real-world problems

ルーマニアの経路探索問題で見たような経路探索のアルゴリズムは現実世界の問題でよく用いられる。

空路検索サービス
状態
現在位置（空港等）、現在時刻は当然として、経路コストの計算に影響してくる各種履歴情報も持つ必要がある。
初期状態
ユーザーによって指定される。
行動
現在位置（+乗り換え時間）から現在時刻以降発のあらゆる航空便のあらゆる席の等級。
遷移モデル
乗った便の目的地が現在位置になり、到着時刻が現在時刻となる。
ゴールテスト
ユーザーによって指定された目的地にいるかどうか。
経路コスト
金額、待ち時間、飛行時間、入出国・関税手続き、席の品質、時刻、航空機の種類、マイレージ等々が関係する。

これ以外にも、予定通り飛ばないような場合も考慮に入れる必要があるかもしれない。

旅行問題touring problems
経路探索問題のように単に目的地に着くというだけではなく、全ての場所を1回以上周ってから目的地に着くことを目標とする。

巡回販売員問題traveling salesperson problem, TSP
旅行問題とは違い、一筆書きで全てを周る最短経路を目指す。
NP困難NP-hard問題として知られる。

VLSIレイアウトVLSI layout問題
超大規模集積回路VLSI上に配置する膨大な量の部品や配線の最適な配置を目標とする。

ロボット・ナビゲーションrobot navigation
経路探索問題をより一般化し、連続的な空間を前提としたもの。平面を移動する場合は空間は二次元となるが、ロボットは複数の作動装置を持ちうるので、探索空間はそれ以上の多次元空間となる。

自動組立順序判定automatic assembly sequencing
組立の順序を間違うとうまく組み立てられないようなものの順序を求める。
目的の効能を持つようなアミノ酸の3次元的な配置を求めるタンパク質設計protein designも、こういう組立問題assembly problemの一つ。

3.3　解の探索Searching for Solutions

3.3.0　（冒頭）

解の探索においては、初期状態からの可能な行動シーケンスを調べていくことになる。

Figure 3.6

ルーマニアの例でいくとこの図のようになるが、これを探索木search treeという。

初期状態である根rootから始まり、そこから可能な行動によって新たな状態を生成generateして探索木を展開expandしていく。
個々の楕円をノードnodeといい、生成される元のノードを親ノードparent node、生成される側を子ノードchild nodesという。
子ノードを持たないノードを葉ノードleaf nodeといい、そこから展開可能な候補としての葉ノードの集合をフロンティアfrontierまたはオープン・リストopen listという。
上図では、展開済みのノードはグレー表示、フロンティアに属するノードは太枠、未生成のノードは淡色で示されている。

探索においては、解が見つかるか、もう展開ができなくなるかというところまで展開を続けていくことになるが、様々な探索アルゴリズムは主に、どこを展開するかの決定方法が異なっている。
これを探索戦略search strategyという。

一般的な木探索tree-searchアルゴリズムは以下のようになる。
function Tree-Search(problem) returns a solution, or failure
initialize the frontier using the initial state of problem // problemの初期状態によってフロンティアを初期化する
loop do
if the frontier is empty then return failure // フロンティアが空になったら失敗
choose a leaf node and remove it from the frontier // どれか一つの葉ノードを選択し、それをフロンティアから外す
if the node contains a goal state then return the corresponding solution // 選択したノードが目標の状態を含んでいれば、それに対応する解を返す
expand the chosen node, adding the resulting nodes to the frontier // 選択したノードを展開し、得られた子ノードをフロンティアに加える

上図の(c)をよく見ると、SibiuからAradに逆戻りしているパターンがあることがわかる。
こういうのを繰り返し状態repeated stateといい、これはループ経路loopy pathによって作られる。
経路コストは段階コストの総和であり、段階コストはゼロ以上と仮定しているので、ループ経路は探索から外さなければならない。

ある状態に至る経路が複数ある場合は、冗長経路redundant pathが生じる。
ループ経路も冗長経路の一種。
ルーマニアの例でいくと、Arad→Sibiuに対してArad→Zerind→Oradea→Sibiuは冗長経路。

冗長経路も探索に含める意味はない。
問題の定式化の時点で冗長性を排除することができる場合もある。
8クイーン問題の改良版では左の列から順にクイーンを置いていくとしていたが、どの列からでも置けるようにしても問題としては成立する。
しかし、前者の場合だと八つのクイーンのある配置に至る経路はただ1つなのに対し、後者の場合だと8の順列である8!通りの経路が存在してしまうことになる。

冗長経路を避けることは重要なことなのだが、そのためには過去の状態を記憶しておく必要がある。
木検索を改良して、探索済み集合explored setまたはクローズド・リストclosed listとして展開済みのノードの集合を保持するようにしたのがグラフ探索graph-searchアルゴリズムである。
function Graph-Search(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
initialize the explored set to be empty // 探索済み集合を空に初期化する（追加）
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
add the node to the explored set // 選択したノードを探索済み集合に加える（追加）
esxpand the chosen node, adding the resulting nodes to the frontier
only if not in the frontier or explored set // 子ノードのうち、フロンティアにも探索済み集合にも含まれていないものだけ（追加）
グラフ探索では、同じノードが重複することがないため探索木は状態空間そのものの形となる。
また、探索済みの領域と未探索の領域は常にフロンティアによって仕切られることになり、初期状態から未探索の領域に達するためには必ずフロンティアを経由しなければならないということになる。

3.3.1　探索アルゴリズムの基礎構造Infrastructure for search algorithms

Figure 3.10

ノード\(n\)は以下のような要素を持つ必要がある。
\(n\).State
当該ノードに対応する状態
\(n\).Parent
当該ノードを生成した親ノード
上図のノード間の矢印が子ノードから親ノードに向いていることに注意。
\(n\).Action
親ノードから当該ノードが生成された行動
\(n\).Path-Cost
初期状態から当該ノードにいたるまでの経路コスト

以下のChild-Node関数は、親ノードと行動からそれによって生成される子ノードを返す。
function Child-Node(problem, parent, action) returns a node
return a node with // 以下のようなノードを返す
State = problem.Result(parent.State, action),
Parent = parent,
Action = action,
Path-Cost = parent.Path-Cost + problem.Step-Cost(parent.State, action)

あるノードが目標である場合は、そこからParentをたどっていくことで経路が得られ、それぞれのActionをつなげることで解としての行動シーケンスが得られる。
なお、状態は世界のある有り様を示すのに対し、ノードは飽くまでも探索木の構成要素であって特定の経路を前提としている。
複数のノードが同一の状態に対応するということもありうる。

フロンティアのデータを保持するデータ構造としてはキューqueueが適している。
キューには以下のような操作がある。
Empty?(\(queue\))
キューが空のときにのみ true を返す
Pop(\(queue\))
キューの先頭の要素をキューから外して返す
Insert(\(element, queue\))
要素をキューに加え、そのキューを返す
キューは登録された要素が保持される順番が主たる特徴となるが、一般的な種類としては以下の3つがある。
先入先出キューfirst-in first-out queue, FIFO queue
最も（登録されたのが）古い要素から順に取り出される
後入先出キューlast-in first-out queue, LIFO queue
最も新しい要素から順に取り出される
優先度付キューpriority queue
最も優先度の高い要素から順に取り出される

探索済み集合はハッシュ・テーブルhash tableとして実装できる。
実装にあたっては、等しく扱うべき単位に注意しなければならない。
たとえば巡回販売員問題であれば \(\{Bucharest, Urziceni, Vaslui\}\) は \(\{Urziceni, Vaslui, Bucharest\}\) と同様の内容となる。
同様に扱われるべき内容は同様な形になるようにしてやれば実装が容易になる場合がある。

3.3.2　問題解決の成績評価Measuring problem-solving performance

探索アルゴリズムを評価するには、以下の4つの方法がある。
完全性completeness
解が存在する場合には必ず解を見つけられるかどうか
最適性optimality
最適解（→3.1.1）を見つけられるかどうか
時間的複雑性time complexity
どれだけ時間がかかるか
空間的複雑性space complexity
どれだけのメモリを必要とするか

時間的・空間的複雑性に関しては、対象となる問題自体の困難さとの関係で考えられることになる。
問題の複雑さは、計算機科学では状態空間のグラフの大きさ（ノードの数とノード間を結ぶリンクの数の和）で測られることが多い。
しかし、予めグラフが判明していなかったり大きさが無限大だったりする場合もあるので、以下の3つの量で測られることが多い。
分岐因子branching factor
一つのノードに対する最大の子ノードの数。値は\(b\)で表される
目標ノードの深さdepth
根ノードから最も近い目標ノードまでのステップ数。値は\(d\)で表される
最大経路長
グラフ内に存在する最長の経路の長さ。値は\(m\)で表される。
時間は探索時に処理されるノードの数と関連し、空間は探索時に記憶されるノードの数と関連する

さらに、以下のように考えて評価することもできる。
探索コストsearch cost
時間的複雑性 + 場合によっては空間的複雑性も加える
総合コストtotal cost
探索コスト + 解の経路コスト
二つの重み付けの比率は場合に応じて考える必要がある。

3.4　事前情報なし探索戦略Uninformed Search Strategies

3.4.0　（冒頭）

事前情報なし探索uninformed search、別名 盲目探索blind searchとは、問題の定義以外の情報を予め与えられない状態で探索を行うもの。

3.4.1　幅優先探索Breadth-first search

Figure 3.12


まず、根ノードを展開し、次に全ての子ノードを展開し、そして全ての孫ノードを展開し……という感じで進めていく。
Graph-Search関数内でフロンティアのデータ構造として先入先出キューを用いるようにすれば、この幅優先探索とすることができる。
浅い順にノードを展開していくため、目標ノードが見つかった場合は自動的にそれが最も浅い目標ノードということになる。

function Breadth-First-Search(problem) returns a solution, or failure
node ← a node with State = problem.Initial-State, Path-Cost = 0
if problem.Goal-Test(node.STATE) then return Solution(node) // 根ノードが目標ノードだったらいきなり終了
frontier ← a FIFO queue with node as the only element
explored ← an empty set
loop do
if Empty?(frontier) then return failure
node ← Pop(frontier) // 先入先出キューなので、最も浅いノードが選ばれる
add node.State to explored
for each action in problem.Actions(node.State) do
child ← Child-Node(problem, node, action)
if child.State is not in explored or frontier then
if problem.Goal-Test(child.State) then return Solution(child) // Graph-Searchのときと位置が違うが、処理の効率化のためここでやっている（こうしないと\({\mathcal O}(b^{d + 1})\)となってしまう）
frontier ← Insert(child, frontier)

評価
完全性
\(d\)と\(b\)が有限であれば、○
最適性
つまりノードの深さと経路コストの順番が一致していれば、○
時間的複雑性
根ノードから\(b\)の子ノードが生成され、次にその\(b\)のノードからそれぞれ\(b\)の子ノードが生成され（つまり\(b^2\)）、次の階層では\(b^2\)のノードからそれぞれ\(b\)の子ノードが生成される（つまり\(b^3\)）、という流れが深さ\(d\)で目標ノードが見つかるまで繰り返される。
したがって生成されるノードの数は、\(b + b^2 + b^3 + ... + b^d = {\mathcal O}(b^d)\)となる。
空間的複雑性
上で述べたような流れでノードが生成されていくわけだが、探索済み集合には深さ\(d - 1\)までのノードが全て格納されると考えると\({\mathcal O}(b^{d - 1})\)、フロンティアには\(b^d\)格納されるので\({\mathcal O}(b^d)\)となる。
したがって全体としてはやはり\({\mathcal O}(b^d)\)となる。

複雑性に関しては指数関数的な値となっているが、これは下図に示されているように、かなりまずい。
（分岐因子は10、処理時間は1秒間に百万ノード、メモリ消費は1ノード毎に1000バイトとして計算されている）
深さ ノード数 時間 メモリ
2 \(110\) .11 ミリ秒 107 キロバイト
4 \(11,110\) 11 ミリ秒 10.6 メガバイト
6 \(10^6\) 1.1 秒 1 ギガバイト
8 \(10^8\) 2 分 103 ギガバイト
10 \(10^{10}\) 3 時間 10 テラバイト
12 \(10^{12}\) 13 日 1 ペタバイト
14 \(10^{14}\) 3.5 年 99 ペタバイト
16 \(10^{16}\) 350 年 10 エクサバイト

深さが少し増えただけで複雑性が大幅に増えているのがわかる。
空間的複雑性の方が時間的複雑性よりも深刻。
13日間ならまだ待てるが1ペタバイトのメモリを使うのはかなり難しい。
とはいえ時間的複雑性自体もやっぱり深刻。
たった深さ16の探索のために350年もかかるとか。
結局、このような指数関数的に複雑性が増大する場合は、小規模な探索以外では非現実的ということになる。

3.4.2　統一コスト探索Uniform-cost search

Graph-Search関数内のフロンティアのデータ構造として最も経路コストが低いノードを返すような優先度付キューを用いるようにすると、統一コスト探索とすることができる。
幅優先探索と違い、段階コストがバラバラの場合であっても最適性を満たす。
ただし、経路の長さは考慮しないため、段階コストが0のものが含まれている場合はそこで無限ループに陥ってしまうため、完全性を満たすためには全ての段階コストはゼロ以上でなければならない。
function Uniform-Cost-Search(problem) returns a solution, or failure
node ← a node with State = problem.Initial-State, Path-Cost = 0
frontier ← a priority queue ordered by Path-Cost, with node as the only element
explored ← an empty set
loop do
if Empty?(frontier) then return failure
node ← Pop(frontier) // 最も経路コストが低いノードが選ばれる
if problem.Goal-Test(node.State) then return Solution(node) // Breadth-First-Searchの位置でやってしまうと最適でない解を返してしまう可能性が生じるため、またこの位置に戻っている（※1）
add node.State to explored
for each action in problem.Actions(node.State) do
child ← Child-Node(problem, node, action)
if child.State is not in explored or frontier then
frontier ← Insert(child, frontier)
else if child.State is in frontier with higher Path-Cost then // 子ノードと同じ状態に対応するのノードが既にフロンティアに含まれている場合であっても、それよりも経路コストが低い場合は登録ノードを置き換える（※2）
replace that frontier node with child

Figure 3.15

※1、※2の必要性については、上図でSibiuからBucharestまでの経路探索をシミュレーションしてみるとわかる。
複雑性については、最適解の経路コストを\(C*\)（\(^*\)は「スター」と読み、最適な\(C\)という意味合い）とし、最小の段階コストを\(ε\)とすると、最悪の場合は\({\mathcal O}(b^{1 + [C^* / ε]})\)ということになる。
\(ε = 1\)であれば\({\mathcal O}(b^{d + 1})\)となり、幅優先探索とほぼ一緒となる（\(d + 1\)となっているのは、ゴールテストを展開のタイミングで行っていることによる）。

3.4.3　深さ優先探索Depth-first search

Figure 3.16


フロンティアの中の最も深いノードから順に探索していくというもの。
Graph-Search関数内でフロンティアのデータ構造として後入先出キューを用いるようにしたものがこれにあたる。
グラフ探索ではなく木探索として実装されることも多く、プログラムとしては再帰呼び出しによる実装も一般的。

有限の状態空間内ではグラフ探索型だと完全性を満たすが、木探索型だと満たさない。
展開中のノードまでの経路に含まれるノードが子ノードとして現れた場合は無視するようにすれば、メモリの追加負担なしに無限ループを避けることができる。
だがこの場合も、冗長経路を避けることはできない。
無限の状態空間内ではどちらも完全性を満たさない。

最適性は満たさない。

時間的複雑性に関しては、グラフ探索型だと一応状態空間のサイズに制限されるが、木探索型だと最大深度 m までの全てのノードを探索する可能性もあるので\({\mathcal O}(b^m)\)となる。
さらに\(m\)は無限大ということもあり得る。

空間的複雑性に関しては、グラフ探索型だと特に違わないが、木探索型だと探索中の経路とその経路上のノードからの子ノードだけ保持すればよいので\({\mathcal O}(bm)\)という非常に小さな値になる。
幅優先探索と比較すると、木探索型の深さ優先探索であれば深さ16の場合であってもメモリ消費はたったの156KBなのでその差は歴然（約 1 / 7,000,000,000,000）。
というわけで、今後この章では深さ優先探索という場合は主に木探索型の方を考える。
後戻り探索backtracking searchという、もっとメモリ効率のよいアルゴリズムも存在する（→6章）。

3.4.4　深さ制限探索Depth-limited search

深さ優先探索の、無限のグラフではほぼ使い物にならないという欠点を補うために、最大深度を制限して探索を行うというもの。最大深度は\(l\)で表される。
\(l < d\)の場合は解を見つけられず完全性を満たさないし、\(l > d\)の場合は最適性を満たさない。
\(d\)が予め判っていれば問題ないが。
時間的複雑性は\({\mathcal O}(b^l)\)、空間的複雑性は\({\mathcal O}(bl)\)となる。

Tree-SearchやGraph-Searchを一部修正しても実装可能だが、ここでは再帰呼び出しを使った実装例を示す。
解が見つからなかった場合の値が、本当に解がなかったという場合の失敗failureと、深さ制限に抵触して解が見つけられなかったという場合の打ち切りcutoffの2種類があることに注意。
function Depth-Limited-Search(problem, limit) returns a solution, or failure/cutoff
return Recursive-DLS(MAKE-NODE(problem.Initial-State), problem, limit)
function Recursive-DLS(node, problem, limit) returns a solution, or failure/cutoff // 再帰呼び出しされる関数
if problem.Goal-Test(node.State) then return Solution(node)
else if limit = 0 then return cutoff // 深さ制限に達してしまったら cutoff を返す
else
cutoff_occurred? ← false // cutoff発生フラグ
for each action in problem.Actions(node.State) do
child ← Child-Node(problem, node, action)
result ← Recursive-DLS(child, problem, limit - 1) // 子ノードはそれ自体の深さが一つ増えるため、深さ制限値を一つ減らして再帰呼び出し
if result = cutoff then cutoff_occurred? ← true
else if result ≠ failure then return result // 再帰呼び出し先で解が見つかった場合は、それを返す
if cutoff_occurred? then return cutoff else return failure // 全ての子ノード（とそこから続く全子孫ノード）を探索しても解が見つからなかった結果として、cutoffが発生している場合はcutoffを（この場合はその先に解が存在する可能性が残っている）、そうでない場合はfailureを返す

3.4.5　反復深化深さ優先探索Iterative deepening depth-first search

Figure 3.19


最大深度を0,1,2,...と順番に設定しなおして解が見つかるまで深さ優先探索を行うというもの。
反復深化探索iterative deepening searchの一種で、これを深さ優先探索と組み合わせたもの。

反復深化探索のアルゴリズムは以下のようになっている。
function Iterative-Deepening-Search(problem) returns a solution, or failure
for depth = 0 to ∞ do
result ← Depth-Limited-Search(problem, depth)
if result ≠ cutoff then return result
これは、深さ優先探索の少ないメモリ消費量と、幅優先探索の完全性・最適性のいいとこ取りとなる。
最大深度を増やすたびに毎回最初から深さ優先探索を繰り返すのは無駄が大きいように思えるが、通常はノードの数の大半はその時点での最も下の階層にあるので、それまでの深度での繰り返しはあまり問題にはならない。
解は\(d\)階層にあるとすると、\(d\)階層（ノード数\(b^d\)）は\(1\)回、\(d - 1\)階層（ノード数\(b^{d - 1}\)）は\(2\)回、\(d - 2\)階層（ノード数\(b^{d - 2}\)）は\(3\)回...という具合にノードが生成されることになるので、最悪の場合の生成ノード数は\(b^d + 2×d^2 + 3×d^3 + ... + (d - 1)b^2 + db\)となる。
たとえば\(b = 10, d = 5\)とした場合には、幅優先探索だと最大で\(111,110\)個のノードが生成されるのに対し、反復深化深さ優先探索では最大で\(123,450\)個となる。
それでも無駄な繰り返しを極力抑えたい場合は、メモリの許す限りは幅優先探索を行い、それ以降は反復深化深さ優先探索に切り替えるようにすればよい。
一般的に、ノードの深さと経路コストの順番が一致しており探索空間が大きく解の深さが判らない場合の事前情報なし探索としては、この方法が最も好ましい。

反復深化探索の考え方と統一コスト探索を組み合わせたものは、反復延伸探索iterative lengthening searchと呼ばれる。
しかしこれは統一コスト探索と比べてオーバーヘッドがかなり大きくなってしまう。

3.4.6　双方向探索Bidirectional search

Figure 3.20


初期状態と目標点の双方から探索を進めていき、経路がつながる点（お互いのフロンティア内の共通ノード）を探すというもの。
一方向に進める場合は最悪で\(b^d\)のノードを探索することになるが、双方向的に進めて中間点付近で経路がつながった場合は\(b^{d / 2} + b^{d / 2}\)となり、はるかに少なくなる。
時間的複雑性も空間的複雑性も\({\mathcal O}(b^{d / 2})\)となる。
片方の探索を反復深化深さ優先探索にすることで（両方は不可）、空間的複雑性を約半分にすることができる。
この方法は時間的複雑性に強みがあるが、目標点から逆方向に探索を進めるというのは必ずしも容易ではない。
ルーマニアの経路探索の例や8パズルならば容易だが、掃除機問題のように目標となる状態が明示的に示されているがそれが複数ある場合や、8クイーン問題のように目標となる状態が列挙しにくい場合は容易ではない。
また、最初に見つかった解が最適解とは限らない。
さらに、状態遷移に方向がある場合は逆方向も計算できる必要がある。

3.4.7　事前情報なし探索戦略の比較Comparing uninformed search strategies

　 完全性 時間的複雑性 空間的複雑性 最適性
幅優先探索 あり ※1 \({\mathcal O}(b^d)\) \({\mathcal O}(b^d)\) あり ※3
統一コスト探索 あり ※1 ※2 \({\mathcal O}(b^{1 + [C^* / ε]})\) \({\mathcal O}(b^{1 + [C^* / ε]})\) あり
深さ優先探索 なし \({\mathcal O}(b^m)\) \({\mathcal O}(bm)\) なし
深さ制限探索 なし \({\mathcal O}(b^l)\) \({\mathcal O}(bl)\) なし
反復深化深さ優先探索 あり ※1 \({\mathcal O}(b^d)\) \({\mathcal O}(bd)\) あり ※3
双方向探索（適用可能であれば） あり ※1 ※4 \({\mathcal O}(b^{d / 2})\) \({\mathcal O}(b^{d / 2})\) あり ※3 ※4
※1 : \(b\)が有限の場合
※2 : 全ての段階コストがゼロより大きい場合
※3 : 全ての段階コストが等しい場合
※4 : 両方の探索で幅優先探索が使われている場合（完全性の場合は片方でいいのでは？）
表は木探索の場合の内容だが、グラフ探索の場合であれば、時間的・空間的複雑性が状態空間の大きさに制限される点と、深さ優先探索も有限の状態空間内であれば完全性を満たす点が異なる。

3.5　事前情報あり（ヒューリスティック）探索戦略Informed (Heuristic) Search Strategies

3.5.0　（冒頭）

事前情報あり探索informed searchとは、問題の定義以外の情報を予め与えられた状態で探索を行うもの。
ここでは最良優先探索best-first searchという方法を考える。
統一コスト探索では経路コスト（\(g(n)\)と表される）は最小のものから探索を進めていたが、最良優先探索では評価関数evaluation function（\(f(n)\)と表される）に基づいて評価値が最小のものから探索を進めていく。

探索戦略は評価関数の選び方で決まる。
ほとんどの最良優先探索では評価関数としてヒューリスティック関数heuristic function（\(h(n)\)と表される）を含むものを使っている。
\(h(n)\)が示すのは、ノード\(n\)から目標状態までの最短経路の見込み値となる。
\(n\)が目標ノードであれば\(h(n) = 0\)となる。
常に\(h(n) = 0\)であれば、統一コスト探索と同じものとなる。

3.5.1　貪欲な最良優先探索Greedy best-first search

これは評価関数としてそのままヒューリスティック関数を用いるというもの。
つまり、\(f(n) = h(n)\)。
目先のノードの\(h(n)\)だけしか見ずに進むので、貪欲と呼ばれる。

たとえば、ルーマニアの経路探索で以下の表のような各地点から目標地点（Bucharest）までの直線距離straight-line distanceを評価値とした場合の探索の流れは下図のようになる。

Figure 3.22

Figure 3.23

Figure 3.2

この例では一応最小限の探索コストで解を得られているが、実際にはFagaras経由の経路よりもRimnicu Vilcea経由の経路のほうが短いため、最適解ではない。
また、これは有限な状態空間内であっても完全性も満たさない。
たとえばIasiからFagarasへの経路を探索しようとすると、NeamtとIasi間を往復するだけで永久にFagarasにたどり着くことはない。
グラフ探索型にしておけば、有限な状態空間内でなら完全性を満たす。
そして時間的・空間的複雑性は、最悪の場合であれば全部のノードを探索することになるので\(O(b^m)\)となるが、これはヒューリスティック関数の性能次第で減らすことができる。

3.5.2　A*探索 : 見込み総合コストの最小化A* search: Minimizing the total estimated solution cost

評価関数として\(f(n) = g(n) + h(n)\)を使うというもの。
\(g(n)\)は初期状態から\(n\)までの経路コストであり、\(h(n)\)は\(n\)から目標までの見込みコストなので、それの和は\(n\)を通る最も低コストな解の見込みコストとなる。
\(h(n)\)を適切に定めれば、A*探索は完全性と最適性を満たす。
さらにその場合、その\(h(n)\)を使って根ノードから最適経路を探索するアルゴリズムの中ではA*探索が最も展開するノード数が少なく効率的なものとなる。
この性質を最適最効率optimally efficientという。

Figure 3.24

A*探索が最適性を満たすための\(h(n)\)の条件
第1の条件は\(h(n)\)がコストを過大評価しないこと（適格性）
このような\(h(n)\)を適格ヒューリスティックadmissible heuristicという。
この場合、\(f(n) = g(n) + h(n)\)は真の経路コストを過大評価しない。
第2の条件は、任意の\(n\)と、その後続ノード\(n'\)について、\(h(n) ≦ c(n, a, n') + h(n')\)を満たすこと（一貫性consistencyまたは単調性monotonicity）
後続ノードの\(f\)の方が低くなることはないということ。
これは三角不等式triangle inequalityの一種。
直線距離はこれを満たす。
結局、一貫性を満たせば、自動的に適格性も満たすことになる。

木探索型であれば適格性だけでOKだが、グラフ探索型の場合は一貫性も必要になる。
たとえば↓のような場合は、グラフ探索型だと先に[s3: f = 35]が登録されてしまって[s3: f = 30]が無視されてしまう（しかし適格性があれば目標よりもコストは低いはずなので木探索型であれば問題ない）。
[s1: f = 10]┬[s2: f = 20]─[s3: f = 35]
　└[s4: f = 50]─[s3: f = 30]

\(h(n)\)が一貫性を満たす場合は、A*探索でノードが展開されるときは常にそのノードまでの最適経路が定まった状態となる。

Figure 3.25

\(h(n)\)が一貫性を満たす場合は\(f(n)\)が減少することはないため、図のように根ノードから徐々に上がっていく等高線を描くことができる。
たとえば、\(400\)の等高線の線上+内側の全てのノードは\(f(n)\)が\(400\)以下ということになる。
目標ノードに向かって等高線が細く延びるような\(h(n)\)は、探索ノードの数が少なくて済むので性能がよい。

C*（最適解のコスト）の等高線の内側のノードは全て展開される。
C*の等高線に乗っているノード（つまり\(f(n) = C^*\)のノード）は展開されるかもしれないし、されないかもしれない。

A*探索が完全性を満たすためには、C*以下の（つまりC*の等高線の線上+内側の）ノード数が有限であればよい。

Figure 3.24を見ると、Timisoaraは\(f(n) = 447\)であり\(C^* = 418\)より大きいため、根ノードの直接の子であるにもかかわらず展開されていない。
最適性を保ったままTimisoara以下の全経路を切り捨てていることになるが、これを刈り込みpruningという。

適切な\(h(n)\)を使用した場合にA*探索は完全性・最適性を満たしまた最適最効率となるが、時間的・空間的複雑性はやはり指数関数的に増大するため、これが常に最良の方法になるとは限らない。

真の値を\(h^*\)とした場合、ヒューリスティックの絶対誤差absolute errorを\(Δ \equiv h^* - h\)、相対誤差relative errorは\(\epsilon \equiv (h^* - h) / h^*\)と表される。
目標状態が1つで逆の移動もできる場合（8パズル等）、A*探索の時間的複雑性は\({\mathcal O}(b^Δ)\)となる。
段階コストが一定の場合は\({\mathcal O}(b^{\epsilon d})\)となる。
よって、この場合の有効分岐因子（→ 3.6.1）は\(b^\epsilon\)となる。
目標状態が複数ある場合、特に\(\epsilon\)よりも近いものが複数ある場合はさらに計算量が増える。
また、たとえ誤差がなかったとしても無差別に近い状態が大量に存在する場合はほとんど幅優先探索と変わらなくなってしまう。

とはいえ空間的複雑性の方が問題としては深刻。

3.5.3　メモリ制限ヒューリスティック探索Memory-bounded heuristic search

A*探索のメモリ消費を減らす最も簡単な方法は、反復深化の方法を適用すること。
そうしてできたのが、反復深化A*探索iterative-deepening A*, IDA*である。
反復深化深さ優先探索では徐々に深さを大きくしていったが、IDA*探索では\(f\)コストをもちいる。
また、打ち切り値としても\(f\)コストを用いる。
段階コストが一定単位の値をとるような多くの問題では実用的だが、段階コストが連続的な値をとる場合は反復深化の統一コスト探索と同様の問題が生じる。

標準的な最良優先探索を単純な再帰関数で模倣するものとして、再帰的最良優先探索recursive best-first search, RBFSがある。
これは下図のように進む。

Figure 3.27

3.5.2の図（Figure 3.24）と同じ順番で展開されているが、フロンティアを丸ごと記憶する代わりに経路上の各ノードの子ノード中で2番目に見込みのあるノードの\(f\)値を記憶することにし、メモリ消費を線形linearの水準に抑えている。

function Recursive-Best-First-Search(problem) returns a solution, or failure
return RBFS(problem, Make-Node(problem.Initial-State), ∞)
function RBFS(problem, node, f_limit) returns a solution, or failure and a new f-cost limit
if problem.Goal-Test(node.State) then return Solution(node)
successors ← []
for each action in problem.Actions(node.State) do
add Child-Node(problem, node, action) into successors
if successors is empty then return failure, ∞ // 子ノードが存在しない場合は、候補から外す
for each s in successors do // 子ノードの\(f\)値を設定。もしあれば前回の値で更新
s.f ← max(s.g + s.h, node.f)
loop do
best ← the lowest f-value node in successors // 子ノード中で最も\(f\)値が低いものを選択。それぞれの\(f\)値は変化していくため、bestに選ばれるノードも変化していく
if best.f > f_limit then return failure, best.f // \(f\)値最小の子ノードの\(f\)値がf_limitを超えていたらfailureを返す。そして、呼び出し元で、親ノードの\(f\)値にこのときの\(f\)値がセットされる
alternative ← the second-lowest f-value among successors // 子ノード中で2番目に低い\(f\)値を取得
result, best.f ← RBFS(problem, best, min(f_limit, alternative)) // 再帰呼び出し（min(f_limit, alternative)を超えない範囲で探索）
if result ≠ failure then return result // 再帰呼び出し先で解が見つかった場合はそれを返す。失敗（打ち切りも含む）の場合は次のループへ
図（Figure 3.27）中ではノード上部の矩形内にf_limitが示されている。
また、再帰呼び出しRBFS関数の戻り値としてbest.fの値が更新されている点にも注意。

RBFS探索は\(h(n)\)が適格であれば最適性を満たす。
空間的複雑性は一次の水準に抑えられているが、進んで戻ってを繰り返すので時間的複雑性は小さくない。

IDA*探索やRBFS探索は非常にメモリ消費が少ないが、メモリも最大限に活用することで時間的複雑性を削減することができる。
そうしてできたのが、メモリ制限A*探索memory-bounded A*, MA*や、簡易MA*探索simplified MA*, SMA*である。
SMA*探索では、メモリがいっぱいになるまでは通常のA*探索のように進むが、それ以降は新しいノードを記憶する度に\(f\)値が最大となっているノードをメモリから削除し、同時にRBFS探索のようにその親ノードにその\(f\)値を反映させる。
SMA*探索は、解となる経路がメモリ内に収まる限りは（到達可能ならば）完全性を満たす。
最適経路が到達可能であれば最適性も満たす。
結局のところ、最適解を探す場合、特に、状態空間がグラフ状で、段階コストが均一でなく、そしてノードの生成がフロンティアや探索済み集合の維持に比べて大変でない場合は、実際的な観点からSMA*は十分robustな探索アルゴリズムといえる。
とはいえ、候補が多数合ったりして頻繁に行ったり来たりさせられると（メモリに余裕がない状態では）その度にノードを生成しなおさなければならなくなるので、計算コストが嵩んでしまい、理論上は到達可能な解であっても実際上は時間がかかりすぎて到達できないということがあり得る。
メモリ消費と時間はトレードオフの関係にある。

3.5.4　よりよい探索のための学習Learning to search better

エージェントでよりよい探索方法を学習することは可能。
（たとえばルーマニアの経路情報のような）オブジェクトレベルobject levelの状態空間内を探索しているプログラムの内部状態をメタレベルmetalevelの状態空間として捉え、そこからメタレベル学習metalevel learningをすることができる（この種の学習に用いられる技法については、→21章）。

Figure 3.24

図では次々とノードが展開されて探索木が大きくなっていく様子が示されているが、この各ノードがオブジェクトレベルの状態を表し、(a)～(f)がメタレベルの状態を表していると見ることができる。

3.6　ヒューリスティック関数Heuristic Functions

3.6.0　（冒頭）

この節では8パズルを例に、ヒューリスティック関数について見ていく。

8パズルでは到達可能な状態数は\(9! / 2\)なので、\(9! / 2 = 181,440\)の状態を探索しなければならない可能性がある。
これはまだ現実的な数だが、15パズルとなると約\(10^{13}\)にもなってしまう。
なので、何らかのヒューリスティック関数を使って効率を上げる必要がある。

よく使われる2つのヒューリスティック関数を示す。
\(h_1 = （目標状態と比較して）間違った配置のタイルの数\)
これは適格性を満たす。
\(h_2 = それぞれのタイルの目標状態との距離の和\)
これも適格性を満たす。
タイルは縦横にしか動けないため、ここでは直線距離ではなく縦横の距離で測られる。
これを街区距離city block distanceまたはマンハッタン距離Manhattan distanceという。

Figure 3.28

この例だと\(h_1 = 8\)、\(h_2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18\)となる。

3.6.1　ヒューリスティックの精度が性能に与える影響The effect of heuristic accuracy on performance

ヒューリスティックの性能を測る方法の一つとして、有効分岐因子effective branching factorがある。これは\(b^*\)で表される。
これは、根ノードも含めた全ての生成されるノードの数を\(N + 1\)としたときに\(N + 1 = 1 + b^* + (b^*)^2 + (b^*)^3 + ... + (b^*)^d\)となる数。
もちろん、同じヒューリスティックであっても\(b^*\)は毎回変動するが、十分困難な問題であればかなり安定することが多い。
したがって、それほど多くない回数でも実験的に探索させてみることで\(b^*\)を得、それによって性能測定することができる。
ヒューリスティックの性能が高ければ高いほど、\(b^*\)は1に近づいていく。

実際に事前情報なしの反復深化探索IDS、\(h_1\)を使ったA*探索、\(h_2\)を使ったA*探索で8パズルをそれぞれ100回解かせてみた時の平均生成ノード数、平均\(b^*\)は表のようになる。

Figure 3.29


いかなるノードについても\(h_2(n) ≧ h_1(n)\)を満たす（こういう関係を、\(h_2\)は\(h_1\)を支配dominateするという）ため、基本的には常に\(h_2\)は\(h_1\)よりも優れているといえる。
ただし、\(f(n) = C^*\)となるノードが複数ある場合はそうとは限らない場合もある。
一般的にいって、ヒューリスティック関数はそれが一貫性を満たしており、かつそれ自体の計算負荷が高すぎなければ、より大きな値を返す方がより望ましいものとなる。

3.6.2　条件緩和問題からの適格ヒューリスティックの生成Generating admissible heuristics from relaxed problems

\(h_1\)や\(h_2\)みたいなものを機械的に作り出すには、元の問題のいくつかの条件を取り除いた条件緩和問題relaxed problemを考えるとよい。

8パズルにおける行動は以下のように表現できる（形式言語での表現は、→8,10章）。
タイルは、マスAが縦方向か横方向にマスBと隣接しており、かつ、マスBが空の場合に、マスAからマスBに移動できる。
この条件を、以下のように緩和することができる。
(a) タイルは、マスAが縦方向か横方向にマスBと隣接している場合に、マスAからマスBに移動できる。
(b) タイルは、マスBが空の場合に、マスAからマスBに移動できる。
(c) タイルは、マスAからマスBに移動できる。
この(a)からは、\(h_2\)（マンハッタン距離）が、(c)からは\(h_1\)（誤りタイル数）が得られる。
これらの問題は、8つの独立した問題に分解できるので、事実上、探索不要で求めることができる。

条件緩和問題における状態空間は、パターンの条件が緩和されているので、元の問題の状態空間を内包する上位集合となっている。
したがって、元の状態空間では存在しなかった経路が解となる場合もあるため、条件緩和問題における最適解のコストは元の問題の最適解のコスト以下となる。
よって、これを元にしたヒューリスティック関数は適格となる。
さらにこれは三角不等式も満たすため、一貫性も持つ。

条件緩和の方法は複数あり得るため、そういう場合は（\(h_1\)と\(h_2\)のように）複数のヒューリスティック関数が得られることになるが、どれが最も効率的かと考えなくても、以下のように単に全て同時に適用して最大のコストを返すようにすればよい。
\(h(n) = \)max\(\{h_1(n), h_2(n), ... , h_m(n)\}\)
こうすれば、適格性・一貫性を保持しつつ\(h_1(n), h_2(n), ... , h_m(n)\)の全てを支配する\(h(n)\)を得ることができる。

3.6.3　部分問題からの適格ヒューリスティックの生成 : パターン・データベースGenerating admissible heuristics from subproblems: Pattern databases

Figure 3.30

図のように、8枚のタイルのうち1,2,3,4の4枚のタイルの位置のみを考慮するようにした問題（ただし、他のタイルの移動はコスト算入する）からも、適格なヒューリスティック関数を得ることができる。
このように、元の問題を部分的に解く問題を、部分問題subproblemという。
このときのコスト計算は、全ての可能な状態からのコストを予め計算してデータベースに保存しておけばよい。
このようなデータベースを、パターン・データベースpatter databasesという。
パターン・データベースを用意するには、目標状態から各状態を逆算していくとよい。

こうして複数の部分問題から得られたヒューリスティック関数も、組み合わせて最大コストを取ることで、より効率的なものとすることができる。

互いに独立な部分問題であれば、それぞれから得られたヒューリスティック関数の値を和をとっても適格なヒューリスティック関数となる。
こういう関係を互いに素disjointという。
たとえば1,2,3,4のタイルの位置のみ考慮する部分問題と、5,6,7,8のタイルの位置のみ考慮する部分問題は、両方同時に影響を与える動きが存在するため互いに疎とはいえないが、他のタイルの動きを無視するようにすれば互いに疎となる。

3.6.4　経験からのヒューリスティックの学習Learning heuristics from experience

経験からもヒューリスティック関数を得ることができる。
たくさん問題を解いて各状態とそこからの最適解、そして経路コストをデータとして保存し、そこから18章や21章にあるような方法で学習させることができる。
各状態の何らかの特徴fecturesを用いることで、推測の足しにすることもできる。

たとえば、たくさん問題を解いて各状態の\(h_1\)の値と最適経路コストの比を求めることで、より正確なヒューリスティック関数が得られる可能性がある。
\(h_1\)と\(h_2\)を両方使って、\(h(n) = c_1×h_1(n) + c_2×h_2(n)\)というふうに（通常は線形に）組み合わせるということも可能。
ただし、これは適格性・一貫性を満たすとは限らない。