RSS

  

RSS

パズル


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

  • いわいまさか
  • at 2019/5/25 22:15:14

碁石拾いは古典的なパズル。
wikipediaにも説明がある。
https://ja.wikipedia.org/wiki/%E7%A2%81%E7%9F%B3%E6%8B%BE%E3%81%84

最近パズルの会で碁石拾いが話題になっていた。プログラムで解いている人もいた。

自分は、整数計画ソルバーで解いてみようと思い立った。碁石拾いは、１個ずつ手が進むので、普通の探索プログラムで解くのに向いているところだがw

整数計画ソルバーは「整数の連立不等式、等式の問題」を解いてくれるツール。つまり、「解きたい元々の問題」を「整数の連立不等式、等式の問題」で表せれば、整数計画ソルバーが解いてくれるという塩梅。

もう、一段、具体的には・・・
①碁石拾いの問題を読んで、LPというフォーマットで出力する。この部分はC#で作った。
②LPを整数計画ソルバーのSCIPに解かせる。
③でてきた出力を読んで、答え出力。さらに、別解検索で①に戻る。この部分もC#。

SCIPというのは整数計画ソルバーのひとつ。
ページは　https://scip.zib.de/

LPというのはSCIPに入力できるフォーマット
http://www.msl.titech.ac.jp/~serc/kannolab/kanno/lecture/lp_file160604.pdf
http://www.msl.titech.ac.jp/~serc/kannolab/kanno/lecture/linpro161020.pdf

この方法の気に入っているところは、
①「整数の連立不等式、等式の問題」に変換するところ自体がパズルっぽいところ。
②そして、①をクリアしてしまうと、プログラムでの解き方（どうやったら、そもそも解けるのかとか、枝刈りとか）を考えなくてよいというところ。
③また、それは、①をしっかり作れば、バグり難いということ。

つづく

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

コメントを書く