p07-0110(rock climbing Problem)

Rock Climbing ProblemPresented By: Aijaz Ali Roll# p07-0110 : 

Rock Climbing ProblemPresented By: Aijaz Ali Roll# p07-0110

Rock Climbing Problem : 

Rock Climbing Problem A rock climber wants to get from the bottom of a rock to the top by the safest possible path. At every step, he reaches for handholds above him; some holds are safer than other. From every place, he can only reach a few nearest handholds.

Rock climbing (cont) : 

Rock climbing (cont) At every step our climber can reach exactly three handholds: above, above and to the right and above and to the left. Suppose we have a wall instead of the rock. There is a table of “danger ratings” provided. The “Danger” of a path is the sum of danger ratings of all handholds on the path. 5 3 4 2

Rock Climbing (cont) : 

Rock Climbing (cont) We represent the wall as a table. Every cell of the table contains the danger rating of the corresponding block. The obvious greedy algorithm does not give an optimal solution. 2 5 4 2 The rating of this path is 13. The rating of an optimal path is 12. 4 1 2 5 However, we can solve this problem by a dynamic programming strategy in polynomial time.

Idea: once we know the rating of a path to every handhold on a layer, we can easily compute the ratings of the paths to the holds on the next layer. : 

Idea: once we know the rating of a path to every handhold on a layer, we can easily compute the ratings of the paths to the holds on the next layer. For the top layer, that gives us an answer to the problem itself.

For every handhold, there is only one “path” rating. Once we have reached a hold, we don’t need to know how we got there to move to the next level. : 

For every handhold, there is only one “path” rating. Once we have reached a hold, we don’t need to know how we got there to move to the next level. This is called an “optimal substructure” property. Once we know optimal solutions to subproblems, we can compute an optimal solution to the problem itself.

Recursive solution: : 

Recursive solution: To find the best way to get to stone j in row i, check the cost of getting to the stones (i-1,j-1), (i-1,j) and (i-1,j+1), and take the cheapest. Problem: each recursion level makes three calls for itself, making a total of 3n calls – too much!

Solution - memorization : 

Solution - memorization We query the value of A(i,j) over and over again. Instead of computing it each time, we can compute it once, and remember the value. A simple recurrence allows us to compute A(i,j) from values below.

Dynamic programming : 

Dynamic programming Step 1: Describe an array of values you want to compute. Step 2: Give a recurrence for computing later values from earlier (bottom-up). Step 3: Give a high-level program. Step 4: Show how to use values in the array to compute an optimal solution.

Rock climbing: step 1. : 

Rock climbing: step 1. Step 1: Describe an array of values you want to compute. For 1 ? i ? n and 1 ? j ? m, define A(i,j) to be the cumulative rating of the least dangerous path from the bottom to the hold (i,j). The rating of the best path to the top will be the minimal value in the last row of the array.

Rock climbing: step 2. : 

Rock climbing: step 2. Step 2: Give a recurrence for computing later values from earlier (bottom-up). Let C(i,j) be the rating of the hold (i,j). There are three cases for A(i,j): Left (j=1): C(i,j)+min{A(i-1,j),A(i-1,j+1)} Right (j=m): C(i,j)+min{A(i-1,j-1),A(i-1,j)} Middle: C(i,j)+min{A(i-1,j-1),A(i-1,j),A(i-1,j+1)} For the first row (i=1), A(i,j)=C(i,j).

Rock climbing: simpler step 2 : 

Rock climbing: simpler step 2 Add initialization row: A(0,j)=0. No danger to stand on the ground. Add two initialization columns: A(i,0)=A(i,m+1)=?. It is infinitely dangerous to try to hold on to the air where the wall ends. Now the recurrence becomes, for every i,j: A(i,j) = C(i,j)+min{A(i-1,j-1),A(i-1,j),A(i-1,j+1)}

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): Initialization: A(i,0)=A(i,m+1)=?, A(0,j)=0

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): The values in the first row are the same as C(i,j).

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): A(2,1)=5+min{?,3,2}=7.

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): A(2,1)=5+min{?,3,2}=7. A(2,2)=7+min{3,2,5}=9

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): A(2,1)=5+min{?,3,2}=7. A(2,2)=7+min{3,2,5}=9 A(2,3)=5+min{2,5,4}=7.

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): The best cumulative rating on the second row is 5.

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): The best cumulative rating on the third row is 7.

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): The best cumulative rating on the last row is 12.

Rock climbing: example : 

Rock climbing: example C(i,j): A(i,j): The best cumulative rating on the last row is 12. So the rating of the best path to the top is 12.

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): To find the actual path we need to retrace backwards the decisions made during the calculation of A(i,j).

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): The last hold was (4,4). To find the actual path we need to retrace backwards the decisions made during the calculation of A(i,j).

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): The hold before the last was (3,4), since min{13,7,8} was 7. To find the actual path we need to retrace backwards the decisions made during the calculation of A(i,j).

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): To find the actual path we need to retrace backwards the decisions made during the calculation of A(i,j). The hold before that was (2,5), since min{7,10,5} was 5.

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): To find the actual path we need to retrace backwards the decisions made during the calculation of A(i,j). Finally, the first hold was (1,4), since min{5,4,8} was 4.

Rock climbing example: step 4 : 

Rock climbing example: step 4 C(i,j): A(i,j): We are done!

Printing out the solution recursively : 

Printing out the solution recursively PrintBest(A,i,j) // Printing the best path ending at (i,j) if (i==0) OR (j=0) OR (j=m+1) return; if (A[i-1,j-1]<=A[i-1,j]) AND (A[i-1,j-1]<=A[i-1,j+1]) PrintBest(A,i-1,j-1); elseif (A[i-1,j]<=A[i-1,j-1]) AND (A[i-1,j]<=A[i-1,j+1]) PrintBest(A,i-1,j); elseif (A[i-1,j+1]<=A[i-1,j-1]) AND (A[i-1,j+1]<=A[i-1,j]) PrintBest(A,i-1,j+1); printf(i,j)

Slide 29: 

Thank You Any Question??