コラム / AI (人工知能) / 第1章

HOME 研究室概要 コラム 周辺探索 メンバー 掲示板 リンク

第1章 探索法

 探索法とは問題解決の基礎となる手法です。ここでは木の探索法について説明します。

 探索には様々な方法がありますが、その中から比較的簡単な幅優先探索(横型探索)と深さ優先探索(縦型探索)の2つについて紹介したいと思います。

 このページの目次

1.1節 探索木の例
1.2節 幅優先探索(横型探索)
1.3節 深さ優先探索(縦型探索)

 1.1節 探索木の例

 では簡単な例を通して、 これら2つの探索の手順を見てみましょう。

探索木

図.1: 探索木

 例えば、図.1のような木構造であるとき、Sを出発点、Gを目標点とすると、幅優先(横型)探索は以下のような順番でGを探索します。節点の侯補リストを未調査の意味を込めてOPENリストと表し、調べ終わった節点は、対比的にCLOSEDリストと名づける集合に入れるものとします。

 1.2節 幅優先探索(横型探索)

 幅優先探索は、単純にいえば出発節点に近い節点から順番に探索していくという方法です。つまり、私たちが手がかりなしに探し物をするときのように、まず手近なところをすべて探し、そこで見つからなければ、次に手近なところをすべて探していくように、探索範囲をだんだん広げていくという探索法です。

  ・ OPEN = (S)  Sを調べる  Gでない  OPEN = ()  [Sを除去]
  ・ Sを展開・追加  A,B → OPEN = (A B)
  ・ Aを調べる  Gでない  OPEN = (B)  [Aを除去]
  ・ Aを展開・追加  C,D → OPEN = (B C D)  [後に挿入]
  ・ Bを調べる  Gでない  OPEN = (C D)  [Bを除去]
  ・ Bを展開・追加  G,E → OPEN = (C D G E)
  ・ 同様にC,Dを調べる  Gでない  OPEN = (G E)  [C,Dを除去]
  ・ Gを調べる  G(目標節点)である  (探索成功)

幅優先探索(横型探索)

図.2: 幅優先探索(横型探索)

 1.3節 深さ優先探索(縦型探索)

 幅優先探索に対し、深さ優先探索は、その時点で調べた節点が目標節点でない場合、さらにその先へと次々に探索していく手法です。つまり、ある節点の次に調べる子節点(枝)が複数あるとき、その一つ先にあるすべての節点を調べてから、(目標節点がなかった場合)別の子節点(枝)に戻り、また同様に探索を繰り返すようなやり方です。

  ・ OPEN = (S)  Sを調べる  Gでない  OPEN = ()  [Sを除去]
  ・ Sを展開・追加  A,B → OPEN = (A B)
  ・ Aを調べる  Gでない  OPEN = (B)  [Aを除去]
  ・ Aを展開・追加  C,D → OPEN = (C D B)  [先頭に挿入]
  ・ Cを調べる  Gでない  OPEN = (D B)  [Cを除去]
  ・ Cを展開(なし)  Dについても同様  OPEN = (B)
  ・ Bを調べる  Gでない  OPEN = ()  [Bを除去]
  ・ Bを展開・追加  G,E → OPEN = (G E)  [先頭に挿入]
  ・ Gを調べる  G(目標節点)である  (探索成功)

深さ優先探索(縦型探索)

図.3: 深さ優先探索(縦型探索)

 このようにして、幅優先探索と深さ優先探索は行われます。

 これら幅優先探索と深さ優先探索の優劣は一般的には決められないことは明らかです。強いていえば、その問題領域における何らかの知識なりに基づいて、目標節点が探索木の浅いところにあることがわかっているならば幅優先探索が有利であり、逆に深いところにあることがわかっているならば深さ優先探索が有利であるといえます。

 しかし、一般的に、このような判断をするだけの情報がないときは、どちらがよいかは言えないでしょう。

ページの上へ 上のページへ 次の章へ


企画・製作 村上・泉田研究室 HP製作委員会(2001)
ご意見・お問い合わせは、こちら までどうぞ。