CS 404 Artificial Intelligence

3. (10 pts) Backtracking Below graph shows state space with cost attached to each arc. Example: The cost to travel from A to B is 100, cost from A to Dis 170, i.e., (100 (A to B) + 50 (B to C) + 20 (C to D)]. Use Backtracking algorithm to reach the goal state H. Ignore paths with cost higher than 180, i.e., when traveling down an arc raises the total cost of the path to above 180 then you should not take that arc. Evaluate immediate child states of a parent state from left to right. Show below lists for each iteration CS 404 Artificial Intelligence Cs, for current state, state currently under consideration. SL, for state list, lists the states in the current path being tried. If a goal is found, SL contains the ordered list of states on the solution path. NSL, for new state list, contains nodes awaiting evaluation, i.e., nodes whose descendants have not yet been generated and searched. DE, for dead ends, lists states whose descendants have failed to contain a goal. If these states are encountered again, they will be detected as elements of De and eliminated from consideration immediately. -100 90 150 B N so 90 60 50 G 20 20 10 40 30 E H 60 50 F