[PYTHON] Kombinationsoptimierung - typisches Problem-Gewichtsanpassungsproblem

Typisches Problem und Ausführungsmethode

Gewichtsanpassungsproblem

Das Problem der Gewichtsanpassung ist ein allgemeiner Begriff wie "Problem der maximalen Gewichtsanpassung, Problem der maximalen Gewichtsanpassung, Problem der maximalen Anpassung des maximalen Gewichts, Problem der maximalen Anpassung des minimalen Gewichts, Problem der perfekten Anpassung des minimalen Gewichts".

• Alle Gewichte sind 0 oder mehr.
• Das Problem der minimalen Gewichtsanpassung wird normalerweise nicht berücksichtigt, da ** leer ** die offensichtlich optimale Lösung ist.
• Wenn alle Gewichte 1 in "Maximales Gewichtsanpassungsproblem und maximales Gewichtsmaximales Anpassungsproblem und minimales Gewichtsmaximales Anpassungsproblem" sind, einfach "Maximales Gewichtsanpassungsproblem" Namens.
• Wenn die Gewichte im "Problem der perfekten Übereinstimmung des maximalen Gewichts und des Problems der perfekten Übereinstimmung des minimalen Gewichts" alle 1 sind, wird dies einfach als "Problem der perfekten Übereinstimmung" bezeichnet.
• Das Problem der maximalen Übereinstimmung mit minimalem Gewicht und das Problem der perfekten Übereinstimmung mit minimalem Gewicht können durch Ändern des Gewichts auf "maximales Gewicht - das Gewicht" auf das maximale Übereinstimmungsproblem mit maximalem Gewicht und das perfekte Übereinstimmungsproblem mit maximalem Gewicht reduziert werden.
• Das Problem der perfekten Anpassung des maximalen Gewichts ist nur dann eine Lösung, wenn die Lösung des Problems der maximalen Anpassung des maximalen Gewichts die perfekte Übereinstimmung ist.
• Aus diesen Gründen ist es nur erforderlich, eine Lösung für das Problem der maximalen Gewichtsanpassung und das Problem der maximalen Gewichtsanpassung zu finden.
• Das Problem der maximalen Gewichtsanpassung kann durch das folgende max_weight_matching (Edmonds-Methode) gelöst werden. --Maximales Gewicht Um das Problem der maximalen Übereinstimmung zu lösen, geben Sie unten in max_weight_matching maxcardinality = True an.
• Wenn das Diagramm ein zweiteiliges Diagramm ist, gibt es einen Algorithmus (wie die ungarische Methode), der eine höhere Leistung als allgemeine Diagramme aufweist.

Problem der maximalen Gewichtsanpassung

Für den ungerichteten Graphen $ G = (V, E) $ ist, wenn das Gewicht $ w (e) $ jeder Seite $ e \ in E $ angegeben ist, $ \ sum_ {e \ in M} {w ( e) Finden Sie das passende $ M $ mit dem größten} $.

Ausführungsmethode (maximales Gewichtsanpassungsproblem)

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

#CSV-Daten
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)

Ergebnis

{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

#Zufällige Daten
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()

Daten

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