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

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

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

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

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

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

#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(*s);
  ...
  (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) fringe->clear();
    }
    else expand(fringe, s, combiner);
    delete s;
    search(fringe, combiner, findAll);
  }
}

int main ()
{
  STATUS* s=new STATUS...
  FRINGE fringe;
  fringe.push_back(s);
  search(&fringe, &FRINGE::push_front, false); //深さ優先
  //search(&fringe, &FRINGE::push_front, true); //解をすべて見つける
  //search(&fringe, &FRINGE::push_back, false); //幅優先
  //search(&fringe, &FRINGE::push_back, true); //解をすべて見つける
  return 0;
}

数独を解く場合には、typedef vector<vector<int> > STATUS;でいいでしょう。関数については、実行結果を参照してください。

コメントと空行を取り除くと、（Mathematicaの時は含めなかった）実行部分を含めて約90行です（実行結果）。

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

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

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

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

BAR bar=&Foo::func;

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

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

参考：プログラマの道具箱（深さ優先探索と幅優先探索） Mathematica編

Related posts:

1. 油売り算(Mathematica)
2. プログラマの道具箱（深さ優先探索と幅優先探索） Mathematica編
3. プレゼント交換の手伝い
4. 数独で見るRuby（とMathematica）のパワーと表現力
5. Puzzles for Hackers