가중치 매칭 문제에서의 해법 비교

이게 뭐야



최대 가중치 매칭 문제 의 2개의 해법의 계산 시간을 비교했다.

계산



파이썬
import time, numpy as np, networkx as nx
from pulp import *
from ortoolpy import addbinvars
np.random.seed(1)
平均次数 = 3
for N in [10,100,200,500,1000,2000,5000]:
    # グラフ作成
    g = nx.fast_gnp_random_graph(N, 平均次数/(N-1))
    for r,(i,j) in zip(np.random.rand(g.number_of_edges()),g.edges_iter()):
        g.edge[i][j]['weight'] = r

    # 汎用ソルバ(cbc)で計算
    m = LpProblem(sense=LpMaximize)
    x = addbinvars(g.number_of_edges())
    for v,(i,j) in zip(x, g.edges()):
        g[i][j]['Var'] = v
    m += lpDot([g[i][j]['weight'] for i,j in g.edges()], x)
    for nd in g.nodes():
        m += lpSum(d['Var'] for d in g[nd].values()) <= 1
    t1s = time.clock()
    m.solve()
    n1 = len([i for i,v in enumerate(x) if value(v) > 0.5])
    t1e = time.clock()

    # エドモンズ法
    t2s = time.clock()
    n2 = len(nx.max_weight_matching(g))//2
    t2e = time.clock()
    assert n1==n2
    print(N,t1e-t1s,t2e-t2s)
>>>
10 0.02683257321768906 0.004652122559491545
100 0.038709433923941106 0.041949099861085415
200 0.046430152317043394 0.1253287561412435
500 0.08796162778162397 1.2250798634777311
1000 0.15964821091620252 4.0942329679674
2000 0.3348240090563195 20.510134776166524
5000 0.9361551560868975 159.31649612302135

시각화



jupyter
%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.xlabel('ノード数')
plt.ylabel('計算時間(秒)')
plt.plot([10,100,200,500,1000,2000,5000],[0.0268,0.0387,0.0464,0.0879,0.1596,0.3348,0.9361], label='汎用ソルバ')
plt.plot([10,100,200,500,1000],[0.0046,0.0419,0.1253,1.2250,4.0942], label='エドモンズ法')
plt.legend();



고찰


  • 일반적으로 전용 솔버가 범용 솔버보다 성능이 좋을 것으로 기대된다. ( 무료 런치 정리 - Wikipedia )
  • 양자 모두 엄밀해를 요구하고 있다.
  • 범용 솔버의 기본값은 무료 cbc입니다.
  • 범용 솔버는 분지 한정법에 기초한 다항식 순서를 보증하지 않는 방법이지만, 계산 시간이 선형 순서에 가깝고 5000 노드에서도 1초가 걸리지 않는다.
  • 전용 알고리즘인 에드몬스법은, 효율이 좋은 방법이라고 알려져 있지만, 계산 시간이 선형 오더가 되어 있지 않기 때문에, 5000 노드에서는 범용 솔버의 170 배가 되고 있다.

  • 이상

    좋은 웹페이지 즐겨찾기