RSS

 

RSS


プログラム


整数計画ソルバーで唯一解判定 その1

  • いわいまさか
  • at 2019/6/16 10:08:58

整数計画ソルバーでパズル(的なもの)の唯一解判定に関して、いままで、自分の作戦では。

①LPを書いて答えを出す。
②もとのLPに対して①の答えを禁じた条件を追加したものを書き、答えを出す。
「①が解ありで、②で解なしだと、唯一解だ」という作戦を使っていた。

これだと、LPを2回解くことになり、つまり、2回目で同じ計算をまた解かせるので、もったいなさそうなのだった。

今回、LP1回分で、解なし、唯一解、複数解を判定することにチャレンジ。

簡単な問題で進める。
問題は「数nを2個の自然数の和で表す。ただし、使う自然数はみんな違うもの」

n=2だと 解なし
n=3だと 1+2の唯一解
n=4だと 1+3の唯一解
n=5だと 1+4 2+3 解が2個
n=6だと 1+5 2+4 解が2個
ニコリのペンシルパズルのカックロの要素的問題。

大枠の展望

a君に解かせて
同じ問題をb君にも解かせて
a君とb君の答えが違う方をよりよいとしておき(maximizeとかが使えるかなぁ)
①a君とb君が違う答えを出してくれば、複数解
②それでも、a君とb君が同じ答えを出してくれば、唯一解
③a君もb君も答えられなければ、解なし

ということで。

つづく


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