RSS

  

RSS

プログラム


プ：グループ分けを整数計画で

  • いわいまさか
  • at 2014/7/11 21:58:12


スリザーリンクを整数計画で解こうとすると
「全体的に１個のループ」というルールが書きにくい。
ネットを検索するとそういう記事にあたるし、自分もそう思う。

それをやや遠くに見据えて以下のような練習。

点p１～p７まであって
線でつながっていたり、いなかったり。



「どの点とどの点がひとつながりになっているか？」

このくらい簡単だと
p1,p2,p6 がひとつのグループで
p3,p4,p5,p7がもうひとつのグループだとわかる。
けど、点が多くなってくると、だんだん、わからなくなってくる。

これを整数計画で判定してみる。

作戦としては、まず、
「グループ名に一番、若い点の番号をつける」
p1,p2,p6 は　　グループ「１」だし、
p3,p4,p5,p7 はグループ「３」にしたい。

ソースとしては、

####################################
Maximize
  value: xsum        (1)

Subject To
   x1 - x2 = 0        (2)
   x1 - x6 = 0
   x2 - x6 = 0
   x3 - x4 = 0
   x3 - x7 = 0
   x3 - x7 = 0
   x4 - x5 = 0
   x5 - x7 = 0

   x1 + x2 + x3 + x4 + x5 + x6 + x7 - xsum = 0   (3)

   x1 <= 1           (4)
   x2 <= 2
   x3 <= 3
   x4 <= 4
   x5 <= 5
   x6 <= 6
   x7 <= 7

Bounds

Binary

End
####################################

・上記(2)  リンク状態　
x1はp1が属しているグループ名を表している。

例えばp1 と p2　はつながっているので、
x1 と x2 は同じになる。
x = x2   ->  x1 -  x2 = 0

(2)からの８行でリンク状態を表している。
ここのパートはリンクの状態に合わせて書き換えて行くことになる。

・上記(4)  若い点の番号をつけるので
　p1の属しているグループ番号 x1は 1以下に
　p2の属しているグループ番号 ｘ2は 2以下に
　p3の属しているグループ番号 ｘ2は 3以下に
　・・・・・・・・・・・・・・・・・・・・・・
　なる。

上の条件２つだけだと、ひとつながりになってもないのに
「オレはグループ「１」っす」と
（あるいは、「オレはグループ「－１００」っす」と）
ウソ申告してくるヤツが出てしまうので・・・

・上記(1)(3)
　グループ番号を「最大、高く」なるようにしておく。
　これでちゃんと、ウソ申告なしのグループ番号になる。

　逆に、全部の点が、p1とひとつながりの場合には、どんなに最大を狙ってもみなさん、グループ１にしかならない。

実際にSCIＰにかけると

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
solution status: optimal solution found
objective value:                                   15
xsum                                               15 (obj:1)
x1                                                  1 (obj:0)
x2                                                  1 (obj:0)
x6                                                  1 (obj:0)
x3                                                  3 (obj:0)
x4                                                  3 (obj:0)
x7                                                  3 (obj:0)
x5                                                  3 (obj:0)
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

という答えが出て、

p1,p2,p6 がグループ「１」でp3,p4,p7,p5がグループ「３」だと判定できている。

今回の例は、ループになっている場合だったけど、枝分かれしたり、余分にリンクがはってある場合も特に、問題なく使える。



  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56103

コメントを書く