CS 188 Fall 2019 Section 1: Search1 Towers of HanoiThe Towers of Hanoi is a famous problem for studying recursion in computer science and recurrence equationsin discrete mathematics. We start with N discs of varying sizes on a peg (stacked in order according to size),and two empty pegs. We are allowed to move a disc from one peg to another, but we are never allowed to movea larger disc on top of a smaller disc. The goal is to move all the discs to the rightmost peg (see figure).In this problem, we will formulate the Towers of Hanoi as a search problem.(a) Propose a state representation for the problemOne possible state representation would be to store three lists, corresponding to which discs are on which peg.If we assume that the N discs are numbered in order of increasing size 1, ..., n, then we can represent each pegas an ordered list of integers corresponding to which discs are on that peg.(b) What is the size of the state space? If there are k pegs and n disks, then the size of the state space is kn.For this setup, the size is 3N.(c) What is the start state? ([1, ..., n], [], [])(d) From a given state, what actions are legal?We can pop the first integer from any list (i.e., peg) and push it onto the front of another list (peg), so long asit is smaller than the integer currently at the front of the list being pushed to (i.e., peg being moved to).(e) What is the goal test? Is the state the same as ([], [], [1, ..., n])?12 Search algorithms in actionFor each of the following graph search strategies, work out the order in which states are expanded, as wellas the path returned by graph search. In all cases, assume ties resolve in such a way that states with earlieralphabetical order are expanded first. Remember that in graph search, a state is expanded only once.a) Depth-first search.States Expanded: Start, A, C, D, GoalPath Returned: Start-A-C-D-Goalb) Breadth-first search.States Expanded: Start, A, B, D, C, GoalPath Returned: Start-D-Goalc) Uniform cost search.States Expanded: Start, A, B, D, C, GoalPath Returned:
View Full Document
Unlocking...