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?

$\endgroup$
2
  • 2
    $\begingroup$ Don't you need to get to the finish point too? $\endgroup$ Commented Feb 3, 2018 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$ Commented Feb 3, 2018 at 10:00

1 Answer 1

Reset to default
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)$.

$\endgroup$
4
  • $\begingroup$ But the recursion should probably be reversed to decrease complexity :) $\endgroup$ Commented Feb 11, 2018 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$ Commented Feb 11, 2018 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$ Commented Feb 12, 2018 at 20:58
  • $\begingroup$ I am also assuming that all $p_i$'s are non-negative. $\endgroup$ Commented Feb 13, 2018 at 11:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.