Comparaison des solutions aux problèmes d'appariement de poids

Qu'est-ce que c'est

Nous avons comparé les temps de calcul des deux solutions de Maximum Weight Matching Problem.

Calcul

python


import time, numpy as np, networkx as nx
from pulp import *
from ortoolpy import addbinvars
np.random.seed(1)
Commande moyenne= 3
for N in [10,100,200,500,1000,2000,5000]:
    #Création de graphes
    g = nx.fast_gnp_random_graph(N,Commande moyenne/(N-1))
    for r,(i,j) in zip(np.random.rand(g.number_of_edges()),g.edges_iter()):
        g.edge[i][j]['weight'] = r

    #Solveur polyvalent(cbc)Calculé avec
    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()

    #Méthode Edmonds
    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

Visualisation

jupyter


%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.xlabel('Nombre de nœuds')
plt.ylabel('Temps de calcul(Secondes)')
plt.plot([10,100,200,500,1000,2000,5000],[0.0268,0.0387,0.0464,0.0879,0.1596,0.3348,0.9361], label='Solveur polyvalent')
plt.plot([10,100,200,500,1000],[0.0046,0.0419,0.1253,1.2250,4.0942], label='Méthode Edmonds')
plt.legend();

image.png

Considération

c'est tout

Recommended Posts

Comparaison des solutions aux problèmes d'appariement de poids
[Astuces] Problèmes et solutions dans le développement de python + kivy
Comparaison des modules de conversion japonais en Python3
À propos des problèmes et des solutions d'OpenPyXL (version Ver 3.0)
L'ancien openssl pose des problèmes dans diverses parties de python
○○ Résolution de problèmes dans le département de mathématiques avec optimisation
Comparaison des classificateurs en ligne
Comparaison des programmes d'adaptation
Comparaison du code de moyenne mobile exponentielle (EMA) écrit en Python
Comparaison de l'utilisation des fonctions d'ordre supérieur dans Python 2 et 3
Comparaison des méthodes de détection des couleurs dans OpenCV inRange, numpy, cupy
Comparaison de la loi hongroise et des solveurs polyvalents pour les problèmes d'allocation
Problèmes et solutions à la demande de MySQL db dans Python 3
Comparaison de la gestion des trames de données en Python (pandas), R, Pig