Branch and Bound – Codificare l’algoritmo da zero
Ramo e Limite - Costruire l'algoritmo da zero
Una Comprensione Più Approfondita dell’Algoritmo nel Linguaggio di Programmazione Python
Introduzione
Se provieni dall’articolo introduttivo: Branch and Bound – Introduzione Prima di Codificare l’Algoritmo da Zero, allora questa è la parte in cui progrediamo nella comprensione dell’algoritmo codificandolo da zero. Questo mi aiuta sempre a capire il funzionamento dell’algoritmo, avanzando il pensiero algoritmico o computazionale di cui ho bisogno nella mia professione.
Se sei capitato su questo articolo senza leggere l’articolo introduttivo, ti consiglio di leggere i concetti dietro l’algoritmo e comprendere il flusso di lavoro prima di provare il codice qui sotto. Poiché vogliamo evitare contenuti ridondanti, salteremo la spiegazione dell’algoritmo branch and bound e passeremo subito alla codifica.
Ripasso Rapido dell’Algoritmo:
L’algoritmo Branch and Bound, quando utilizzato per risolvere programmi lineari e nel contesto della programmazione intera, segue i seguenti passaggi generali.
- Inizializzazione – Inizializzare la variabile come il valore ottimale minore. Se si sta massimizzando, il valore dovrebbe essere impostato a meno infinito, e il contrario vale per un problema di minimizzazione. La ragione di ciò è che il processo ricorsivo del codice dovrebbe cercare di trovare una soluzione migliore e che una singola esecuzione dell’algoritmo fornirebbe già una soluzione migliore.
- Rilassamento della Programmazione Lineare – Il problema principale verrà risolto se il vincolo intero non è applicato. Pertanto, “rilassiamo” quel vincolo e lo trattiamo come un normale problema di programmazione lineare, da qui il termine “rilassamento della programmazione lineare”. Questo passaggio viene eseguito per ogni sotto-problema.
- Verifica dell’Integralità – Se la soluzione iniziale è già integrale, il programma termina. Questa condizione viene verificata anche per ogni sotto-problema.
- Branching – Se la soluzione ottimale non è integrale, allora il problema viene scomposto (o “ramificato”) in sotto-problemi più piccoli. Ciò viene fatto aggiungendo vincoli a…
