ESEMPIO DI ALBERO BRANCH-AND-BOUND
Problema di Copertura nodi pesata
15
5
3
10
2
9
4
7
7
11
6
12
2
4
10
3
5
3
59
nodo calcolato
59
nodo calcolato
x1=0
x1=1
nodo da calcolare
59
nodo calcolato
x1=0
65
x1=1
nodo da calcolare
59
nodo calcolato
x1=0
65
x7=0
x1=1
x7=1
nodo da calcolare
59
nodo calcolato
x1=0
x1=1
65
x7=0
65
x7=1
nodo da calcolare
59
nodo calcolato
x1=0
x1=1
65
x7=0
65
x4=0
x4=1
x7=1
nodo da calcolare
59
nodo calcolato
x1=0
x1=1
65
nodo con soluzione
x7=0
65
x4=0
x7=1
x4=1
69
15
5
10
3
2
9
4
7
7
11
6
12
2
4
10
3
5
3
nodo da calcolare
59
nodo calcolato
x1=0
x1=1
65
nodo con soluzione
x7=0
65
x4=0
15
5
10
x7=1
x4=1
69
65
3
2
9
4
7
7
11
6
12
2
4
10
3
5
3
nodo da calcolare
59
nodo calcolato
x1=0
x1=1
65
nodo con soluzione
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x4=1
65
65
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
61.5
x7=0
65
x4=0
69
x7=1
x4=1
65
65
nodo da calcolare
nodo con soluzione
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
x7=1
x4=1
65
65
nodo da calcolare
nodo con soluzione
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65
nodo con soluzione
x2=1
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
x2=1
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
x2=1
63
nodo eliminato
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
x3=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
85
x3=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
85
x3=1
64
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
85
x3=1
64
x7=0
x7=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
x3=1
64
85
x7=0
64
x7=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
85
64
x4=0
x3=1
64
x7=0
x4=1
x7=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
69
nodo da calcolare
x7=1
x2=0
x4=1
65
65 68
nodo con soluzione
nodo eliminato
x2=1
63
x3=0
85
64
x4=0
71
x3=1
64
x7=0
x4=1
x7=1
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
15
5
10
x7=1
x2=0
x4=1
69
nodo da calcolare
65
65 68
nodo con soluzione
x3=0
85
64
x4=0
3
nodo eliminato
x2=1
63
x3=1
64
x7=0
x7=1
x4=1
2
9
4
71
7
7
11
6
12
2
4
10
3
5
3
64
59
nodo calcolato
x1=0
x1=1
65
62
x7=0
65
x4=0
15
5
10
x7=1
x2=0
x4=1
69
nodo da calcolare
65
65 68
nodo con soluzione
x3=0
85
64
x4=0
3
nodo eliminato
x2=1
63
x3=1
64
x7=0
x7=1
x4=1
2
9
4
71
7
7
11
6
12
2
4
10
3
5
3
64
64