RSS

  

RSS

プログラム


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

  • いわいまさか
  • at 2019/6/16 19:59:06

前回の記事からのつづき

問題：
　自然数の２個の和で５を表す。
　使う自然数は違うもの。

という問題を解くためのLPはこれ。
sum5.lp

a君用に・・・

a1 a2 a3 a4 a5 は和に１を使うか、２を使うか、３を使うかというbinary変数（bool変数）

①要素が２個だということの式
a1 + a2 + a3 + a4 + a5 = 2 
②和が5になることの式
1 a1 + 2 a2 + 3 a3 + 4 a4 + 5 a5 = 5
③全部の解に番号をふる。２進数的なことで。
a君とb君の答えの比較用に。
1 a1 + 2 a2 + 4 a3 + 8 a4 + 16 a5 = an

同じことをb君にもやってあげて。

解の番号を比較して
diff = an - bn
それができるだけ最大(Maximaize)になるようにしている。

a君b君答えがなければ、解なし
a君b君の答えがあってdiffが0なら、a君とb君が同じ答えを提出しているので、唯一解。
a君b君の答えがあってdiffが0より大きいなら複数解
ということになる。

n=5のところの数字をかえて試してみると、

n=2  解なし
n=3  diff=0  唯一解
n=4  diff=0  唯一解
n=5  diff=3  複数解
n=6  diff=7  複数解

と結果がでる。

考察：
前回の記事で提示した「解なし、唯一解、複数解を１回のLPで判定する」という目的は達成した。
だけど、「解が２個以上あれば、複数解だよん」というゆるい要求に対して「解番号の差を最大にする」というギンギンな計算をさせてるため、無駄がある。
今回の問題は小さかったため、問題にならなかったが、大きい問題を解くときには、その無駄が問題になる。このままでは使えない。


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

コメントを書く