BranchandBound

Use the lower bound as starting root-state and determine Q and state at Line 7 for 2 iterations.

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:

 é[(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 )