CS638             Artificial Intelligence                 MidSem Exam                        October 10, 2006

Max marks =   70                    Weightage = 20%                               Be Concise
  1. In the graph shown alongside, A is the start node and G the goal node. List the order in which DFID will visit nodes, including repeat visits if any, before it terminates. Assume the children are generated from left to right in the figure. Assume that the search algorithm does not maintain a CLOSED list. Is the algorithm guaranteed to terminate without a CLOSED list? Under what conditions? Justify your answer.                                                                                                       [marks 10]









Order of visiting nodes

Depth = 0 : A

Depth = 1 : ABCD






Depth = 0 : A

Depth = 1 : ADCB



Yes, the algorithm is guaranteed to terminate without a CLOSED list as long there exists a path from to the goal node.  This is because the algorithm iteratively searches paths of longer lengths. It cannot go down a loop infinitely. If the shortest path to the goal has length L, eventually it will start exploring all paths of length L and find the solution.

  1. Algorithm A* is about to expand the node N in the graph below. Labels on edges are cost of moves. Show the graph after A* has finishedexpanding the node N.  [marks 20]


The graph after N is expanded.












  1. Given the cost matrix in the accompanying table, determine the estimated cost of a TSP tour that contains the segment DE but excludes the segment AB. Describe your estimating function. What properties should the estimating function have to devise a good TSP solver?                                                                                           [marks 10]


The estimate is computed by summing up the two lowest allowed values in each row in the cost matrix, and dividing the sum by two. For segments that are known to be in the tour the corresponding cost has to be included. Likewise for segments that have to be excluded, the corresponding cost has to be left out. In the given problem cost of DE, which is 70, is included twice, and cost of AB (10) is not included.

 Estimated cost = [(AC + AD) + (BE + BC) + (CA + CD) + (DE + DA) + (ED + EB)]/2

                         = [(20 + 30) + (30 + 40) + (20 + 30) + (70 + 30) + (70 + 30)]/2

 = 370/2

 = 185


A higher estimate can be found by recognizing that A C D are forming a cycle of length three, or recognizing that in the chosen links nodes C and D have three degrees, and replacing one of these costs by a higher one from that row.

 Properties of estimating function

  1. Should be a lower bound. This is needed for admissibility of the algorithm.

  2. Should be as high as possible. This is to make the search more focused and efficient.

  1. Choose a representation for solving the TSP problem using a GA, and devise a crossover operator that produces valid tours. Illustrate the operator with an example with a nine city problem                                                                                                                                                                                             [marks 9]


One way of implanting GAs for TSP


Path or Order representation = list the cities in the order visited.     


Crossover - select a subtour (substring)  from one parent and arrange the remaining cities in the order of the other parent. For example, given two parent tours


            P1 = (2,4,7,1,5,9,8,3.6) and

            P2 = (4,5,7,2,6,8,1,9,3)


For the above example choosing the subsequences from fourth to seventh city gives the children.


C1 = (x,x,x,1,5,9,8,x,x) and

            C2 = (x,x,x,2,6,8,1,x,x)


the remaining cities for C1 are arranged in order as in P2 = (4,5,7,2,6,8,1,9,3) giving (4,7,2,6,3). Likewise for the other child the remaining cities are arranged in the order of P1 giving the two offspring,


C1 = (1,5,9,8,4,7,2,6,3) and

            C2 = (2,6,8,1,4,7,5,9,3)




  1. What is the minimax value of the 4-ply game tree shown below? Mark the recommended move for root. Show the nodes visited by the Alpha-Beta algorithm searching from left to right.                                          [marks 20]




  1. Given a triangle ABC and an interior point D in the triangle, show that the lengths of segments satisfy the following inequality.

AD + BD <= AC + BC                                                            [marks 1]


Do try this one.