A server is given a stack of n pizzas. Each pizza is a different size. The server can flip the top k pizzas, reversing their order. The cost of flipping k pizzas is k. The servers goal is to order the pizzas from smallest (top) to largest (bottom), with minimal cost. More formally, the search states are all permutations of (1,2,3,...,n), and the goal is (1,2,3,...,n). Starting from a state, say (5,3,2,4,1), the action flip 3 has cost 3 and results in the state (2,3,5,4,1).

Consider the following heuristics for this problem: a. H1: The largest pizza that is out of place. b. H2: The number of pizzas out of place.

a) Which heuristics of the following are admissible? (i) H1, (ii) H2, (iii) H1+H2 (iv) max (H1,H2).

b) Does H1 dominate H2?

c). Is H1 consistent?

d) Is H2 consistent?

Show Your Work