ESEMPIO DI ALBERO BRANCH-AND-BOUND

Problema di Copertura nodi pesata

53

2

4

7

6

12

10

35

3

4

2

11

7

9

10

15

59nodo calcolato

59

x1=0 x1=1nodo calcolato

nodo da calcolare

59

x1=0 x1=1

65

nodo calcolato

nodo da calcolare

59

x1=0 x1=1

65x7=0 x7=1

nodo calcolato

nodo da calcolare

59

x1=0 x1=1

65

x7=0 x7=1

65

nodo calcolato

nodo da calcolare

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

nodo calcolato

nodo da calcolare

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69

nodo calcolato

nodo da calcolare

nodo con soluzione

53

2

4

7

6

12

10353

4

2

11

7

9

1015

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

nodo calcolato

nodo da calcolare

nodo con soluzione

53

2

4

7

6

12

10353

4

2

11

7

9

1015 5

32

4

7

6

12

10353

4

2

11

7

9

1015

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

65

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

61.5

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

68

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

64

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

64x4=0 x4=1

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

64x4=0 x4=1

71

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

64x4=0 x4=1

71 64

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

53

2

4

7

6

12

10353

4

2

11

7

9

1015 5

32

4

7

6

12

10353

4

2

11

7

9

1015

59

x1=0 x1=1

65

x7=0 x7=1

65x4=0 x4=1

69 65

62

x2=0 x2=1

6863

x3=0 x3=1

85

64

x7=0 x7=1

64x4=0 x4=1

71 64

nodo calcolato

nodo da calcolare

nodo con soluzione

nodo eliminato

65

645

32

4

7

6

12

10353

4

2

11

7

9

1015 5

32

4

7

6

12

10353

4

2

11

7

9

1015