RSS

  

RSS

パズル


パ：「または」を不等式であらわす

  • いわいまさか
  • at 2014/6/26 20:21:52

最近、整数計画ソルバーの
scip
をいじっている。

「一次の不等式（あるいは等式）の問題に落とし込」んでやればscipがサクっと解いてくれる。

ネット内の情報を参考に
数独、お絵かき１９（いわいオリジナル）、シャカシャカ（ニコリ）
を解くプログラムをscipとC#を使ってできた。
その記事はまた。

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

今回の問題は
「５枚あるカードのうちＡが２枚か４枚だ」
というのをどう不等式だけで書くか

ということで

１枚目のカードがＡか否か　　　a1　　　（0 か 1)
２枚目のカードがＡか否か　　　a2
３枚目のカードがＡか否か　　　a3
４枚目のカードがＡか否か　　　a4
５枚目のカードがＡか否か　　　a5

Aの総数はsumは
a1 + a2 + a3 + a4 + a5 = sum

「Aが２枚だ」は
sum == 2
と等式で書けばよい。

だが、

「Ａが２枚か４枚か」は

sum===2 or sum===4 と書ければいいけれど、
その方法は用意されてないようなので。
（このあたり、いわいの調査不足の可能性あり）

不等式で書ききりたいわけで。

フラグを用意して
flag2    このフラグが１のときはＡは２枚だ
　　　　 フラグが０ときは何枚でもよい

flag4    このフラグが１のときはAは４枚だ
　　　　  フラグが０のときは何枚でもよい

があれば、
flag2+flag4 >= 1
 で記述できる。
（flag2とflag4は同時に成り立つことはない）


あとは、flag2、ｆlag4とsumの関係を書いてやるとよくて、
例えば、(書き方はいろいろある）

sum => 2 * flag2 
sum =< -3 *flag2 +5
 
flag4とsumの関係は

sum => 4 * flag4 
sum =< -1 * flag4 +5

でよいので。

まとめると

a1 + a2 + a3 + a4 + a5 = sum
sum => 2 * flag2 
sum =< -3 *　flag2 +5
sum => 4 * flag4 
sum =< -1 * flag4 +5
flag2　+　flag4 >= 1

になる。

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

で、いいかなぁ～。
式自体はあっていると思う。
scipで動かした感じＯＫだった。

だが、
もっと式自体が整理できるかも。
だし、
scipやその周辺に他の記述方法、解決方法がある可能性はある。
し。

以上


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

コメントを書く


コメント

「scip」で剰余計算（「％」）ができるなら、
sum % 2
で偶奇判定して、0を除外すればよいので
sum == 2 or sum == 4
は
((1 + sum) % 2) * sum > 0
と書けます。

http://lpsolve.sourceforge.net/5.5/lp-format.htm とかhttp://lpsolve.sourceforge.net/5.0/CPLEX-format.htm　のもので。
簡単に言うと「１次の不等式（等式）しか書けない」。
http://www.iwai-masaka.jp/56093.html に別解を書きました。そちらもどうぞ。

なるほど、そういうことだったのですね。
ご説明ありがとうございます。