Advent Calendar 22日目の記事 組合せ最適化で不等式を解く
Advent Calendar 24日目の記事 組合せ最適化でへやわけを解く
これなに
波及効果を、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 各部屋のマスには1からその部屋のマス数までの数を1つずつ入れます
- 同じ数字を同じ横行、または同じ縦列に入れる場合、数字と数字の間にその数字と同じ数以上のマス目がなくてはなりません
下記は、左が問題で、右が答えです。
入力パラメータ
dataにヒントが入っているとします。
python
import numpy as np
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
...3..
......
..2..4
3..4..
......
..2...""".split()
rms = [[eval(t) for t in s.split('/')] for s in """\
0,0
0,1/0,2/1,2
0,3/1,3/1,4/2,3
0,4
0,5/1,5/2,4/2,5/3,5
1,0/1,1
2,0/3,0/3,1/4,1
2,1/2,2/3,2/4,2
3,3/4,3/5,1/5,2/5,3
3,4
4,0/5,0
4,4/4,5/5,5
5,4""".splitlines()]
nw, nh = len(data[0]), len(data)
na = max(len(rm) for rm in rms)
Pythonで解く
数理モデルを作成し、解きましょう。
変数
- v：各位置がどの数字か (1)
- r：各位置の数字 (2)
制約
- 数字があれば、その数字 (3)
- 数字は１つのみ (4)
- rをvで表現 (5)
- nマス以内に2つ以上の数字nはないこと (6)
- 各部屋内で同じ数字はないこと (7)
python
m = LpProblem()
v = addbinvars(nh, nw, na) # (1)
r = addvars(nh, nw) # (2)
def dirs(i, j, k):
yield from (v[i+l][j][k] for l in range(1, k+2) if i+l < nh)
yield from (v[i][j+l][k] for l in range(1, k+2) if j+l < nw)
for i in range(nh):
for j in range(nw):
if data[i][j].isdigit():
m += r[i][j] == int(data[i][j]) # (3)
m += lpSum(v[i][j]) == 1 # (4)
m += lpDot(range(na), v[i][j]) + 1 == r[i][j] # (5)
for k in range(na):
m += lpSum(dirs(i,j,k)) <= 2*(1-v[i][j][k]) # (6)
for rm in rms:
for k in range(len(rm)):
m += lpSum(v[i][j][k] for i,j in rm) == 1 # (7)
m.solve()
結果の表示
python
print(np.vectorize(value)(r).astype(int))
>>>
[[1 2 1 3 1 2]
[2 1 3 2 4 1]
[4 3 2 1 5 4]
[3 2 1 4 1 3]
[2 1 4 1 3 1]
[1 5 2 3 1 2]]
解けていることが確認できます。
以上