[PYTHON] 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".

• Tous les poids sont égaux à 0 ou plus. --Le problème de correspondance de poids minimum n'est généralement pas pris en compte car ** vide ** est la solution optimale évidente.
• Lorsque les poids sont tous 1 dans "Problème de correspondance de poids maximum et problème de correspondance maximum de poids maximum et problème de correspondance maximum de poids minimum", simplement "Problème de correspondance de poids maximum" Appelé.
• Lorsque les poids sont tous 1 dans le "problème de correspondance parfaite de poids maximum et problème de correspondance parfaite de poids minimum", on l'appelle simplement le "problème de correspondance parfaite".
• Le problème de correspondance de poids minimum maximum et le problème de correspondance parfaite de poids minimum peuvent être réduits au problème de correspondance maximum de poids maximum et au problème de correspondance parfaite de poids maximum en changeant le poids en "poids maximum-le poids".
• Le problème de correspondance parfaite du poids maximal n'est une solution que lorsque la solution du problème de correspondance maximale du poids maximal est une correspondance parfaite.
• À partir de ces choses, il est seulement nécessaire d'avoir une solution pour le problème de correspondance de poids maximum et le problème de correspondance de poids maximum maximum.
• Le problème de correspondance de poids maximum peut être résolu par le suivant max_weight_matching (méthode Edmonds). --Poids maximum Lors de la résolution du problème de correspondance maximum, maxcardinality = True doit être spécifié dans max_weight_matching ci-dessous. --Si le graphique est un graphique en deux parties, il existe un algorithme (comme la méthode hongroise) qui a des performances plus élevées que les graphiques généraux.

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}

python

# pandas.DataFrame
from ortoolpy.optimization import MaxWeightMatching
MaxWeightMatching('data/edge0.csv')

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()

Les données

• data/node0.csv
• data/edge0.csv