CS638
Artificial Intelligence
MidSem Exam
October 10, 2006
Max marks
= 70
Weightage = 20%
Be Concise
Answer: Order of visiting nodes Depth = 0 : A Depth = 1 : ABCD Depth = 2 : ABECACBFNDADCHA Depth = 3 : ABEIBCFNDABABCDCBECAFIG
(or)
Depth = 0 : A Depth = 1 : ADCB Depth = 2 : ADHCACDNFBABCEA Depth = 3 : ADHNDCNFBADADCBCDHCANG 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.
Answer: The graph after N is expanded.
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
Answer: 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
P_{1} = (2,4,7,1,5,9,8,3.6) and P_{2} = (4,5,7,2,6,8,1,9,3)
For the above example choosing the subsequences from fourth to seventh city gives the children.
C_{1} = (x,x,x,1,5,9,8,x,x) and C_{2} = (x,x,x,2,6,8,1,x,x)
the remaining cities for C_{1}
are arranged in order as in P_{2} = (4,
C_{1} = (1,5,9,8,4,7,2,6,3) and C_{2} = (2,6,8,1,4,7,5,9,3)
Answer
AD + BD <= AC + BC [marks 1]
Do try this one.
End.
