備忘録

ここ数日つらつら考えていた問題についてちょっと前進した気がするのでここに書く。

2つの重み付きグラフ

• G1=(V1,E1)
• G2=(V2,E2)

が与えられ、両者のノードの和集合V1∪V2の任意の2要素の間に大小関係が定義されているとする(早い話、枝だけでなくノードにも重みがつけられていると考えて良い)。
また、G1のノード数≦G2のノード数とする。
このとき、次の条件を満たすG2の部分グラフG'を求めよ。

• G1と同じ形である(i.e. G'のノードと枝をG1にぴったり過不足無く重ね合わせられる)
• ぴったり重ね合わせたときの重なり合うノード同士が、全て制約条件 G1のノード≦G2のノード を満たす
• ぴったり重ね合わせたときの重なり合う枝の重みの差の絶対値の合計(Dと置く)が最小値をとる

これはG2の部分グラフの中から、G1と同形で最もよく似た部分グラフを、ノードの大小に関する制約付きで求める問題。
基本的にノード同士の対応を総当たりして解くしかないと思うが、隣接行列表現により枝刈りできる。たとえば

• G1の隣接行列Xを作成し、行を1(接続)の数の降順でソート、さらに列をノード数昇順でソート
• G2の隣接行列Yを作成し、行を1(接続)の数の降順でソート、さらに列をノード数昇順でソート

とした上で、まず次のテストを行う。

• XとYの行を上から1行づつ比較して、Xの行i内の接続の数＞Yの行i内の接続の数が1回でも成立したら、解非存在。
• XとYの行iにおいて、先頭から順に値が1の列同士を対応づけていったとき、G1のノード≦G2のノード を満たせなくなったなら、解非存在

上記テストにパスした場合に限り、Yの列を(G1のノード≦G2のノード を満たす範囲内で)総当たりで入れ替えてチェックする。列はノードの大小昇順でソート済みだから、組み合わせの数は、Xがm次正方行列だとすると、最悪m*(m-1)/2、期待値としては(m/2)^2ぐらいだと思う。
また、その際、個々のチェックは、Xがm次正方行列、Yがn次正方行列だったなら、(m-1)次正方行列X'と(n-1)次正方行列Y'について同じ問題を解く小問題に帰着するので全体を再帰的手順として書き下せる。
これにDに関する上限カットを組み合わせてさらに効率化することは容易だ。

まああんまりたいした話じゃないけど、この計算がいずれ戦いの鍵を握る日が来る(ぉ