You are going on a long trip. You start on the road at mile post 0. Along the wa

Question

You are going on a long trip. You start on the road at mile post 0. Along the way there are n
hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. Theonly places you are allowed to stop are at these hotels, but you can choose which of the hotels youstop at. You must stop at the nal hotel (at distance an), which is your destination.You would ideally like to travel 300 miles a day, but this may not be possible (depending onthe spacing of the hotels). If you travel x miles during a day, the penalty for that day is (300x)2.

You want to plan your trip so as to minimize the total penalty—that is, the sum, over all traveldays, of the daily penalties. Give an ecient algorithm that determines the optimal sequence ofhotels at which to stop.

Explanation / Answer

The recursive formula for finding a solution for the given problem is :

For any stop ai there is an optimal route to get there which is the minimal cost of all routes from a0 to ai. This result from either taking the optimal route to ai-1 the it is going to ai , or taking the optimal route to ai-2 then going to ai , and so on , until looking at straight from 0 to ai. It gives us a recursive solution S for any Si of :

S0 = Si = min ( 0<=j ( Sj + cost ( j , i ) )

Where cost( j , i ) = ( 300 - ( ai-aj ) )2

For each Si we need to know all Sj values where j < I , to solve this problem dynamically we want to store the values of Si in a list sequentially. These values are only the minimum penalty for each stop, we will need a second list that for each ai stores the value of j, or the previous stop that yields the minimum penalty. We can than traverse this backwards to find the optimal route.

Algorithm is :

Bestroute(int a[ ])

{

int i , j;
int S[ ];

int R[ ];

S[0] = 0;

R[0] = 0;

for(i=1;i<=n;i++)

{

Previosstop = 0;

Minpenalty = infinity;

for( j = 0; j < i; j++)

{

if(S[j] + (300-(a[i] –a[j]))2 < minpenalty)

{

Minpenalty =   S[j] + (300-(a[i] –a[j]))2

Previousstop =j;

}

}

S[i] =mipenalty;

R[i] = previousstop;

}

}

The time complexity of this algorithm is we can count the number of comparisons. The outer for loop iterates n times , from 1 to n. the inner for loop iterates i times , then total number of comparisons are equal to 1+2+3+…..+n =n(n+1)/2. This is (n2).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.