이게 뭐야

수학과 컴퓨터 어드벤트 캘린더의 11일째 기사 「볼록 다각형의 최적 삼각형 분할」를 조합 최적화에서 풀어 보았습니다.

사고방식

볼록 N각형에 교차하지 않도록 N-3개의 대각선을 그리면 삼각형 분할할 수 있으므로 합이 최소의 것을 선택하면 됩니다.

수리 최적화 절차는 스도쿠를 통해 조합 최적화를 배우자.을 참조하세요.

예제

적당히 다각형을 만듭니다.

python3

import matplotlib.pyplot as plt
import numpy as np, pandas as pd, networkx as nx
from pulp import LpProblem, lpDot, lpSum, value
from ortoolpy import addbinvars
plt.rcParams['figure.figsize'] = (4,4)
plt.axes().set_aspect('equal', 'datalim')

pos = np.array([[1,2],[2,0],[4,0],[6,1],[5,4],[4,5],[2,4]])
dcpos = dict(enumerate(pos))
n = len(pos)
g = nx.Graph()
g.add_edges_from([(i,(i+1)%n) for i in range(n)])
nx.draw_networkx(g,pos=dcpos)
plt.show()

변수 테이블

변수 테이블을 만듭니다.

python3

a = pd.DataFrame([(i,j,np.linalg.norm(pos[i]-pos[j]))
    for i in range(n) for j in range(i+2,n-(i==0))], columns='I J Dist'.split())
a['Var'] = addbinvars(len(a))
a[:2]

I
J
Dist
Var


0
0
2
3.605551
v000001

1
0
3
5.099020
v000002

공식화하고 풀다

제약은 N-3개 필요라고 하면 교차시키지 않게 됩니다.

python3

m = LpProblem()
m += lpDot(a.Dist, a.Var)
m += lpSum(a.Var) == n-3 # N-3本必要
for idx,(i1,j1,_,v1) in a.iterrows():
    for _,(i2,j2,_,v2)  in a[idx+1:].iterrows():
        if i1 < i2 < j1 < j2:
            m += v1+v2 <= 1 # 交差させない
m.solve()
a['Val'] = a.Var.apply(value)
print('対角線の和',value(m.objective))
g.add_edges_from(a[a.Val>0.5].values[:,:2])
nx.draw_networkx(g,pos=dcpos)
plt.show()
>>>
対角線の和 15.200792856081229

할 수 있었습니다.

이상