組合せ最適化でクリークを解く #Python

Advent Calendar 9日目の記事組合せ最適化でチョコナを解く
Advent Calendar 11日目の記事組合せ最適化でスターバトルを解く

これなに

クリークを、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。

自分でも試してみたい人は、下記を参考にしてください。

数独を通して組合せ最適化を学ぼう

問題

いくつかのマスを黒くぬります。
数字は、数字が隣接するマス中の黒マスの数を表します。
すべての白マスは連結すること。

左が問題で、右が答えです。

Pythonでは、data（数字ならばヒント）を使うことにします。

python

import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = """\
....1.
0.....
..3.4.
.2.12.
...1.1
......""".splitlines()

変数表

下記のような変数表を作成します。各行の変数(Var)は0または1をとります。
変数の値が1ならば、該当行該当列のマスが該当の数になります。

	行	列	Var
0	0	0	v000001
1	0	1	v000002
...	...	...	...

python

ni, nj = len(data)-1, len(data[0])-1
a = pd.DataFrame([(i,j) for i in range(ni)
    for j in range(nj)], columns=['行','列'])
a['Var'] = addbinvars(len(a))
a[:2]

数理モデルを作り解く

変数表ができたので、クリークの解になるように、制約条件を追加し数理モデルを作成し、解きましょう。

数字のヒントは、周りの黒の数。
白が連結していること。
- 制約条件として書くこともできますが、大変なので、ここでは一旦無視して解きます。
- 答えが連結していないときに、その答えを禁止して解き直します。
- 連結しているかどうかは、unionfind.isconnectedでできます。

python

m = LpProblem()
m += lpSum(a.Var)
for i in range(ni+1):
    for j in range(nj+1):
        if data[i][j].isdigit():
            q = f'{i-1}<=行<={i}&{j-1}<=列<={j}'
            m += lpSum(a.query(q).Var) == int(data[i][j])
while True:
    m.solve()
    r = a.Var.apply(value)
    if unionfind.isconnected((r!=1).values.reshape(ni,nj)):
        break
    m += lpSum(a[r==1].Var) <= (r==1).sum()-1

結果の表示

python

plt.imshow((1-r).values.reshape(ni,nj), cmap='gray', interpolation='none')
plt.show()

解けていることが確認できます。

以上