조합 최적화의 격차를 풀기

Advent Calendar 14일 기사 조합 최적화로 벽 로직 풀기
Advent Calendar 16일 기사 조합 최적화로 미술관 풀기

이게 뭐야

의 놀라움을 파이썬으로 조합 최적화 모델을 만들고 풀어줍니다.
푸는 재미는 모델링을 고안하는 것입니다.

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

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

문제

각 횡행의 왼쪽, 각 세로 열 위에 있는 숫자는 그 행(열) 안에서 연속적으로 검게 칠하는 흰색 매스의 수를 나타냅니다

하나의 행(열)에 숫자가 여러 개 있는 경우 숫자의 순서대로 그 숫자의 수만큼 연속적으로 검은색으로 칠합니다

.

하나의 행(열)에 숫자가 여러 개 있는 경우 해당 숫자가 나타내는 검은색 매스의 연속 사이에 1매스 이상의 흰색 매스(칠하지 않은 매스)가 들어갑니다

아래는 문제와 대답입니다.

공식화

\begin{array}{cl}
            変数 & v_{ij} \in \{0, 1\} ~ \forall i, j ~ ~ ~ (マスi,jが黒かどうか) (1) \\
                 & r_{k} \in \{0, 1\} ~ \forall k, 縦または横 ~ ~ ~ ~ ~ (縦または横ごとにk番目の候補を選ぶかどうか) (2) \\
\mbox{subject to} & \sum_k{r_k} = 1 ~ \forall 縦または横 ~ ~ ~ ~ (縦または横ごとに候補の中から1つ) (3) \\
                 & 候補を選んだらマスの色は候補の通り (4) \\
\end{array}

hinth에 가로 힌트가 있고 hintv에 세로 힌트가 있다고 가정합니다.

파이썬

import numpy as np, matplotlib.pyplot as plt
from pulp import LpProblem, lpSum, value
from ortoolpy import addvars, addbinvars
hinth = [[int(s) for s in t.split(',')] for t in
         '2 3,2 2,3 2,2 8 7 1,4 3,3 1,1 3'.split()]
hintv = [[int(s) for s in t.split(',')] for t in
         '2 1,2 1,5 5,2 1,2,1 3 6 1,3,2,1 3,4 1,1'.split()]

수리 모델을 만들어 풀다

의 놀라움을 해결하기 위해 제약 조건을 추가하고 수리 모델을 만들고 풀어 봅시다.

do에서 행 또는 열 힌트를 처리합니다.

makelist에서 힌트를 기반으로 패턴을 열거하고 0-1 변수로 하나의 패턴을 선택합니다.

파이썬

def baselist(i, j, k):
    return [0] * i + [1] * j + [0] * k
def makelist(n, l):
    p = l[-1]
    if len(l) == 1:
        if n < p: return None
        return [baselist(i, p, n - p - i) for i in range(n - p + 1)]
    ll = l[:-1]
    s = sum(ll) + len(ll) - 1
    return [j + baselist(1, p, n - p - s - i - 1) \
        for i in range(n - p - s) for j in makelist(i + s, ll)]
def do(m, v, hint):
    for i, hh in enumerate(hint):
        l = makelist(v.shape[0], hh)
        r = addbinvars(len(l)) # (2)
        m += lpSum(r) == 1 # (3)
        for j, c in enumerate(l):
            for k, b in enumerate(c):
                m += (1 - 2 * b) * v[k,i] <= 1 - b - r[j] # (4)
m = LpProblem()
v = np.array(addvars(len(hintv), len(hinth))) # (1)
do(m, v, hinth)
do(m, v.T, hintv)
m.solve()

결과 표시

파이썬

plt.imshow(1-np.vectorize(value)(v), cmap='gray', interpolation='none')
plt.show()

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

이상