ICS 171Fall 2008Homework Informed Search1) Exercise 4.1 (pg 134)2) Exercise 4.2 (pg 134)3) Exercise 4.3 (pg 134)4) Prove that the Manhattan Distance heuristic for 8-puzzle is admissible5) Consider the heuristic function for the 8-Queens problem described on page 112: h = number of pairs of queens that are attacking each other. Is this heuristic admissible? If it is not, propose another heuristic that is admissible.6) Exercise 4.11 (pg 135)7) Use the min-conflict (local search) method to solve the 4-Queen problem. Start with the queens on the main diagonal. Break ties randomly. 8) Compute the following gradients: )2)(1(2)2(2)1(2),()2(),,()2()exp()1(),,())(exp(11),()1()2)(1(),,,(2223323yxyxyxgyzxzyxczyxxzyxhcbyaxyxgxyztzyxtzyxfbWhere a,b,c are some arbitrary constants.Provide pseudo-code for a gradient descent algorithm that minimizes g(x,y).ICS 171Fall 20089) For the graph below, find the path of the Uniform Cost Search from state A to state I. Show a fringe queue for every step. 1 3 5 4 2 4 3 1 2 10) Consider the search tree below. There are 2 goal states, G1 and G2. The numbers on the edges represent step-costs. You also know the following heuristic estimates: h(BàG2) = 9, h(DàG2)=10, h(AàG1)=2, h(CàG1)=1. In what order will A* search visit the nodes? Explain your answer by indicating the value of the evaluation function for those nodes that the algorithm considers.ABGIH
View Full Document
Unlocking...