BranchandBound
|
Document last modified:
|
Use the lower bound as starting root-state and determine Q and
state at Line 7 for 2 iterations.
| |
(a,c)+(a,b)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,d) |
|
| lower bound = ⌈[ |
(1 + 3) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 3) |
]/2⌉
= 14 |
Our bounding function will be to compute the sum s of the
two smallest weights for each vertex that includes edges in the
possible cycle.
For example, edge (a, d) must be included as weights
of (a,d) and (d,a) as:
| |
(a,c)+(a,d)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,a)+ |
(e,c)+(e,d) |
|
| lower bound = ⌈[ |
(1 + 5) + |
(3 + 6) + |
(1 + 2) + |
(3 + 5) + |
(2 + 3) |
]/2⌉ = 16 |
To reduce the state-space generated:
- We'll start at a and after
visiting n-1 nodes, visit the remaining unvisited node and return to
a.
- Also, because the graph is undirected, we will generate only tours
in which b is visited before c (we're simply enforcing a partial ordering of
vertices to visit); that's why Node 2 is not expanded further.
The state-space tree is:
-
Node Best-First( Node
root-state )
-
Q ← ∅
-
state ← root-state
-
while true
-
if goal(state)
return state
-
Q
← Q +
successors(state)
-
if Q =
| return NIL
-
state =
EXTRACT-MIN( Q )
|
|
 |
Iteration 1
state
| |
(a,c)+(a,b)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 3) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 3) |
]/2⌉
= 14 |
Q={(a,b)=14, (a,d)=16, (a,e)=19} Remember b before c so skip c.
| |
(a,c)+(a,b)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 3) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 3) |
]/2⌉
= 14 |
|
| |
(a,c)+(a,d)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,a)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 5) + |
(3 + 6) + |
(1 + 2) + |
(3 + 5) + |
(2 + 3) |
]/2⌉
= 16 |
|
| |
(a,c)+(a,e)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,a) |
|
| é[ |
(1 + 8) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 8) |
]/2⌉
= 19 |
|
-
Node Best-First( Node
root-state )
-
Q ← ∅
-
state ← root-state
-
while true
-
if goal(state)
return state
-
Q
← Q +
successors(state)
-
if Q =
| return NIL
-
state =
EXTRACT-MIN( Q )
|
|
|
Iteration 2
state
| |
(a,c)+(a,b)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 3) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 3) |
]/2⌉
= 14 |
Q={(a,b,d)=16, (a,b,c)=16, (a,d)=16, (a,b,e)=19, (a,e)=19}
| |
(a,c)+(a,b)+ |
(b,a)+(b,d)+ |
(c,a)+(c,e)+ |
(d,e)+(d,b)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 3) + |
(3 + 7) + |
(1 + 2) + |
(3 + 7) + |
(2 + 3) |
]/2⌉
= 16 |
|
| |
(a,c)+(a,b)+ |
(b,a)+(b,c)+ |
(c,a)+(c,b)+ |
(d,e)+(d,c)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 3) + |
(3 + 6) + |
(1 + 6) + |
(3 + 4) + |
(2 + 3) |
]/2⌉
= 16 |
|
| |
(a,c)+(a,d)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,a)+ |
(e,c)+(e,d) |
|
| é[ |
(1 + 5) + |
(3 + 6) + |
(1 + 2) + |
(3 + 5) + |
(2 + 3) |
]/2⌉
= 16 |
|
| |
(a,c)+(a,b)+ |
(b,a)+(b,e)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,b) |
|
| é[ |
(1 + 3) + |
(3 + 9) + |
(1 + 2) + |
(3 + 4) + |
(2 + 9) |
]/2⌉
= 19 |
|
| |
(a,c)+(a,e)+ |
(b,a)+(b,c)+ |
(c,a)+(c,e)+ |
(d,e)+(d,c)+ |
(e,c)+(e,a) |
|
| é[ |
(1 + 8) + |
(3 + 6) + |
(1 + 2) + |
(3 + 4) + |
(2 + 8) |
]/2⌉
= 19 |
|