조합 최적화로 추리 퍼즐 풀기

Advent Calendar 11 일 기사 조합 최적화로 스타 배틀 풀기
Advent Calendar 13 일 기사 조합 최적화로 페인트 영역 풀기

이게 뭐야

추리 퍼즐 1 을 Python에서 조합 최적화 모델을 만들어 풀어보세요.
푸는 재미는 모델링을 고안하는 것입니다.

자신도 시도하고 싶은 사람은 아래를 참조하십시오.

스도쿠를 통해 조합 최적화를 배우자.

문제

3개의 쌍( kinds )을 입력하여 각 쌍 간의 대응을 구합니다.

힌트( data )

아키라는 백색을 샀다.

명은 실이 아니다.

파란 종이를 사는 사람이 있다.

용기는 종이가 아니다.

긍정은 신발을 샀다.

긍정은 아기가 아니다.

파이썬에서는 kinds (3 가지 유형), data (성부, 사람, 물건, 색)을 사용하기로 결정합니다.

파이썬

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

...
...
...
...
...


파이썬

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.

힌트를 만족시키는 것.

파이썬

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()

결과 표시

파이썬

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
서양
종이
블루



풀리고 있는지 확인할 수 있습니다.

이상



추리 퍼즐은 주식회사 니코리 의 등록상표 입니다. ↩