0
$\begingroup$

There are n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly d days (i.e have to make d-1 stops in between). If you travel x miles during a day, the cost for that day is x^2. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.

I came up with this dp solution:

Let dp(i) be the minimum cost such that the last stop is hotel i. Base case: dp(0)=0.

To compute dp(i), I consider all possible places 0<=k<i, that we might have stopped before. Thus, the recurrence relation becomes:

for i=1;i<=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k<i;k++
    if (dp(i)>dp(k)+(ai-ak)^2)
      dp(i) = dp(k)+(ai-ak)^2)
      prev(i) = k 

How do we make sure that this algorithm takes exactly d stops?

$\endgroup$
0
$\begingroup$

For this problem, you should be using a two dimensional table where dp(i,j) is the minimum cost such that hotel i is reached in exactly j days.

If i<j there is no possible solution.

If i=j there is the solution where every hotel is visited.

If i>j, compare

  • dp(i-1,j-1) + (a(i) - a(i-1))^2
  • dp(i-2,j-1) + (a(i) - a(i-2))^2
  • ... as long as i-n>=j-1

And pick the minimum.

To find the optimal sequence, either store the previous hotel visited in the table or go back through the table starting at dp(n,d).

$\endgroup$
1
$\begingroup$

Start with yinnosanders algorithm, then try to get faster than $O (n^3)$ in typical cases:

With your cost model, travelling a total distance of x miles in d days costs at least $x^2 / d$. If you could stop anywhere you like, you would travel $a_n / d$ miles every day.

First find a reasonably good set of stops: On each day, when there are d' days left, you pick the hotel whose distance is closest to the remaining distance, divided by d'. This gives you an upper limit L for the cost of the optimal journey.

Now jinnosanders suggests that you calculate dp(i,j). But first we calculate a lower limit for the cost of any journey that involves stopping at hotel i on day j: The cost would be lowest if you drove the same distance on each of the first j days, and the same distance on the remaining last days. The cost is at least $a_i^2 \space/\space j\space+\space(a_n - a_i)^2/(d-j)$. If this cost is higher than the upper limit L for the best solution that we found earlier, then there is no need to calculate dp (i, j) and we set dp (i, j) = infinity instead.

We will have dp (j-1, j-1) ≥ dp (j, j-1) ≥ dp (j+1, j-1) ... so when we calculate dp (i, j), we stop when dp (i-n, j-1) = infinity. This should work considerably faster than O (n^3) in typical cases if the hotels are reasonably close to equidistant.

$\endgroup$
  • $\begingroup$ What guarantee do you have that your upper limit calculation will result in a possible journey? It seems like you need to add the condition in paragraph 3 that a hotel can only be selected if there are at least d' hotels after it. $\endgroup$ – yinnonsanders Oct 25 '17 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.