조합 최적화로 녹지 풀기

Advent Calendar First Day 스도쿠를 통해 조합 최적화를 배우자.
Advent Calendar 3 일째 기사 조합 최적화로 폭격기 퍼즐 해결

이게 뭐야

칵로 1 을 파이썬에서 조합 최적화 모델을 만들어 풀어 라.
푸는 재미는 모델링을 고안하는 것입니다.

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

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

문제

아래 그림의 흰색 칸에 1~9의 숫자를 넣어 세로 또는 가로 합계가 힌트와 같도록 합니다.


파이썬에서는 data
파이썬

import re, pandas as pd
from pulp import LpProblem, lpDot, lpSum, value
from ortoolpy import addbinvars
data = """\
#..##
....#
..#..
#....
##..#""".splitlines()
hint_v = [ # 開始行、開始列、個数、合計
    (0,1,4,11),
    (0,2,2,4),
    (1,0,2,14),
    (1,3,4,10),
    (2,4,2,3),
    (3,2,2,3),
]
hint_h = [ # 開始行、開始列、個数、合計
    (0,1,2,5),
    (1,0,4,17),
    (2,0,2,6),
    (2,3,2,4),
    (3,1,4,10),
    (4,2,2,3),
]

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 매스가 해당 수가 됩니다.


행
열
수
Var

0
0
1
1
v000001

1
0
1
2
v000002

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


파이썬

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

수리 모델을 만들어 풀다

변수 테이블을 만들었으므로, 괭이의 해가되도록 제약 조건을 추가하고 수리 모델을 만들고 풀어 봅시다.

각 매스에 숫자를 1개 넣는다. …(1)

. 에서 하나의 매스 변수가 DataFrame의 hint_v 에 들어가므로 hint_h 하면 숫자를 하나 선택하게 됩니다.

일련의 배열로, 같은 숫자는 1개까지. …(2)

아래에서는 일련의 배열을 DataFrame( for _,v in a.groupby(('行','列')) )에 넣습니다. 일련의 배열은 직사각형이므로 v 로 간단하게 꺼낼 수 있습니다.

일련의 배열의 합계를 힌트와 동일하게. …(3)

2열의 DataFrame의 각 열을, 각각 제1 인수, 제2 인수에 건네주고 싶을 때, m += lpSum(v.Var) == 1 그리고 할 수 있습니다. 이것은 전치 ( b )하고 DataFrame.query ( *b.T.values )로 확장 ( T )하고 있습니다.

파이썬

m = LpProblem()
for _,v in a.groupby(('行','列')):
    m += lpSum(v.Var) == 1 # (1)
for (di,dj),hint in zip([(1,0),(0,1)],[hint_v,hint_h]):
    for si,sj,nl,sm in hint:
        b = a.query(f'{si}<=行<={si+nl*di}&{sj}<=列<={sj+nl*dj}')[['数','Var']]
        for _,v in b.groupby('数'):
            m += lpSum(v.Var) <= 1 # (2)
        m += lpDot(*b.T.values) == sm # (3)
m.solve()

결과 표시

파이썬

a['Val'] = a.Var.apply(value)
r = a[a.Val>0.5].数[::-1].tolist()
print(re.sub('\\.', lambda _: str(r.pop()), '\n'.join(data)))
>>>
#23##
9512#
51#31
#3142
##21#

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

이상



녹는 주식회사 니코리 의 등록상표 입니다. ↩