Backtraking e branch and bound

[dzcosimo]

per prima cosa se sto postando troppo ditemelo che mi modero ma sono sotto a preparare l'ultimo esame dell'anno e dunque i dubbi escono fuori come funghi :-D
passiamo dunque alla domanda:
fra i vari metodi di programmazione ne ho trovati due in particolare -ovvero quello del backtraking e quello del branch and bound- che mi danno particolari problemi, in particolare non ne capisco la differenza. Entrambi si basano sul generare un albero rappresentante le soluzioni e nell'esplorarlo se ho capito bene.

cit. da wiki:
"Gli algoritmi Branch and Bound sono detti di enumerazione implicita perché si comportano esattamente come un algoritmo di enumerazione -cioè "provano" tutte le soluzioni possibili fino a trovare quella ottima (o quella corretta)- ma ne scartano alcune dimostrando a priori la loro non ottimalità."

cito ora dalle dispense messe a disposizione sul loro sito dai docenti del corso di algoritmi e strutture dati della facoltà di ingegneria informatica di Pisa, riguardo al backtraking:
"...ogni volta che si sale di un livello si aggiunge un vincolo all'insieme delle soluzioni. Appena tutto un albero è stato visitato si toglie tale vincolo e si risale per visitare un altro sottoalbero dello stesso livello. Quando ci si accorge che un sottoalbero non conterrà alcuna soluzione valida possiamo 'potare' quel ramo per velocizzare la ricerca"

non si tratta sostanzialmente della stessa cosa?
vi prego di chiarirmi, se ne avete voglia e tempo, la differenza fra i due metodi che prorprio non riesco a cogliere

[apatriarca]

Dalla pagina inglese di wikipedia:
"The branch-and-bound design strategy is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that the branch-and-bound method (1) does not limit us to any particular way of traversing the tree and (2) is used only for optimization problems."
Inoltre in branch and bound si calcola un lower e upper bound dei rami. Nel backtracking invece si visita un ramo finché non si trova un errore e si torna a quel punto indietro. Non ci sono metodi per scartare a priori dei rami.

[dzcosimo]

grazie milleXD
ma ora mi chiedo, quando possibile dunque è opportuno utilizzare i due metodi contemporaneamente?
ad esempio nell'algoritmo delle n regine potrei aggiungere un array(è pura teoria non so se possa velocizzare effettivamente le cose) di bool nel quale posso immagazzinare se una colonna già ospita una regina ed in quel caso aggiungere il vincolo di non accedere a quella colonna?in questo caso dovrebbe essere programmazione branch and bound se ho capito bene; al contrario se non utilizzassi questo metodo, entrassi nel nodo che rappresenta le possibilità di posizionamento in quella riga e vedessi che ci sta già una regina decidendo dunque di tornare indietro in questo caso userei il backtraking?

[apatriarca]

No, quello è semplicemente backtracking. Ad ogni turno escludi tutte le possibilità che portano immediatamente ad un vicolo cieco.

[dzcosimo]

allora per favore mi puoi fare un esempio di branch and bound?
perchè non capisco ancora la differenza,mi pareva di aver intuito che in un caso i vincoli venivano messi prima di leggere l'albero(b.a.b.) ed in un caso durante la lettura(backtraking) ma evidentemente così non è...

[apatriarca]

Hai dato un occhiata alla pagina di wikipedia in inglese? Era un po' più chiaro l'algoritmo di quanto fosse spiegato in italiano. Comunque si usa solo nei problemi di ottimizzazione. Supponi di voler trovare il massimo assoluto di una funzione. Allora dividi il dominio in alcuni sottoinsiemi e supponi di avere un modo per calcolare l'upper e i lower bound dell'insieme. A questo punto se c'è un insieme che ha il suo upper bound minore del lower bound di un qualche altro sottoinsieme si può scartare. Un esempio specifico al momento non mi viene. Prova comunque a dare un occhiata a quella pagina.