RSS

  

RSS

パズル


整数計画ソルバーで碁石拾い その２

  • いわいまさか
  • at 2019/5/26 12:10:23

前の記事はこちら、
整数計画ソルバーで碁石拾い

不等式や等式を立てていくところを見ていく。

説明するのにあたり、石の配置は
●●●●
●
アルファベットで示せるようにしておくと
ＡＢＣＤ
Ｅ
それぞれ座標は
Ａ(1,1) Ｂ(1,2) Ｃ(1,3) Ｄ(1,4)
Ｅ(2,1)
とした。(y,x)の順番なので注意。

石に全部、名前をつける。座標からとって。
(1,1)にある石なら x0101  以下同様。 

スタート地点はどこからでも始められるので、
最初とる石の前にまだ、見えない石があるとして、xssssとしておく。最後のところも、同様にxeeeeとしておく。

石から石の移動（スタートやエンドも含めて）で考えられるリンクをすべて、binary変数とし登録する。それぞれの変数の取りえる値は0か1。
候補という意味で、
石と石の関係として、縦か横の座標一致で、つながる。
スタートからは全ての石につながる。
すべての石からエンドへはつながる。

 l_xssss_x0101
 l_x0102_x0101
 l_x0103_x0101
 l_x0104_x0101
 l_x0201_x0101
 l_xssss_x0102
 l_x0101_x0102
 l_x0103_x0102
 l_x0104_x0102
 l_xssss_x0103
 l_x0101_x0103
 l_x0102_x0103
 l_x0104_x0103
 l_xssss_x0104
 l_x0101_x0104
 l_x0102_x0104
 l_x0103_x0104
 l_xssss_x0201
 l_x0101_x0201
 l_x0101_xeeee
 l_x0102_xeeee
 l_x0103_xeeee
 l_x0104_xeeee
 l_x0201_xeeee

そして、例えば
 l_x0102_x0101が1ならば、そのリンクが存在することを示す。この変数のうちの6個が1になって、スタートからエンドまでうまくつながっていればそれが答えということになるわけ。

つづく

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

コメントを書く