Metodo Branch and Bound

Metodo del Branch and Bound

Il metodo del Branch and Bound è un paradigma di programmazione utilizzato nei problemi di ottimizzazione nell’esplorazione dello spazio delle soluzioni.
Questo metodo è caratterizzato dall’enumerazione sistematica implicita di tutte le soluzioni del problema, procedendo nell’albero della ricorsione ramo per ramo e prima di procedere nella ricorsione sottostante valuta la possibilità che il resto del ramo possa portare ad una soluzione migliore di quella attualmente considerata come migliore, calcolando un limite superiore ed inferiore per la soluzione. Permette in modo semplice di evitare interi rami di ricorsione nell’albero di ricerca delle soluzioni, ottimizzando il tempo macchina sui rami considerati promettenti, ovvero con possibilità di raggiungere una soluzione ottima.
Per utilizzare un algoritmo di Branch and Bound abbiamo quindi bisogno di regole di Branch per suddividere lo spazio delle soluzioni, un metodo per il calcolo del bound per l’ottimo e le normali regole di esplorazione dell’albero di ricerca su cui applicare il metodo.
Le regole di Branch sono le normali regole utilizzate negli algoritmi di ricerca ricorsiva con cui si suddivide il problema fino a problemi elementari.
Le procedure per il calcolo del Bound sono invece legate al problema stesso e quindi devono essere pensate problema per problema, di fondo viene comunque memorizzata una soluzione provvisoria per ogni passaggio ricorsivo su cui viene poi fatto backtrack.