please help CS

1 2 3 31 initial state 2. Consider the Towers of Hanoi puzzle shown here consisting of three disks (labeled 1, 2 and 3 based on their size) on pegs labeled A, B, and C. States are represented as a list of the disks on each peg, ordered from top to bottom. For example, the initial state pictured here is represented as 2 and the goal state with all disks on peg B as A B 1 2 -3- 3. where each dash "-" indicates an empty peg. We want to solve this problem using a state space formulation and the A* algorithm. Operators representing legal moves are all of the form move(disk, peg, newpeg) where disk is 1, 2 or 3, and peg and newpeg can be A, B or C. Each op- erator means that disk is moved from its current peg to a different newpeg, so for example, applying the specific operator move(1, A, B) to the initial state produces the successor state 2 31 The prerequisites for using an operator are that disk must be on peg and have no other disks on top of it, and that no other smaller disk is currently on newpeg (i.e., a disk can never be on top of a smaller disk). For any state n, let g(n) be the usual cost function: the number of moves used to reach state n from the start state. Let heuristic function h(n) be the number of disks in state n that are not on the goal peg B (e.g., the values of g and h for the start state are 0 and 3, respectively). a. Is h(n) an admissible heuristic function? Why or why not? b. Draw the search tree generated by the A* Algorithm using the above representation and g and h functions, starting from the initial state and going to the point in which six nodes have been expanded and their descendants added to the search tree. Whenever a duplicate state occurs (one that already appears in the search tree), just discard the duplicate and do not include it in the search tree. Thus your answer should show all non-duplicate nodes generated as successors to any expanded node during this search. Write each node's g, h and f values next to that node within parentheses. c. Put an asterisk next to all leaf nodes in your search tree produced in (b) that could possibly be the next node expanded by the A* algorithm were the search process to continue. d. Circle the leaf node in your search tree produced in (b) that is on a minimum cost path to a solution. 1 2 3 31 initial state 2. Consider the Towers of Hanoi puzzle shown here consisting of three disks (labeled 1, 2 and 3 based on their size) on pegs labeled A, B, and C. States are represented as a list of the disks on each peg, ordered from top to bottom. For example, the initial state pictured here is represented as 2 and the goal state with all disks on peg B as A B 1 2 -3- 3. where each dash "-" indicates an empty peg. We want to solve this problem using a state space formulation and the A* algorithm. Operators representing legal moves are all of the form move(disk, peg, newpeg) where disk is 1, 2 or 3, and peg and newpeg can be A, B or C. Each op- erator means that disk is moved from its current peg to a different newpeg, so for example, applying the specific operator move(1, A, B) to the initial state produces the successor state 2 31 The prerequisites for using an operator are that disk must be on peg and have no other disks on top of it, and that no other smaller disk is currently on newpeg (i.e., a disk can never be on top of a smaller disk). For any state n, let g(n) be the usual cost function: the number of moves used to reach state n from the start state. Let heuristic function h(n) be the number of disks in state n that are not on the goal peg B (e.g., the values of g and h for the start state are 0 and 3, respectively). a. Is h(n) an admissible heuristic function? Why or why not? b. Draw the search tree generated by the A* Algorithm using the above representation and g and h functions, starting from the initial state and going to the point in which six nodes have been expanded and their descendants added to the search tree. Whenever a duplicate state occurs (one that already appears in the search tree), just discard the duplicate and do not include it in the search tree. Thus your answer should show all non-duplicate nodes generated as successors to any expanded node during this search. Write each node's g, h and f values next to that node within parentheses. c. Put an asterisk next to all leaf nodes in your search tree produced in (b) that could possibly be the next node expanded by the A* algorithm were the search process to continue. d. Circle the leaf node in your search tree produced in (b) that is on a minimum cost path to a solution