問題解決(前半)

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

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

2.1 問題解決とは

• 問題解決とは、対象とする問題に関する知識、データ、手続きなどを用いて、計算や推論を行い、与えられた問題に対する解を見つけ出すことである。
• 人工知能が議論の対象とする問題解決とは解を得るための手順がアルゴリズムとして確立されていない問題領域で、経験的知識(ヒューリスティック)を利用して妥当な解を発見することである。このような考え方で問題解決を行う場合は、次の二つの作業が必要となる。
  • 問題の表現：対象の世界を経験的知識が適用可能で、かつコンピュータで処理可能な形式で表現する。対象世界を表現するさまざまな特徴や条件を変数や規則で表し、それらの関係をグラフや表などで表す。一般に対象世界の状態の変化は状態空間と呼ばれるグラフで表され、問題解決とは、状態空間のなかで初期状態から解となる目標状態(ゴール)に至る経路を見つけることとして定義される。
  • 解の探索：解とは、初期状態から目標状態に至る経路のことであり、解の探索とは、状態空間のなかからこの経路を効率よく見つけ出すことである。人間は直感やさまざまな経験的知識を利用して、短い時間で目標状態に至る経路を発見することができる。この発見的手法をモデル化することが人工知能における解の探索である。

2.2 状態空間における問題の表現と解の探索

• 問題を正確に解くためには、その解を探すための可能な道筋を調べつくすことが必要である。この道筋は、状態と作用素により表される。
• 状態とは問題を解く各段階における対象のありさまや条件の表現であり、作用素とは、ある状態からほかの状態へ移行するための手段や現象を意味する。
• 状態空間とは初期状態からすべての作用素を適用することにより到達可能なすべての状態とその経路の集合である。
• 状態空間を計算機で処理可能な形式に記述するためには、対象の問題の性質を表すために最も適したモデルを考える必要がある。これらは一般にはグラフ、行列、集合、論理など数学的なモデルを利用して定義されている。
• 一般に、ある状態に対して適用可能な作用素は複数存在する。このなかでどの作用素を選び出すかで、探索の経路は異なる。対象とする状態に対して、適用可能な作用素の集合から一つの作用素を選び出す基準の探索を戦略という。
• 戦略をもたない探索方法を盲目的探索という。盲目的探索は、手続きは簡単であるが、解を見つける保証が無く、また探索効率も悪い。

2.3 系統的な解の探索

• 最も単純な解の探索法は、初期状態からはじめて、適用可能な作用素をランダムに一つだけ選び、これを繰り返しているうちに目標状態を見つける盲目的探索である。これに対して初期状態から到達可能なすべての状態を調べる方法として系統的探索という方法がある。これは解が存在すれば必ず見つけ出すことができる。しかし、複雑な問題であれば状態空間のサイズ(状態の数)がきわめて大きくなり、解を見つける効率が著しく低下する恐れが強い。
• 人間が問題解決に際して用いる経験的知識を利用し、解の探索効率を向上させるのが知識を用いた解の探索である。
• 系統的探索の最も基本的な方法には、その探索順序により縦型探索(深さ優先探索)と横型探索(はば優先探索)がある。
  • 縦型探索：初期状態から離れた状態を優先的に調べる探索方法である。探索の過程で許容状態に遷移できる作用素が存在しない状態を行き止まり状態という。行き止まり状態になると解を探索するために、それまでの経路を次の探索を再会できる状態まで後戻りしなければならない。これをバックトラックという。解の探索ではこのバックトラックを効率よく制御することが重要である。このために、スタックが用いられる。
  • 横型探索：初期状態に近い状態から優先して調べる探索法である。新たに調べるべき状態の記録にキューを用いる。

今日はここまで。
残りは後日。