Exercise 12        Name __________________        Score __/ 12
Document last modified: 

  1. (2) Verify that the circuit in Figure 34.8(b) is unsatisfiable.
  2. (3) A Hamiltonian path in a graph is a simple path that visits every vertex exactly once.

    Show that the language HAM-PATH={<G,u,v> : there is a Hamiltonian path from u to v in graph G} belongs to NP.

  3. (1) Figure 34.5 illustrates that the reduction algorithm F computes a reduction function f from language L1 to L2 in polynomial time. What is done by function f on reducing L1 to L2 for the Critical Path Analysis problem (discussed at the end of Single Source Shortest Path notes)?
     
  4. (3) Give the state-space tree generated by a backtracking solution to HAM-PATH, again selecting vertices in alphabetical order. Number the nodes in the order generated. Recall that backtracking is essentially DFS with early cutoff, the cutoff occurs when there is no solution compatible with previous solutions.

     

  5. (3) Apply the branch and bound (best-first) algorithm to solve the traveling salesman problem, drawing the state-space tree generated. Number nodes as generated. Use the lower bound formula from class notes. Start at a, stop when reaching the goal of touring all cities.

                                a       b         c         d

    lower bound = é[(2+5)+(2+3)+(1+5)+(1+3)]/2ù = 11

     

    1. Node Best-First( Node root-state )
        -- pre: root-state is lowest bounds
        -- post: returns NIL if no solution otherwise best-fit solution

    2.   Q ¬ Æ

    3.   state ¬ root-state                                     

    4.   while true

    5.     if goal(state) return state                      -- assignment goal is all cities visited

    6.     Q ¬ Q + successors(state)                     -- adds immediate successors of state

    7.     if Q = Æ return NIL

    8.     state = EXTRACT-MIN( Q )                      -- removes and returns minimum cost state