GED (Graph Edit Distance) を調べてみる

グラフ間の編集距離。類似度に使われるわけだけど、ノードが増える度に指数上に計算量が増えるらしいのでいくつも論文がでているもよう。画像認識とかに使われているみたい。

Bipartite Graph Matching for Computing the Edit Distance of Graphs
http://videolectures.net/gbr07_riesen_bgm/

の動画とスライドを何回も見た。どうやら、Assignment問題(Algorithm::Munkres)というのに置き換えて解く。
この問題も初めて知りました。Munkresアルゴリズムは追ってないけど、モジュールに詳しい説明があるのでなんとなくわかった。
ところでCostはどうやって求めるのだろう。というより、コスト関数は自前で用意するのかな。。

A*探索とかも使うらしい。響きは懐かしいが何をやっているかさっぱり覚えていない。勉強しよう。