プログラマの道具箱(深さ優先探索と幅優先探索) C++編


参考:数独の平凡な解法(C言語Mathematica

Mathematicaで実装した深さ優先探索と幅優先探索をC++に移植してみましょう。

深さ優先探索と幅優先探索

探索木のノードを表現する型をSTATUS、そのリストをFRINGE、FRINGEにノードを追加するメンバ関数をCOMBINERとします。

データ構造はツリーではなくリストを使います。候補ノードを、スタックで管理すれば深さ優先探索、キューで管理すれば幅優先探索になるわけですが、std::stackとstd::queueにおいて、要素を取り出すメソッド名が同じではないため多態性を利用できません。ですから、ノードはstd::listで管理し、要素はメンバ関数pop_front()で常に先頭から取り出すことにします。

要素を追加する際に、メンバ関数push_front()を使えば深さ優先探索に、push_back()を使えば幅優先探索になります。探索に使う関数search()は、引数としてこれらのメンバ関数へのポインタを取るようにしましょう。

道具箱には次のようなコードを入れておけばいいでしょう。

#include <iostream>
#include <list>

using namespace std;

typedef ... STATUS; //ノードのための型
typedef list<STATUS*> FRINGE; //ノードを管理するオブジェクトの型
typedef void (FRINGE::*COMBINER)(FRINGE::const_reference); //メンバ関数へのポインタ

//解を報告する手続き
void report(STATUS* s)
{
  ...
}

//解かどうかを判定する述語
bool goal(STATUS* s)
{
  ...
}

//探索を深める
void expand(FRINGE* fringe, STATUS* s, COMBINER combiner)
{
  ...
  STATUS* newStatus=new STATUS...
  ...
  (fringe->*combiner)(newStatus);
}

//探索の本体
void search(FRINGE* fringe, COMBINER combiner, bool findAll)
{
  if (fringe->size()!=0) {
    STATUS* s=fringe->front();
    fringe->pop_front();
    if (goal(s)) {
      report(s);
      if (!findAll) {
        while (!fringe->empty()) {
          STATUS* tmp=fringe->front();
          fringe->pop_front();
          delete tmp;
        }
      }
    }
    else expand(fringe, s, combiner);
    delete s;
    search(fringe, combiner, findAll);
  }
}

int main ()
{
  STATUS* s=new STATUS...
  ...
  FRINGE* fringeP=new FRINGE();
  fringeP->push_back(s);
  search(fringeP, &FRINGE::push_front, true); //depth-first search
  //search(fringeP, &FRINGE::push_back, true); //breadth-first search
  return 0;
}

数独を解く場合には、typedef int STATUS;でいいでしょう。関数については、実行結果を参照してください(実行する場合には、スタックサイズを大きくする必要があるかもしれません)。

コメントと空行を取り除くと、(Mathematicaの時は含めなかった)実行部分を含めて約100行です。

C++に関する必要な知識の大部分は、拙著『Microsoft Visual C++入門』にまとめてありますが、深さ優先・幅優先を指定するために必要なメンバ関数へのポインタの使い方は確認しておきましょう。

クラスFooのオブジェクトのメンバ関数へのポインタには、次のように名前(ここではBAR)を付けておくのが簡単です。

typedef 戻り値の型 (Foo::*BAR)(パラメータリスト)

Fooののメンバ関数funcへのポインタbarは、次のように取得できます。

BAR bar=&Foo::func;

次のようにして、クラスFooのオブジェクトfooのメンバ関数を、ポインタbarを使って呼び出します。

(foo->*bar)(引数リスト)

参考:プログラマの道具箱(深さ優先探索と幅優先探索) Mathematica編

プログラマの道具箱(深さ優先探索と幅優先探索) C++編” への2件のコメント

  1. 通りすがりさん
    5番目はあたっている気がします。
    速さについても何か入れた方がいいでしょう。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です