交差点問題

大学のアルゴリズムとデータ構造という授業で題材になってた問題。それにBGL(Boost Graph Library)で取り組んでみた。

左図の様な交差点がある。

全ての進路に信号が設置してある。

矢印方向にしか進むことができない。

交差する進路は同時に信号を点灯することができない。

効率良く車を進めることのできる点灯の仕方を求めよ。

という問題。

まず、こういった現実の問題を数学のモデルに置き換える。それが右図。

ABなどの一つのノードがA->Bなどと進む進路の信号を表す。

交差する進路は互いに線で結ばれている。

同時に点灯する信号のノードを同じ色で塗る。

線で結ばれているノードは同じ色で塗られていてはいけない。

色の数が最も少なくなるような塗わけかたを探せ。

という感じで、モデル化することができる。"色"という概念で考えるのは四色問題がその起源なのかな。

んで、この問題は「NP完全問題」らしい。名前は聞いた事があるけどよく知らない。
要するに総当たり以外の方法しか現在では知られてなくて、理論的には解けるけど計算機では現実的な時間内に解けないよね。ということらしい。

欲張りアルゴリズム(Greedy algorithm)

最適解を求めるのは大変だから近似解を効率良く求める事を考えようというのを発見的アルゴリズムという。遺伝的アルゴリズムとかもこの類かな。

欲張りアルゴリズムとは

塗れるノードを最初にすべて塗ってしまう。
塗れなくなったら色を変えて同じ事を繰り返す。
すべてのノードに色を塗ることができたら終了。

の様に近似解を求める方法。
これをBGLで実装してみた。

実装

#include <iostream>
#include <utility>
#include <algorithm>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<
  vecS, 
  vecS, 
  undirectedS, 
  property<vertex_color_t, int>
  > signal_graph;


struct is_paintable
{
  typedef graph_traits<signal_graph>::vertex_descriptor vertex_type;

  is_paintable(signal_graph& g) :g_(g) {}
  bool operator()(const vertex_type& v, int color) const {
    graph_traits<signal_graph>::adjacency_iterator vbeg, vend;
    property_map<signal_graph, vertex_color_t>::type 
      colors = get(vertex_color_t(), g_);
    for(tie(vbeg, vend) = adjacent_vertices(v, g_); vbeg != vend; ++vbeg){
      if(colors[*vbeg] == color) return false;
    }
    return true;
  }

private:
  signal_graph& g_;
};

int main(int, char*[]){
  enum signals {AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED, NUM};
  const int num_vertices = NUM;

  typedef std::pair<int, int> edge;
  edge edges[] = 
  {
    edge(AB, BC), edge(AB, BD), edge(AB, DA), edge(AB, EA),
    edge(AC, BD), edge(AC, DA), edge(AC, DB), edge(AC, EA), edge(AC, EB),
    edge(AD, EB), edge(AD, EB), edge(AD, EC),
    edge(BC, DB), edge(BC, EB), 
    edge(BD, DA), edge(BD, EB), edge(BD, EC),
    edge(DA, EB), edge(DA, EC),
  };

  const int num_edges = sizeof(edges)/sizeof(edges[0]);
  signal_graph g(num_vertices);
  for(int i = 0; i < num_edges; ++i){
    add_edge(edges[i].first, edges[i].second, g);
  }

  property_map<signal_graph, vertex_color_t>::type 
    colors = get(vertex_color_t(), g);

  for(int i = 0; i < num_vertices; ++i){
    put(colors, i, 0);
  }

  is_paintable pred(g);

  graph_traits<signal_graph>::vertex_iterator vbeg, vend;
  tie(vbeg, vend) = vertices(g);
  graph_traits<signal_graph>::vertex_iterator it;

  int color = 0;
  int painted = 0;
  while(painted < num_vertices){
    ++color;
    for(it = vbeg; it != vend; ++it){
      if(colors[*it] == 0 && pred(*it, color)){
        ++painted;
        put(colors, *it, color);
      }
    }
  }

  for(it = vbeg; it != vend; ++it){
    cout << "signal " << *it << ": " << colors[*it] << endl;
  }
  cout << "total: " << color << endl;
  return 0;
}

下が出力。

signal 0: 1
signal 1: 1
signal 2: 1
signal 3: 1
signal 4: 2
signal 5: 2
signal 6: 3
signal 7: 3
signal 8: 1
signal 9: 2
signal 10: 4
signal 11: 4
signal 12: 1
total: 4

4色で塗れるらしい。このグラフはAC,DA,BD,EBの4つのノードがすべて互いに結ばれているのでこの4つのノードだけで必ず4色いる。これを4クリークと言う。

んで、必ず4色以上必要で答えが4と出たのだから最適解の一つが得られたということ。なるほど。これは面白い。

BGL

BGLは初めて使ったので、なかなか難しかった。is_paintableの実装とかめちゃめちゃ非効率だし、コードもめちゃめちゃ汚いなぁ。
なかなか複雑なライブラリだけど、結構面白いということが判明したので、これからも何か面白い問題があったら使ってみよう。

イテレータの扱い方はとても面白い。

graph_traits<Graph>::vertex_iterator vbeg, vend;
tie(vbeg, vend) = vertices(g);
for_each(vbeg, vend, hogehoge);

みたいな感じで、イテレータ範囲をpairで返す関数の戻り値をtie(tuple)で受け取り同時に初期化する。
これはlattice_systemの実装でも使いたいテクニックだけど、これではまだまだ不満。
なんというかコードが美しくない。
そして、一時オブジェクトにvbeg, vendという名前を付けてしまうことは最適化されにくくなることでもある。というか、tieの引数にするときにvbeg, vendに実体が必要だから間違い無く無駄なデフォルトコンストラクタの呼出しが起こるはず。

for_each(vertices(g).first, vertices(g).second, hogehoge);

と書いてしまうと、今度はverticesの呼出しが2回起こってしまうし、first/secondってのは見た目が悪い。
上のコードは

for_each(vertices(g), hogehoge);

の一行で書けて欲しい。こうすると無駄な一時オブジェクトが作られなくなるはずだ。

これは前から思ってたことで、STLのインターフェースはみんな好きじゃない。例えば

vector<Hoge> vec;
for_each(vec, hogehoge);

と書けて欲しい。vectorならまだいいだけど、vertices(g)みたいにイテレータを動的に生成する仕組みを使いたい場合はSTLのインターフェースは非効率的。
んで、boost.rangeというライブラリがこれの解決策になりそう。
但しfor_eachとかすべて新しく書かなきゃいけないけど(^^;もうあるのか??