scritto da | on | Nessun commento

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

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
BB01
Titolo: BB01 (0 click)
Etichetta:
Filename: bb01.pdf
Dimensione: 156 kB

Lascia un Commento

News