Problème de correspondance typique de problème-poids par optimisation de combinaison

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

Problème de correspondance de poids

Le problème de correspondance de poids est un terme général tel que "problème de correspondance de poids maximum, problème de correspondance de poids maximum maximum, problème de correspondance parfaite de poids maximum, problème de correspondance de poids minimum maximum, problème de correspondance parfaite de poids minimum".

Problème de correspondance de poids Type de problème Nombre de côtés assortis
Problème de correspondance de poids maximum Maximiser Tout
Problème de correspondance maximum de poids maximum Maximiser Doit être égal au problème de correspondance maximal
Problème de correspondance parfaite du poids maximum Maximiser Doit être la moitié du score
Problème de correspondance de poids minimum maximum Minimiser Doit être égal au problème de correspondance maximal
Problème de correspondance parfaite du poids minimum Minimiser Doit être la moitié du score

Problème de correspondance de poids maximum

Pour le graphe non orienté $ G = (V, E) $, lorsque le poids $ w (e) $ de chaque côté $ e \ dans E $ est donné, $ \ sum_ {e \ in M} {w ( e) Trouvez le $ M $ correspondant avec le plus grand} $.

Méthode d'exécution (problème de correspondance de poids maximum)

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]
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: 1, 1: 5, 0: 2, 2: 0, 4: 3, 3: 4}

mwm2.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaxWeightMatching
MaxWeightMatching('data/edge0.csv')
node1 node2 capacity weight
0 0 2 2 4
1 1 5 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)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 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

Problème de correspondance typique de problème-poids par optimisation de combinaison
Optimisation de combinaison - problème typique de correspondance de problème 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
Optimisation de la combinaison - problème typique - problème de débit maximal
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 la combinaison - problème typique - problème de coupe maximale
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
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
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
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité