Entry

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

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 L[j, i] == 1 then
      for k = 1 to n
        L[k, j] = L[k, j] | L[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 で足りるので,実用上は問題ない場合の方が多い気もするんですが。

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

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN