0
$\begingroup$

I have a set path of $N$ destinations to be visited in order, knowing the distance $D_i$ between each one of them. I can traverse one node $i$ with the cost of $D_i \times r$ or traverse any $5$ nodes in order with a set cost of $B$. How can I find the most cost effective way to visit all the destinations using dynamic programming?

$\endgroup$
3
  • $\begingroup$ Please edit your question to clarify the problem statement. Can you define more clearly what $D_i$ represents? The distance between node $i$ and what? What do you mean by "any 5 nodes in order"? Can you credit where you encountered this and share the original wording? $\endgroup$
    – D.W.
    Commented Jun 5, 2020 at 20:59
  • $\begingroup$ What have you tried, and what progress have you made? We have general resources on how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. I suggest you read through those resources, apply the systematic approach listed there, and show us how far you got. Do you have a recursive algorithm? What subproblem decompositions have you tried so far? $\endgroup$
    – D.W.
    Commented Jun 5, 2020 at 21:00
  • 1
    $\begingroup$ Is $r$ the same for every node or is it a variable? @BenedictDhm $\endgroup$
    – Tom Finet
    Commented Jun 5, 2020 at 22:07

1 Answer 1

1
$\begingroup$

Let us number the destinations from $1$ to $N$ and define an array $c[N]$ where $c[i]$ is the minimum cost to travel to destination $1 \leq i \leq N$. We wish to calculate $c[N]$.

It is clear that $c[1] = D_1 \times r$, because if we find ourselves at destination $1$ we can only have gotten there by travelling one destination at a time, instead of travelling five destinations at a time.

The minimum cost of travelling to destination $2$ must be $c[2] = D_2 \times r + c[1]$ for identical reasons ($2 < 5$) as before. We add the minimum cost of reaching destination $1$ to the minimum cost of reaching destination $2$ because we must have travelled from destination $1$ to $2$.

Now we see that for destinations $i \geq 5$, that we could have reached them by travelling through five destinations at a time instead of the previous one destination at a time. This means $$c[i] = \min(B + c[i - 5], D_{i} \times r + c[i - 1])$$

Where $c[0] = 0$. From this pattern, we can calculate $c[N]$ in $O(N)$ time complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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