0
$\begingroup$

We want to hike over a direct route from starting point $s$ to finish point $f$. We're given a list $p_1<p_2< \dots <p_n$ where the hotel at index $i$ is located $p_i$ kilometers from the start of the route. Throughout the travel we stop each night at a different hotel. The travel is time limited therefore we must finish the travel over $t$ days ($t<n$). The difficulty of walking a certain day is defined as $d^2$, the square of distance traveled.

We want to choose the stops in such a way that we minimize the sum of difficulty over the course of the travel (such that the overall difficulty is the lowest). Find the recurrence relation which describes the problem.

I encountered this problem in the context of dynamic programming. I don't understand how the problem can be described with a recurrence relation here.

This is a sample I drew:

enter image description here

For example we need to plan the travel for $2$ days. Then wouldn't we choose the distances from $p_1$ to $p_2$ and from $p_2$ to $p_3$ as they are minimal distances and hence will yield minimal squares?

Isn't this a matter of just sorting the distances and choosing $t$ minimal ones?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Don't you need to get to the finish point too? $\endgroup$ – user856 Feb 3 '18 at 9:57
  • $\begingroup$ @Rahul I think I see now. So wouldn't this be a variation of knapsack problem where we want minimum instead of maximum? $\endgroup$ – Yos Feb 3 '18 at 10:00
1
$\begingroup$

I observe that:

  1. you are required to stay at a different hotel for $t$ nights and
  2. it never makes sense to go backwards.

We can compute the minimal cost recursively on $t$, the number of remaining stops to make. Define $C(r,m)$ as the minimal cost of a trip that starts at hotel $m$ and visits $r$ different hotels, each with index $> m$.

We then have:

$C(r,m) = \min_{m<i< n-r} \left[ (p_i-p_m)^2 + C(r-1,i) \right]$ if $r>0$ and

$C(0,m) = (p_n - p_m)^2$ (to account for the last day, I assume $p_n$ represents $f$).

If we also define $p_0=0$, the desired answer is $C(t,0)$.

Improve this answer
$\endgroup$
  • $\begingroup$ But the recursion should probably be reversed to decrease complexity :) $\endgroup$ – Fons Feb 11 '18 at 17:35
  • $\begingroup$ I think the idea is right, but I don't follow the formulas. It seems to me that you should be minimizing over $m < i < n-r,$ because hotel $i$ is the next hotel to visit after hotel $m$ and there must be at least $r-1$ hotels remaining after hotel $i$. I also think you mean $C(r,m)$ to be the cost of completing the journey starting at hotel $m$ in $r$ days. You say "visiting hotels with index $\ge m$" but you must mean "index > $m$" or the term $(p_i-p_m)^2$ makes no sense. $\endgroup$ – saulspatz Feb 11 '18 at 18:39
  • $\begingroup$ You are right! The case C(0,m) should also be defined separately to make sure that the goal is reached. $\endgroup$ – Fons Feb 12 '18 at 20:58
  • $\begingroup$ I am also assuming that all $p_i$'s are non-negative. $\endgroup$ – Fons Feb 13 '18 at 11:38

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.