fbpx

Algoritmo Branch and bound

Il Branch and bound è un’algoritmo utilizzato per la risoluzione di problemi di ottimizzazione combinatoria e consiste nella scomposizione del problema originale in sottoproblemi più semplici da risolvere. L’algoritmo trova applicazione nella risoluzione del problema dello zaino, in quello del commesso  viaggiatore o in problemi di assegnamento, inoltre può essere considerato come base per la risoluzione di problemi tramite algoritmi euristici (ad esempio si può usare per creare una generazione di partenza per gli algoritmi genetici). In logistica trova applicazioni pratiche nei problemi di caricamento di vettori o magazzini, nella schedulazione degli ordini di produzione o nella definizione del piano delle consegne. In realtà più che un singolo algoritmo è più opportuno parlare di famiglia di tecniche risolutive che hanno in comune l’albero decisionale ma che si differenziano per le strategie di esplorazione(Depth-first,Highest-first,ibrida,breadth-first ognuna delle  quali presenta vantaggi o svantaggi in termini di complessità di calcolo) o le tecniche di riduzione. Anche nel caso del’algoritmo Branch and bound è possibile reperire librerie per poterlo implementare informaticamente.

ALLEGATI

BB01
Titolo: BB01 (0 click)
Etichetta:
Filename: bb01.pdf
Dimensione: 156 KB
BB02
Titolo: BB02 (0 click)
Etichetta:
Filename: bb02.pdf
Dimensione: 132 KB
BPR02
Titolo: BPR02 (0 click)
Etichetta:
Filename: bpr02-2.pdf
Dimensione: 125 KB

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Articoli collegati

3d bin packing

Il problema di bin packing 3D (3D-BPP) consiste, dato un insieme di oggetti (item) rettangolari di diverse dimensioni, nel determinare il numero minimo di contenitori

leggi

— il nuovo servizio per i piccoli commercianti —

Bottega Digitale

[]