Optimisation de la combinaison - problème typique - problème de coupe maximale

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

Problème de coupe maximum

Dans le graphe non orienté $ G = (V, E) $, on suppose qu'un poids non négatif $ w_ {ij} $ est donné à chaque côté $ e_ {ij} = (v_i, v_j) \ dans E $. À ce stade, trouvez $ V_1, V_2 (= V \ setminus V_1) $ qui maximise $ \ sum_ {v_i \ in V_1, v_j \ in V_2} {w_ {ij}} $.

Méthode d'exécution

usage


Signature: maximum_cut(g, weight='weight')
Docstring:
Problème de coupe maximum
contribution
    g:Graphique(node:weight)
    weight:Caractère d'attribut de poids
production
Poids de coupe totaux et une liste de numéros de sommets

python


#Données CSV
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, maximum_cut
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = maximum_cut(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()
print(t)

résultat


(27.0, [2, 4, 5])

mct2.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaximumCut
MaximumCut('data/node0.csv','data/edge0.csv')[1]
id x y demand weight
2 2 10 5 0 1
4 4 2 2 1 2
5 5 0 5 1 1

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, 4)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
t = maximum_cut(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t[1])
plt.show()

mct.png

Les données

Recommended Posts

Optimisation de la combinaison - problème typique - problème de coupe maximale
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation de la combinaison - problème typique - problème de débit maximal
Optimisation de combinaison - problème typique de problème de sac à dos
Problème d'optimisation de la combinaison - coupe minimale
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
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 de correspondance typique de problème-poids par optimisation de combinaison
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)
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Combinaison de problèmes typiques d'optimisation et comment le faire