Advent Calendar 11日目の記事 組合せ最適化でスターバトルを解く
Advent Calendar 13日目の記事 組合せ最適化でペイントエリアを解く
これなに
推理パズル1を、Pythonで組合せ最適化モデルを作って解きます。
解く楽しみは、モデル化を工夫することになります。
自分でも試してみたい人は、下記を参考にしてください。
問題
- 3つの組(
kinds)を入力し、各組間の対応を求めます。 - ヒント(
data)- 明は白いのを買った。
- 明は糸じゃない。
- 青い紙を買った人がいる。
- 勇は紙じゃない。
- 正は靴を買った。
- 正は赤じゃない。
Pythonでは、kinds（3つの種類）、data（成否、人、物、色）を使うことにします。
python
import pandas as pd
from pulp import LpProblem, lpSum, value
from itertools import chain, product
from ortoolpy import addbinvar
kinds = [['明','勇','正','洋'],
['傘','靴','紙','糸'],
['赤','青','白','黒']]
data = [s.split(',') for s in """\
1,明,,白
0,明,糸,
1,,紙,青
0,勇,紙,
1,正,靴,
0,正,,赤""".splitlines()]
変数表
下記のような変数表を作成します。各行の変数(Var)は0または1をとります。
変数の値が1ならば、該当の人、物、色が成立します。
| 人 | 物 | 色 | Var | |
|---|---|---|---|---|
| 0 | 明 | 傘 | v000001 | |
| 1 | 明 | 靴 | v000002 | |
| ... | ... | ... | ... | ... |
python
a1 = pd.DataFrame((s0,s1,'',addbinvar()) for s0,s1 in product(kinds[0],kinds[1]))
a2 = pd.DataFrame((s0,'',s2,addbinvar()) for s0,s2 in product(kinds[0],kinds[2]))
a3 = pd.DataFrame(('',s1,s2,addbinvar()) for s1,s2 in product(kinds[1],kinds[2]))
a = pd.concat([a1,a2,a3])
a1.columns = a2.columns = a3.columns = a.columns = ['人','物','色','Var']
a[:2]
数理モデルを作り解く
変数表ができたので、推理パズルの解になるように、制約条件を追加し数理モデルを作成し、解きましょう。
- 縦横で丸は1つ。
- AかつB、BかつCなら、CかつA。
- ヒントを満たすこと。
python
m = LpProblem()
for a0,c1,c2 in [(a1,'人','物'),(a2,'人','色'),(a3,'物','色')]:
for _,v in chain(a0.groupby(c1),a0.groupby(c2)):
m += lpSum(v.Var) == 1
for s1,s2,s3 in product(*kinds):
vlst = [a1.query(f'人=="{s1}"&物=="{s2}"').Var.iloc[0],
a2.query(f'人=="{s1}"&色=="{s3}"').Var.iloc[0],
a3.query(f'物=="{s2}"&色=="{s3}"').Var.iloc[0]]
for v in vlst:
m += lpSum(vlst) <= 1+2*v
for c,s1,s2,s3 in data:
m += a.query(f'人=="{s1}"&物=="{s2}"&色=="{s3}"').Var.iloc[0] == int(c)
m.solve()
結果の表示
python
a1['Val'] = a1.Var.apply(value)
a2['Val'] = a2.Var.apply(value)
a1.loc[a1.Val>0.5,['人','物']].merge(a2.loc[a2.Val>0.5,['人','色']])
| 人 | 物 | 色 | |
|---|---|---|---|
| 0 | 明 | 傘 | 白 |
| 1 | 勇 | 糸 | 赤 |
| 2 | 正 | 靴 | 黒 |
| 3 | 洋 | 紙 | 青 |
解けていることが確認できます。
以上