問題解決(後半)

人工知能の続き。
人工知能　第2版 (情報工学入門シリーズ)の第二章の勉強。

人工知能　第2版 (情報工学入門シリーズ)

2.4 知識を用いた解の探索

• 知識を用いる効果
  • 系統的探索は、解が存在すれば必ず見つけることができるが、状態空間が大きくなるとこの方法では目標状態が存在する位置によって解を見つけるまでの時間が非常に長くなる。
  • 探索すべき状態空間を削減する方法の一つに、その問題に関するさまざまな情報(知識)をうまく利用する方法がある。
  • 迷路問題において、出口の方向がわかっていれば、なるべくその方向にある交差点に向かうという方針は他の場合より出口を発見できる可能性が高いことを、人間は経験的知識として知っている。また。この知識にも例外があることや、この経験的知識がうまく行かない場合の対処の方法があることも知っている。
  • 経験的知識を用いて、状態空間の探索の効率を向上させる方法は、知識を用いた解の探索あるいはヒューリスティック探索と呼ばれている。
  • 知識を用いた解の探索には、探索における経験的知識を表現するためのヒューリスティック関数を利用する。
  • 知識を用いた解の探索の例
• 山登り法
  • 目標状態の探索を山頂を目指す山登りにたとえ、ヒューリスティック関数h(q)を現在地のqの標高として考えれば直感的に理解できる。
  • 山登り法は縦型探索に似ているが、途中の状態を記録するスタックSをもたず、目標状態に向かう。したがって、このままでは探索に失敗する可能性が高い。
  • この点を改良することにより、より効率的に解を探索する手続きの研究が行われている。
• 制約条件を用いた探索の効率化
  • 探索効率を上げるための別の方法に、解の探索に制約を加える手法がある。
  • 制約とは、問題の表現において定義される状態を、「許容状態」と「禁止状態」に分離し、探索の過程で禁止状態に移る作用素は適用しないという条件を設けることである。この制約により、解の探索領域を減らすことができれば、探索効率は向上する。
  • 解の探索効率を上げることと、解の精度を上げることは一般にトレードオフの関係にある。
• 解の条件
  • 一般に一つの状態に対して適用可能な作用素は複数存在するので、問題解決の効率はこの作用素の選び方に依存する。作用素の適用条件にうまい制限を加えることにより次の状態の選択を制御することができ、この表現の仕方により効率の良い解の探索を行うことができる。作用素の適用条件のことを作用素の前提条件とよぶ。
  • また得られた解が満たすべき条件を与え、得られた解についてこの条件を適用し、最終的にそれが解として妥当かどうかを調べることが必要である。これを解の拘束条件と呼ぶ。
  • 効率的な解の探索を行うためには、前提条件と拘束条件のバランスを適正に決める必要がある。
  • 一般に人間は経験的知識を用いて適正な前提条件を決定することができる。

2.5 大規模な問題の解決

• 問題の分割
  • 現実の問題を解くときは、そのまま一つの状態空間で表現すると、あまりにも大きな状態空間になり、解の探索効率が低下するおそれがある。
  • もとの問題をより簡単ないくつかの問題(副問題)に分割し、それらを個別に解いて最後に統合することによりもとの問題全体を解けば、解の探索効率を全体的に向上させることが期待できる。これを問題の分割という。
  • 人工知能では、問題分割の経験的知識を利用することにより、効率的な問題解決の手続きを与えることを目的としている。
• AND/OR木による問題の分割
  • 問題の分割には二つの種類がある。
  • OR分割：問題Xを解くためには副問題Aか副問題Bのいずれか一つが解ければよいという場合、問題Xは副問題Aと副問題BにOR分割されるという。この場合、状況に応じて解きやすい副問題を解けばよい。
  • AND分割：問題Xを解くために副問題Aと副問題Bの両方を解かなければならない場合、問題Xは副問題Aと副問題BにAND分割されるという。
  • ある問題がいくつかの副問題に分割された場合、その問題を親問題、吹く問題を子問題とよぶ。解くべきもとの問題を源問題といい、これ以上分割できない問題を素問題という。素問題は解がそのまま簡単に求められる問題である。
  • 可解な問題のみから構成されるAND/OR木の部分木を解木とよぶ。源問題を根とする解木が存在すれば源問題は解が存在する(可解である)。
  • 源問題から出発して解木を構成していく過程をAND/OR木の探索という。
  • AND/OR木の探索とは、Sを根とする部分木のなかで解木を探索する問題である。
• 再起表現による問題の分割
  • 効果的な問題の分割方法の一つに再起表現による問題の分割がある。再起表現による問題の分割とは、問題Pの部分問題に、問題Pと同じ形式の問題が現れることである。このような問題は数多く存在するが、その一つに「ハノイの塔」問題がある。
  • 再起表現を利用して問題を分割すると問題解決の手続きを表現することが容易になる。

今日はここまで。
飛ばしすぎたので、しばらく復習しながら覚えます。