Lezione 24.1: altri esempi interessanti di B&B, il CSP
Completion requirements
il problema del commesso viaggiatore (TSP). Euristica = vicino più vicino, rilassamento = 1-albero di costo minimo, branching = eliminare uno dei lati incidenti al vertice con grado troppo alto nell'1-albero (e perché). Ancora altri esempi interessanti di B&B: il problema del cammino minimo vincolato. Euristica = nessuna, rilassamento = cammino minimo, branching sofisticato basato sul rendere inammissibile il cammino minimo (e perché). Esecuzione del B&P per TSP e CSP su un'istanza: i vari modi di potare un nodo, evoluzione delle valutazioni inferiori e superiori, ottimalità.