조합 최적화로 혼자 해줘.

9664 단어 최적화파이썬퍼즐수학조합 최적화
Advent Calendar 20일 기사 조합 최적화로 빌딩 해결
Advent Calendar 22일 기사 조합 최적화로 부등식 풀기

이게 뭐야



혼자 해줘, 파이썬으로 조합 최적화 모델을 만들어 풀어줍니다.
푸는 재미는 모델링을 고안하는 것입니다.

자신도 시도하고 싶은 사람은 아래를 참조하십시오.
  • 스도쿠를 통해 조합 최적화를 배우자.

    • 문제


  • 반면에 줄 지어있는 숫자 중 일부를 검은 색으로 칠하고 세로와 가로에서 같은 열에 같은 숫자가 여러 개 들어가지 않도록합니다
  • 검은 송어를 세로로 연속하거나 검은 송어로 반면을 분리하지 마십시오



    • 입력 파라미터


    data에 힌트가 있다고 가정합니다.

    파이썬
    import numpy as np
from itertools import chain, product
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars, unionfind
data = np.array([list(s) for s in """\
18626753
31118222
83247651
37583314
54467182
71432535
22834475
22314465""".splitlines()]).astype(int)
nn = len(data)

    파이썬으로 풀기



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

    변수


  • v:0:number, 1:black (1)

    • 제약


  • 검정 이외의 숫자는 종횡으로 중복되지 않는 것 (2)
  • 검정은 연속하지 않을 것 (3)
  • 검은 색으로 분리하지 마십시오 (4)

    • 파이썬
    m = LpProblem()
v = np.array(addbinvars(nn, nn)) # 0:number, 1:black (1)
for i, j in product(range(nn), range(nn)):
    for x in [v[i,:][data[i,:] == j+1], v[:,i][data[:,i] == j+1]]:
        m += lpSum(x) >= len(x)-1 # (2)
for e in chain((v[1:,:] + v[:-1,:]).flat, (v[:,1:] + v[:,:-1]).flat):
    m += e <= 1 # (3)
while True:
    m.solve()
    r = np.vectorize(value)(v)
    if unionfind.isconnected(1-r):
        break
    m += lpSum(v[r==1]) <= r.sum() - 1 # (4)

    결과 표시



    파이썬
    data[r==1] = 0
print(data)
>>>
[[1 8 0 2 6 7 5 3]
 [3 0 1 0 8 0 2 0]
 [8 3 2 4 7 6 0 1]
 [0 7 5 8 3 0 1 4]
 [5 4 0 6 0 1 8 2]
 [7 1 4 0 2 5 3 0]
 [2 0 8 3 4 0 7 5]
 [0 2 3 1 0 4 6 0]]

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

    이상
    조합 최적화로 빌딩 해결
    조합 최적화로 부등식 풀기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage