Python
数学
最適化
パズル
組合せ最適化

組合せ最適化でチョコナを解く

Advent Calendar 8日目の記事 組合せ最適化でのりのりを解く
Advent Calendar 10日目の記事 組合せ最適化でクリークを解く

これなに

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

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

問題

  • 国(太線で区切られた部分)の数は、国内の黒マスの合計とする。国の数がない場合はいくつでもよい。
  • 黒マスの連なりは、長方形とする。

下図の薄いグレーが解です。

Pythonでは、data(黒マスの数)、area(国のグループ)を使うことにします。

python
import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
data = """\
3.3...
.1....
22.21.
......
....3.
.2....""".splitlines()
area = """\
001111
022222
345677
345677
355899
3aa889""".splitlines()

変数表

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

Var
0 0 0 3 0 v000001
1 0 1 0 0 v000002
... ... ... ... ... ...
python
ni, nj = len(data), len(data[0])
a = pd.DataFrame([(i,j,data[i][j],area[i][j]) for i in range(ni)
    for j in range(nj)], columns=list('行列字国'))
a. = a..apply(lambda c: int(c) if c.isdigit() else 0)
a['Var'] = addbinvars(len(a))
a[:2]

数理モデルを作り解く

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

  • 各国の黒の数を指定した数に。
    • 数字は1つだけなので、合計をとれます。注意点として、合計が0なら制約条件にしないことです。
  • 黒の形を長方形にする。
    • 任意の2x2の4マスの黒の合計が3にならないということです。
    • 合計を3にしてはいけないという制約条件は、「4マスの黒の合計 <= 2+2*1マスの黒の合計」を4マスの中の各マスで見れば、OKです。
      • 何故なら、3のときだけ、「3<=2」という状態が出て成り立たないためです。
python
m = LpProblem()
for g,v in a.groupby('国'):
    if v..sum():
        m += lpSum(v.Var) == v..sum()
for i in range(ni-1):
    for j in range(nj-1):
        v = a.query(f'{i}<=行<={i+1}&{j}<=列<={j+1}').Var
        for x in v:
            m += lpSum(v) <= 2+2*x
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()

image.png

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

以上