Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale

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

Problème d'arborescence de surface minimale

Lorsque le poids du côté $ e $ sur le graphe non orienté $ G = (V, E) $ est $ w (e) $, la somme des poids du côté sur tout l'arbre $ T = (V, E_T) $ $ Trouvez l'arbre entier qui minimise \ sum_ {e \ dans E_T} {w (e)} $.

Méthode d'exécution

usage


Signature: nx.minimum_spanning_tree(G, weight='weight')
Docstring:
Return a minimum spanning tree or forest of an undirected
weighted graph.

A minimum spanning tree is a subgraph of the graph (a tree) with
the minimum sum of edge weights.

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]
t = nx.minimum_spanning_tree(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(t, pos, width=3)
plt.show()
print(t.edges())

résultat


[(0, 1), (0, 3), (0, 4), (2, 3), (4, 5)]

mst2.png

python


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

python


#Données aléatoires
import math, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
pos = nx.spring_layout(g)
for i, j in g.edges():
    g.adj[i][j]['weight'] = math.sqrt(sum((pos[i] - pos[j])**2))
t = nx.minimum_spanning_tree(g)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(t, pos, width=3)
plt.show()

mst.png

Les données

Recommended Posts

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 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
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 de combinaison - problème typique de correspondance de problème maximum
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 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 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
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
Problème d'optimisation de la combinaison - coupe minimale
Arborescence de surface totale minimale en C #