Question

Solve the pancake sorting problem with the initial state of 2,1,3,2 and the final state of 1,2,2,3. Note that there are two pancakes of size 2 to reduce the number of states needed. The arc-cost is the number of pancakes flipped.

a. Apply A* search using the heuristic h1 = the index of the largest pancake that is out of place.

b. Apply A* search using the heuristic h2 = the number of pancakes out of position.

c. Apply UCS

Use graph search (keeping track of closed nodes) wheneverapplicable; that is, in your work, do not show children that are found in the set of already closed nodes.

Answer 1

Pancake Sorting Algorithm ,unlike a traditional sorting algorithm, helps to sort the arrays with the fewest comparisons possible.  The main aim is to sort the sequence in as few reversals as possible.

Basic steps to be followed for this algorithm are :

1) Let given array be arr[] and size of array be n. let currentsize be equal to n initially. keep reducing the currentsize by 1 while it is greater than 1.

2) while (currentsize is greater than 1)
……a) Find index of the maximum element in arr[0..curr_szie-1]. Let the index be ‘mi’
……b) Call a function flip(arr,mi) which will reverse the array elements from 0 to mi.
……c) Call a function flip(arr,mi) which will reverse the array elements from 0 to (currentsize-1).

 static int pancakeSort(int arr[], int n) { for (int curr_size = n; curr_size > 1; --curr_size) { int mi = findMax(arr, curr_size); if (mi != curr_size-1) { flip(arr, mi); flip(arr, curr_size-1); } } return 0; } static void flip(int arr[], int i) { int temp, start = 0; while (start < i) { temp = arr[start]; arr[start] = arr[i]; arr[i] = temp; start++; i--; } } static int findMax(int arr[], int n) { int mi, i; for (mi = 0, i = 0; i < n; ++i) if (arr[i] > arr[mi]) mi = i; return mi; } 

for the given intial states : 2 1 3 2 , n=4 and currsize=4, [ ] this signifies the current state of elements in array.

1) maxindex=2, hence flip elements of array from (0,2) [ 3 1 2 2 ] and since currsize=4 ,again flip array elements from (0,3) , [ 2 2 1 3] and currsize=currsize-1=3;

Array : [ 2 2 1 3]

2) maxindex=0, hence flip elements of array from (0,0) [ 2 2 1 3 ] and since currsize=3 ,again flip array elements from (0,2) , [ 1 2 2 3] and currsize=currsize-1=2;

Array : [1 2 2 3] // array is sorted here itself with two flips.

3) maxindex=1, hence flip elements of array from (0,1) [ 2 1 2 3 ] and since currsize=2 ,again flip array elements from (0,1) , [1 2 2 3] and currsize=currsize-1=1;

Array : [ 1 2 2 3]

Hence the array is sorted.