Reference no: EM133234806

Question 1. Approximate admissibility Sometimes non-admissible heuristics can be useful too. Let h ∗ (n) be the shortest distance between state n and the goal state. Call a heuristic h an -admissible heuristic if 0 ≤ h(n) ≤ h ∗ (n) + . That is, it is allowed to be pessimistic about the cost of reaching the goal, but only by . Assume that h(n) = 0 if n is a goal state. Prove that A* tree search finds a goal state whose cost is worse than the optimal by at most . Hint: Start with the proof from the slides of the optimality of A* tree search and think about what needs to change.

Question 2. Dominating heuristics Let h1 and h2 be admissible heuristics with h1 dominating h2. That is, 0 ≤ h2(n) ≤ h1(n) ≤ h ∗ (n). Prove that every node expanded by A* tree search using h1 is also expanded when using h2 instead (you may assume that there are no ties in f-value). This shows that dominating always lead to (weakly) more efficient search.

Question 3. Arc Consistency Suppose we are running the AC-3 CSP algorithm (see pseudocode in slides). Prove that if an arc (Xi , Xj ) is not currently in the queue, then the current Di and Dj must satisfy that Xi is arc-consistent with respect to Xj . Hint: use proof by induction / loop invariant.