Advent Calendar 7日目の記事 組合せ最適化で因子の部屋を解く
Advent Calendar 9日目の記事 組合せ最適化でチョコナを解く
これなに
のりのりを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 盤面のいくつかのマスを黒くぬります。
- 黒マスは必ずタテかヨコにちょうど２つだけぬります。
- 太線で区切られた各部分には、黒マスが２つずつ入ります。
左が問題で、右が答えです。
Pythonでは、data（部屋のグループ）を使うことにします。
python
import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
ABBBC
ADDBC
EDBBB
EEEEE
EEEEE""".splitlines()
変数表
下記のような変数表を作成します。各行の変数は0または1をとります。
変数の値が1ならば、該当行 該当列のマスが黒になります。
| 行 | 列 | 字 | Var | |
|---|---|---|---|---|
| 0 | 0 | 0 | A | v000001 |
| 1 | 0 | 1 | B | v000002 |
| ... | ... | ... | ... | ... |
python
ni, nj = len(data), len(data[0])
a = pd.DataFrame([(i,j,data[i][j]) for i in range(ni)
for j in range(nj)], columns=list('行列字'))
a['Var'] = addbinvars(len(a))
a[:2]
数理モデルを作り解く
変数表ができたので、のりのりの解になるように、制約条件を追加し数理モデルを作成し、解きましょう。
- あるマスが黒なら、その上下左右の黒の数はちょうど1となる。これは、下記の2つの式で表現できます（Mは十分大きな数）。
- 上下左右の黒の数 >= 該当マスの黒の数
- 上下左右の黒の数 <= 1 + M*(1-該当マスの黒の数)
- 各グループ内の黒の数はちょうど2。
python
m = LpProblem()
for _,r in a.iterrows():
e = lpSum(a.query(f'abs(行-{r.行})+abs(列-{r.列})==1').Var)
m += e >= r.Var
m += e <= 1+(len(e)-1)*(1-r.Var)
for g,v in a.groupby('字'):
m += lpSum(v.Var) == 2
m.solve()
結果の表示
python
a['Val'] = a.Var.apply(value)
plt.imshow((a.Val<0.5).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()
解けていることが確認できます。
以上