クラスタリングによる迷路作成アルゴリズム

Japanese / English

はじめに

 クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。

注意:ここで言う「クラスタリング」は同値関係をつなぐもので、 データ解析で良くでてくるクラスタリング、つまり情報空間上に散らばっているデータ点を 適当に似ているもの(近いもの)同士で分類する手法ではありません。


クラスタリングとは

 ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として

などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。

 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、

 友達の友達は友達である
と定義すると、友人関係は同値関係を作る。 その上で、 という情報が分かっていると、 この情報から、

という関係がわかる。このように、 何かと何かがつながっているという情報を処理して、 全体をグループわけする作業がクラスタリングである。 物理面での応用としては、浸透問題などの臨界現象や、 粉体のForce Networkなどの解析にも用いられる。


アルゴリズム

 クラスタリングアルゴリズムはいくつか知られているが、 そのうち一次元配列を使った簡単な例を紹介する。

 この作業はリンクリストの作成である。 下図では、6つの要素からなるリンクリストが、 クラスタリングにより2つにグループ分けされた様子を示す。 最初、すべての要素のリンクは自分を指しているが、 クラスタリングにより、必ず番号の低い側(図では左側)にリンクされる。 このとき、自分からたどっていったリンクの終点の要素の番号が 自分のクラスタ番号となる。

 以上の作業をコードで書くと以下のようになる。 pair1[i]とpair2[i]に同値関係が入っているとして、 関数clusteringを呼んでやればクラスタリングができる。 あとは int get_cluster_numberに要素番号を入れれば その要素のクラスタ番号が返ってくるので、あとは 最大クラスタを探すなり、クラスタの数を数えるなりすることができる。

//---------------------------------------------------------------------------
int cluster[N];
int pair1[N_PAIR],pair1[N_PAIR];
//---------------------------------------------------------------------------
int
get_cluster_number(int index){
  int i = index;
  while(i != cluster[i]){
    i = cluster[i];
  }
  return i;
}
//---------------------------------------------------------------------------
void
clustering(void){
  for(int i=0;i < N;i++){
    cluster[i] = i;
  }
  for(int i=0;i < N_PAIR;i++){
    int i1 = pair1[i];
    int i2 = pair2[i];
    i1 = get_cluster_number(i1);
    i2 = get_cluster_number(i2);
    if(i1 < i2){
        cluster[i2] = i1;
    }else{
      cluster[i1] = i2;
    }
  }
}
//---------------------------------------------------------------------------


迷路作成アルゴリズム

 では、クラスタリングを迷路作成に応用してみよう。 迷路を作成するには、基本的には枝をつけるだけでよい。 しかし、適当に枝を伸ばすと、 「入り口からいけない場所(死に領域)ができる」 「ループができてしまい、解答が一意でなくなる」 などの問題ができてしまう。 そこで、クラスタリングを使って解答のパスが一意で、 なおかつ死に領域ができないことを保証する。

 迷路の作成アルゴリズムは以下の通り。

以上で死に領域とループがない迷路の完成である。


迷路作成例

 以上のアルゴリズムを用いて、「解くと絵が浮かび上がる迷路」を 作ることができる。やり方は簡単で、先に解答のパスを作り、その部分だけ クラスタリングしてから壁を壊し始めれば、ループを作らない保証から 与えた解答が最短距離となる迷路が出来上がる。 以下の図はそのようにして作成した迷路の例である。 左図の迷路を解くと、右図のような絵が浮かび上がる。

 上記の迷路は、クラスタリングアルゴリズムによる迷路作成エンジンを実装したソフト 「迷次郎」により作成した。


おわりに

 クラスタリングアルゴリズムを応用し、 「解くと絵が浮かび上がる迷路」を 作成してみた。クラスタリングはあらゆるネットワークの解析に使えるし、 コードも20行もないので知っていて損はないアルゴリズムである。

追記

 誤解している人がいるようなのでいくつか追記。 クラスタリングアルゴリズムというのは僕が考えたものではなく、かなり古いアルゴリズム。 実装方法はいくつかあるが、上記ではそのうちもっとも簡単なものの一つを紹介してある。 また、この記事の主眼は「迷路作成」ではなく、あくまでもクラスタリングアルゴリズムの紹介。


Rubyによるサンプルコード

 上記の説明だけじゃアルゴリズムが分かりにくいようなので、 某所用に書いたRubyによる手抜きサンプルを置いておく。 実行すると、以下のようなA4一枚の大きさの迷路をeps形式で吐き出す。

 以下はソース。単に実行すれば、同じディレクトリにmaze.epsを作成する。


Author: Hiroshi Watanabe

トップページへ戻る