[PYTHON] Optimisation de combinaison - problème typique de correspondance de problème maximum

Problème typique et méthode d'exécution

Problème de correspondance maximum

Trouvez la correspondance avec le nombre maximum de côtés pour le graphe non orienté $ G = (V, E) $.

Méthode d'exécution

usage


Signature: nx.max_weight_matching(G, maxcardinality=False)
Docstring:
Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once.
The cardinality of a matching is the number of matched edges.
The weight of a matching is the sum of the weights of its edges.

python


#Données CSV
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
for i, j in g.edges():
    del g.adj[i][j]['weight']
d = nx.max_weight_matching(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()
print(d)

résultat


{5: 0, 0: 5, 4: 3, 3: 4, 2: 1, 1: 2}

image.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaxMatching
MaxMatching('data/edge0.csv')
node1 node2 capacity weight
0 0 5 2 4
1 1 2 2 5
2 3 4 2 4

python


#Données aléatoires
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
d = nx.max_weight_matching(g)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()

mwm.png

Les données

Recommended Posts

Optimisation de combinaison - problème typique de correspondance de problème maximum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de la combinaison - problème typique - problème de débit maximal
Problème de correspondance typique de problème-poids par optimisation de combinaison
Optimisation de la combinaison - problème typique - problème de coupe maximale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Optimisation de combinaison - problème typique d'allocation généralisé
Problème d'optimisation de combinaison-problème typique d'emballage de bac
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Problème d'optimisation de la combinaison - coupe minimale
Combinaison de problèmes typiques d'optimisation et comment le faire