조합 최적화로 부등식 풀기

이게 뭐야

문제

두 개의 연속 칸 사이에 부등호가있는 경우, 칸에 들어가는 숫자는 부등호가 나타내는 대소 관계를 충족시켜야합니다.

아래는 왼쪽이 문제이고 오른쪽이 대답입니다. 이 문제에 대한 해결책은 여러 가지가 있습니다.

입력 파라미터

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

파이썬

import numpy as np
from pulp import LpProblem, lpSum, lpDot, value
from ortoolpy import addvars, addbinvars
data = """\
. 1 . 3 .

. 3<. . .

.<. . . 5
V   A    
2 . . . .
    A   A
.<.<4<.>.""".splitlines()
n = (len(data)+1)//2

파이썬으로 풀기

수리 모델을 만들고 풀어 봅시다.

변수

제약

m = LpProblem()
v = np.array(addbinvars(n, n, n)) # (1)
r = np.array(addvars(n, n)) # (2)
for i in range(n):
    for j in range(n):
        m += lpSum(v[i,j]) == 1 # (3)
        m += lpDot(range(n), v[i,j]) + 1 == r[i,j] # (4)
        m += lpSum(v[i,:,j]) == 1 # (5)
        m += lpSum(v[:,i,j]) == 1 # (5)
        c = data[i*2][j*2]
        if c.isdigit():
            m += v[i,j,int(c)-1] == 1 # (6)
for i in range(n - 1):
    for j in range(n):
        c = data[i*2+1][j*2]
        if c == 'A':
            m += r[i,j] <= r[i+1,j] - 1 # (7)
        elif c == 'V':
            m += r[i,j] >= r[i+1,j] + 1 # (7)
for i in range(n):
    for j in range(n - 1):
        c = data[i*2][j*2+1]
        if c == '<':
            m += r[i,j] <= r[i,j+1] - 1 # (7)
        elif c == '>':
            m += r[i,j] >= r[i,j+1] + 1 # (7)
m.solve()

결과 표시

print(np.vectorize(value)(r).astype(int))
>>>
[[5 1 2 3 4]
 [4 3 5 1 2]
 [3 4 1 2 5]
 [2 5 3 4 1]
 [1 2 4 5 3]]