プログラミングメモ - 「ラベル番号の対応表作成問題」ひとつの解答

2010/07/01

随分前に,「ラベル番号の対応表作成問題」なる話を書いたんですけれど(参照:qune: プログラミングメモ - ラベル番号の対応表作成問題),問題を投げっぱなしじゃアレなので,ひとつの解答を書いておきます。これが,効率的なソリューションかというと,そういうわけではありません。

例えば,初回のスキャンでラベル付けした結果,対応表が次のようにできたとします。

1 = 5
4 = 2
6 = 1
3 = 2

こいつの対応関係をまとめればいいわけですけれど,こゆのはマトリックスで管理するのがいいんだと思います。ラベルの対応関係を L とすると,対応関係は次のようにまとめられます。

L | 1 2 3 4 5 6
--+------------
1 |         + +
2 |     + +
3 |   +
4 |   +
5 | +
6 | +

"+" 記号を置いたところが,対応関係のあるラベルのマークです。例えば,1 = 5 の条件があるから,(1, 5) と (5, 1) に "+" マークをつけています。これは機械的にできます。

続いて,自分自身は必ず等しいので,対角要素にマークをつけることができますよね。こんな風に付ける。

L | 1 2 3 4 5 6
--+------------
1 | -       + +
2 |   - + +
3 |   + -
4 |   +   -
5 | +       -
6 | +         -

分かりやすくするために,対角要素は "-" でマークしました。

あとは,推移的な関係をマークすればオッケーですよね。推移的な関係というのは,1 = 2 と 2 = 3 がある場合における,1 = 3 の関係のことです。こいつを見つけ出してマークをつけましょう。

で,これなんですけれど,対応関係の行列の性質をちと踏まえれば,割と簡単にアルゴリズムを構成することができます。この対応関係って,結局,同じグループに入るラベル番号間では,対称になるはずなんですよね。だから,対象になるように,空きを埋めていけばいい。擬似コードで書くと,こんな感じになるんですけれど,巷では Floyd-Warshall (F-W) algorighm なんて呼ばれているそうです(※ F-W algorighm と呼ばれるもんには,いろいろと種類があるのでぐぐるときは注意)。

for i = 1 to n
  for j = 1 to n
    if <emphasis role="strong">L</emphasis>[j, i] == 1 then
      for k = 1 to n
        <emphasis role="strong">L</emphasis>[k, j] = <emphasis role="strong">L</emphasis>[k, j] | <emphasis role="strong">L</emphasis>[k, i]

結局,このアルゴリズムを通すと,マトリックスは次のようになります。上のアルゴリズムを適用した結果,埋まった箇所を "x" でマークします。

L | 1 2 3 4 5 6
--+------------
1 | -       + +
2 |   - + +
3 |   + - x
4 |   + x -
5 | +       - x
6 | +       x -

これでできあがり。あとは,2回目のスキャンでこの表を参照にしながら,ひとつのラベル番号に統一すればオッケーです。

このアルゴリズムの問題は,なんといっても,オーダーにして O(n3) となるところ。また,記憶領域も行列を記憶しておく分で,n2の領域が必要です。もっとも,ループ内で行われていることは大したことないし(or 演算しているだけ),テーブル要素も 0/1 の 1bit で足りるので,実用上は問題ない場合の方が多い気もするんですが。

もっといいやり方はもちろんあるんでしょうけれど,とりあえず,解答例ということで。

Site Navigation
SNS Accounts (@aian)

普段はここら辺に住んでいます.