RSS

  

RSS

パズル


STAR FORMING REGION を SCIPで その２

  • いわいまさか
  • at 2020/12/18 08:07:18

STAR FORMING REGION を SCIPで
の続き。

SCIPは、整数の等式や不等式を入力すると解いてくれる。

まず、正五角形を詰める問題。

候補の正五角形に番号づけすると。
p000,p001,p002。。。。
それぞれが、あるかなしかを変数にする。
とりえる値は　0 or 1
b_000 b_001 b_002 。。。

式①
全部で36個詰めようとすると
b_000 + b_001 + b_002 + 。。。。 = 36

式②
候補の正五角形の中には重なっているものもあるわけで、
もしも p000 と p069が重なっていたとすると
b_000 + b_069 <=1  となる。
片方が採用されると、片方は採用できない。
両方採用されないこともある。なので、足して１以下。
それを、全部の重なっている正五角形のペアに対して書く

 b_000 + b_069 <= 1
 b_000 + b_077 <= 1
 b_000 + b_101 <= 1
 b_004 + b_036 <= 1
 b_004 + b_048 <= 1
 b_004 + b_050 <= 1
 b_008 + b_089 <= 1
。。。。。。。。。。
約1000個

重なっているかどうかはSCIPに入力する前に別プログラムで調べておく。

正五角形を詰めていこうとする問題に関してはこの式①と式②
でおしまい。この解き方の流れはとても、スッキリしてる。
SCIPにかけると、答えを出してくれる。

図にすると


つづく

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

コメントを書く