Answer Happy

QUESTION 1: Search - A* Variants [20 Marks] Queuing variants: Consider the following variants of the A tree search algorithm. In all cases, gis the cumulative path cost of a node n, h is a lower bound on the shortest path to a goal state, and no is the parent of n. Assume all costs are positive. iii. iv. V. i. Standard A ii. A*, but we apply the goal test before enqueuing nodes rather than after dequeuing A*, but prioritize n by g (n) only (ignoring h (n)) A®, but prioritize n by h (n) only (ignoring 8 (n)) A*, but prioritize n by g (n) + h (no) vi. A”, but prioritize n by g (no) + h (n) a) Which of the above variants are complete, assuming all heuristics are admissible? 3 Marks] b) Which of the above variants are optimal, again assuming all heuristics are admissible? [3 Marks] c) Assume you are required to preserve optimality. In response to n's insertion, can you ever delete any nodes m currently on the queue? If yes, state a general condition under which nodes m can be discarded, if not, state why not. Your answer should involve various path quantities (g. h, k) for both the newly inserted node n and another nodem on the queue. [3 Marks] d) In the satisficing case, in response to n's insertion, can you ever delete any nodes m currently on the queue? If yes, state a general condition, if not, state why not. Your answer involves various path quantities (g, h, k) for both the newly inserted node n and another nodes m on the queue. [4 Marks] e) Is A with an e-admissible heuristic complete? Briefly explain. [3 Marks) f) Assuming we utilize an e-admissible heuristic in standard A' search, how much worse than the optimal solution can we get? l.e. c* is the optimal cost for a search problem, what is the worst cost solution an e-admissible heuristic would yield? Justify your answer. [2 Marks] g) Suggest a modification to the A* algorithm which will guaranteed to yield an optimal solution using an e-admissible heuristic with fixed, known e. Justify your answer. [2 Marks]