가중치 매칭 문제에서의 해법 비교
이게 뭐야
최대 가중치 매칭 문제 의 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();
고찰
파이썬
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();
고찰
%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();
이상
Reference
이 문제에 관하여(가중치 매칭 문제에서의 해법 비교), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/SaitoTsutomu/items/7fd199a95d78a6f3b741텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)