조합 최적화로 벽 로직 풀기

Advent Calendar 13 일 기사 조합 최적화로 페인트 영역 풀기
Advent Calendar 15 일 기사 조합 최적화의 격차를 풀기

이게 뭐야

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

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

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

문제

숫자가 채워진 매스에서 숫자의 수만큼 세로와 가로로 선을 그립니다.

하나의 칸에는 하나의 선만 그릴 수 있습니다

숫자가 기입된 매스에는 선을 그릴 수 없습니다

아래는 왼쪽이 문제이고 오른쪽이 대답입니다.


data 에 힌트의 수가 들어 있다고 합니다.

파이썬

import pandas as pd
from itertools import product
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
4..1..
.4..2.
..2..2
1..1..
.1..1.
..3..2""".split()

변수 테이블

아래와 같은 변수 테이블을 작성합니다. 각 행의 변수는 0 또는 1을 취합니다.
변수의 값이 1이면 해당 행 해당 열의 질량이 검정색입니다.
"향"은 {0:왼쪽, 1:상, 2:오른쪽, 3:아래}입니다. VDir 는 그 방향인가 어떤가, VLen 는 화살표의 길이입니다.


행
열
향
VDir
VLen

0
0
0
0
v000001
v000145

1
0
0
1
v000002
v000146

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


파이썬

ni, nj = len(data), len(data[0])
mx = max(ni, nj)
a = pd.DataFrame([(i,j,k) for i,j,k in product(range(ni),
    range(nj),range(4))], columns=list('行列向'))
a['VDir'] = addbinvars(len(a))
a['VLen'] = addvars(len(a))
a[:2]

수리 모델을 만들어 풀다

변수 테이블을 만들었으므로 벽 논리를 해결할 수 있도록 제약 조건을 추가하고 수리 모델을 만들고 해결합니다.

숫자가 있으면 방향 별 길이의 합과 같고 그 위치에 화살표가 없어야합니다. (1)

숫자가 없으면 화살표는 한 방향만 (2)

숫자가 없으면 화살표 방향으로 길이를 1 더하기 (3)

파이썬

drc = [(-1, 0, 0), (0, -1, 1), (0, 1, 2), (1, 0, 3)]
m = LpProblem()
for i,j in product(range(ni), range(nj)):
    b = a[(a.行==i)&(a.列==j)]
    if data[i][j].isdigit():
        m += lpSum(a[(a.行==i+y)&(a.列==j+x)&(a.向==k)].VLen
                   for y,x,k in drc) == int(data[i][j]) # (1)
        m += lpSum(b.VLen) == 0 # (1)
        continue
    m += lpSum(b.VDir) == 1 # (2)
    for y,x,k in drc:
        r = b[b.向==k].iloc[0]
        m += r.VLen <= mx * r.VDir # (3)
        m += r.VLen <= r.VDir + lpSum(
            a[(a.行==i+y)&(a.列==j+x)&(a.向==k)].VLen) # (3)
m.solve()

결과 표시

파이썬

a['Val'] = a.VDir.apply(value)
print('\n'.join(''.join(' '+(data[i][j] if data[i][j].isdigit()
    else '↑←→↓'[int(value(lpDot([0,1,2,3],a[(a.行==i)&(a.列==j)].Val)))])
    for j in range(ni)) for i in range(nj)))
>>>
 4 → → 1 → ↑
 ↓ 4 → → 2 ↑
 ↓ ↓ 2 → ↓ 2
 1 ↓ ↓ 1 ↓ ↑
 ↓ 1 → ↓ 1 ↑
 ← ← 3 → ↓ 2

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

이상