2012年1月13日金曜日

submodular toolbox がうまく使えていない様子

最密部分グラフを求める計算で、submodular 関数として計算することができるようなので、やってみているのであるが、現状ではうまくいっていない。

今回は submodular function optimization toolbox を利用している。
http://www.mathworks.com/matlabcentral/fileexchange/20504-submodular-function-optimization/content/sfo/sfo_min_norm_point.m
入力として作ったグラフは、前回と同じく

[0,1]x[0,1] の2次元正方形にランダムに100個のノードをばら撒いて、[0.1,0.5]x[0.2,0.6] に 20 個をばら撒く。
このとき、距離が 0.15 以下となるノード同士を枝でつなぐ。

これでできた距離行列を distanceMatrix としたときに、


    [m,n] = size(distanceMatrix);
    [findI,findJ,findV] = find(distanceMatrix);
    findV2 = ones(length(findV),1);
    distanceMatrix1 = sparse(findI, findJ, findV2, m, n);

    fn = @(nodeSet) -full(sum(sum(distanceMatrix1(nodeSet,nodeSet))));
    F = sfo_fn_wrapper(fn);

として関数ハンドラを生成している。
つまり、すべての枝の重さを1として、nodeSet で与えられたノードの集合に両端が含まれる枝の数をマイナスしたものを最小化する。
これで、
[bestSet] = sfo_min_norm_point(F,1:n);
とすると、最密部分グラフを構成するノード集合が得られる予定であったのだが、実際にやってみるとノードが2個か3個になってしまう。

Toolbox を正しく利用できていないのか、toolbox のアルゴリズムに間違いがあるのか、それをまずは切り分ける必要がある。

今日の作業内容: toolbox 2h + 論文読み 3h
今日のランチ:らく 鶏の照り焼き定食
明日の予測作業時間:4h

0 件のコメント:

コメントを投稿