(30 points) Imagine you have a state space where a state is represented by a tuple of three positive integers (ij,k), and you have three actions: decrease i by 1 (as long as i> 0), decrease j by 1 (as long as j> 0), and decrease k by 1 (as long as k>0). The goal state is (0,0,0). Assume that a given search method does not revisit states it has already seen, and that whenever there are multiple successors for a given state it first expands the state you get from the action of decreasing i by 1 (if possible), then the action of decreasing j by 1, then k. 1. a. (1 point) What is the branching factor for this problem? b. (2 points) Is this state space a graph or a tree? c. If the initial state is (2,2,2): (3 points) Draw the subset of the state space that you can reach from this state. ii. i. (3 points) Label the states with the numbers 1, 2, 3, ..., to show the order in which they would be expanded by depth-first search. ii. (3 points) Label the states with the upper-case letters A, B, C,,to show the order in which they would be expanded by breadth-first search. iv. (3 points) Label the states with the lower-case letters a, b, C,.., to show the order in which they would be expanded by iterative deepening search d. If the initial state is (iJ,k), what is the time complexity, as a function of i, j, and k, of: i. (3 points) Depth-first search ii. (3 points) Breadth-first search ili. (3 points) Iterative deepening search (3 points) Would your answers to c change if the search method did not check for revisiting states (in other words, if you get to a state you've already been to you don't realize it and simply expand it again)? (3 points) Give an admissible heuristic for this problem. e. f. (30 points) Imagine you have a state space where a state is represented by a tuple of three positive integers (ij,k), and you have three actions: decrease i by 1 (as long as i> 0), decrease j by 1 (as long as j> 0), and decrease k by 1 (as long as k>0). The goal state is (0,0,0). Assume that a given search method does not revisit states it has already seen, and that whenever there are multiple successors for a given state it first expands the state you get from the action of decreasing i by 1 (if possible), then the action of decreasing j by 1, then k. 1. a. (1 point) What is the branching factor for this problem? b. (2 points) Is this state space a graph or a tree? c. If the initial state is (2,2,2): (3 points) Draw the subset of the state space that you can reach from this state. ii. i. (3 points) Label the states with the numbers 1, 2, 3, ..., to show the order in which they would be expanded by depth-first search. ii. (3 points) Label the states with the upper-case letters A, B, C,,to show the order in which they would be expanded by breadth-first search. iv. (3 points) Label the states with the lower-case letters a, b, C,.., to show the order in which they would be expanded by iterative deepening search d. If the initial state is (iJ,k), what is the time complexity, as a function of i, j, and k, of: i. (3 points) Depth-first search ii. (3 points) Breadth-first search ili. (3 points) Iterative deepening search (3 points) Would your answers to c change if the search method did not check for revisiting states (in other words, if you get to a state you've already been to you don't realize it and simply expand it again)? (3 points) Give an admissible heuristic for this problem. e. f