Branch and Bound – Articolo bonus – Visualizzazione dei nodi

Rami e Bound - Articolo bonus - Visualizzazione dei nodi

Usando il pacchetto NetworkX per visualizzare l’algoritmo Branch and Bound in azione

Introduzione

Foto di Alina Grubnyak su Unsplash

Per coloro che arrivano dai miei ultimi due articoli, questo è l’articolo in cui forniamo alcuni codici bonus per visualizzare il nostro algoritmo Branch and Bound in azione.

Gli articoli di questa serie sono i seguenti:

Il contenuto di base per capire il codice seguente si trova in quei due articoli. Sarà difficile capire il codice qui sotto senza aver letto i primi due articoli, poiché discuteremo solo i codici aggiuntivi da aggiungere al codice principale che abbiamo scritto nell’articolo precedente.

In questo articolo, avremo un’anteprima, anche se scriverò ancora un articolo su di esso, su come l’algoritmo Branch and Bound possa essere efficace nel risolvere un problema di ottimizzazione di rete. Più concretamente, forse possiamo visualizzare come funziona e, da lì, avere un’idea o comprensione del suo potenziale per i problemi di ottimizzazione di rete.

Codice di visualizzazione

<p“andiamo aggiuntivo="" al="" articolo.="" che="" codice="" codice,="" contenuto="" dal="" del="" di="" direttamente="" discutiamo="" dobbiamo="" extra,="" graficamente="" grafo="" il="" molto="" nostro="" p="" per="" poiché="" precedente="" prende="" rappresentare="" rete.

Coloreremo i nodi con colori diversi in modo da poter visualizzare facilmente quelli che sono stati potati.”

Aggiunta # 1 – Inizializzazione

import numpy as npfrom scipy.optimize import linprogimport networkx as nximport matplotlib.pyplot as pltoptimal_value = -np.inf# Valore ottimaleoptimal_solution = None# Soluzione ottimale# Albero per contenere nodi e relazioniG = nx.DiGraph()# Oggetto networkxnode_counter = 0# Contatore nodi ottimaliottimal_node = None# Nodo ottimale

In questo codice, abbiamo aggiunto due pacchetti da importare: matplotlib e networkx.

Inoltre, inizializziamo tre variabili necessarie per il nostro grafo di rete:

  • G – o l’oggetto networkx
  • node_counter – per dare nome ai nodi e connetterli.