3 A* search (30 points) Consider a search problem where each state is represented with an...

Transcribed Image Text:

3 A* search (30 points) Consider a search problem where each state is represented with an integer i. The successor function for state i will return three different states i + 1, i 1, and 2* i. The aim of the search process is to reach to a given goal n which is again an integer (n can be smaller, larger or equal to the initial state i). Note that the cost of each action (each application of the successor function) is set to simply one. Consider the heuristic |ni| for the problem. a. Draw the search tree for the case where the initial state is i = 6 and n = 6 and n 10 and A* is applied on the problem. Again at each step, clearly denote which node will be selected for expansion and draw the search tree after each expansion. Provide the g(i), h(i) and f(i) values for each node i. b. Have you found the optimal solution? Why? 3 A* search (30 points) Consider a search problem where each state is represented with an integer i. The successor function for state i will return three different states i + 1, i 1, and 2* i. The aim of the search process is to reach to a given goal n which is again an integer (n can be smaller, larger or equal to the initial state i). Note that the cost of each action (each application of the successor function) is set to simply one. Consider the heuristic |ni| for the problem. a. Draw the search tree for the case where the initial state is i = 6 and n = 6 and n 10 and A* is applied on the problem. Again at each step, clearly denote which node will be selected for expansion and draw the search tree after each expansion. Provide the g(i), h(i) and f(i) values for each node i. b. Have you found the optimal solution? Why?