(4+4+4+5+8+5+5) 35marks
In the ¡°pancake puzzle¡± a kitchen cook produces stacks of N differently sized pancakes. Before they can be served the pancakes must be nicely sorted by size, so that the smallest one is always on top. We do this with the help of a spatula, which can be used to flip some or all of the pancakes in the stack, thus reversing their order. Figure 1 shows an example. Our job is to sort any given stack using the fewest possible flips.
Figure 1 (a) In this size 5 pancake problem the stack is initially arranged as [3, 1, 2, 5, 4]. (b) As an example, we insert the spatula between the 3rd and 4th pancake and flip, which produces a new state [2, 1, 3, 5, 4].
Throughout the questions below, when doing a search, give values for f(n), g(n) and h(n) at each node n.
Copyright By PowCoder代写 加微信 powcoder
(a)Construct a non-trivial heuristic, h1, for a state of the size 5 pancake puzzle (non-trivial means h1 is not always zero). Describe your heuristic and then demonstrate (or prove) it is admissible.
(b) Construct a different non-trivial heuristic, h2, for the size 5 pancake puzzle. Describe h2 then show that it too is also admissible.
(c) Construct another admissible heuristic, h3,which dominates both h1 and h2. Describe then demonstrate (or prove) that h3 is admissible.
(d)Choose one of your admissible heuristics, h1, h2 or h3. Using your chosen heuristic, apply A* search for the problem instance in Figure 1 (left). Show the graph that results after the first 12 expansion steps. Label the nodes clearly. For each one show the state of the pancake stack, the corresponding g-, h- and f-value, and the parent node. Also indicate the membership of OPEN and CLOSED after the 12th expansion step.
(e) Report the cost of the plan (number of flips) and the corresponding sequence of states eventually returned by A*. In one or two paragraphs, state clearly why you believe that this is the minimum number of steps. For example, you might refer to an enumerated proof generated by the complete A* search (included as an appendix) or you can refer to any other sufficient argument.
(f) Take your chosen heuristic from part (d) and change it to derive a new heuristic h4 which works as follows: at the goal state the returned value is 0, but if we are not in a goal state and the 5th pancake is at the bottom of the stack then the heuristic value is very large (>= 1000). Is h4 admissible? Explain why or why not using examples as appropriate.
(g)What would happen if we do a greedy best-first search using h4? Show the graph that results after the first 12 expansion steps of this algorithm. Explain your answer, and show all working. Use the same style of presentation for your answer as in question (d).
Hint: Familiarity with chapter 3 of Russel and Norvig, and associated lecture material, may be very helpful when attempting this question.
Give clear answers and justifications
As a general rule, don¡¯t just give a number or an answer like `Yes¡¯ or `No¡¯ without at least some clear and sufficient explanation – or, otherwise, you risk being awarded 0 marks for the relevant exercise. Make it easy for the person marking your work to follow your reasoning.
If there is an elegant way of answering a question without unnecessary extra work, try to do it that way. More generally, more elegant solutions are preferable – and might at least sometimes be given more marks. Show your working and make your answers clear
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com