0
$\begingroup$

So consider a person located at point $c$ (let's say $c=140$). Given a set of other points, for example, $P = \{100, 50, 190\}$. The cost of traveling to a point $P_i$ is then $|c-P_i|$. Points can be traversed in any order, so let's do them in the order of the example set.

This leads us having to travel the distance $40+50+140 = 230$. A better option would have been to travel the order of $\{190, 100, 50\}$ which gives the distance $50+90+50 = 190$.

I want to try to set up a dynamic programming solution to this problem. I realize that at each step I have to consider the option of traveling to all available points (i.e discover all possible paths, and comparing them all to find the shortest one)

First things first I'd want to set up a recursive formula for the problem, but I can't seem to find out how... I feel like once I have a recursive formula the rest should work itself out.

$\endgroup$
  • $\begingroup$ Intuitively, the solution is to go to the closest extremal point, and then traverse the rest in order. $\endgroup$ – Yuval Filmus Feb 19 at 14:57
  • $\begingroup$ Yeah I figured as much, but I'm more interested in the solution wherein a recursive formula can be applied to an unsorted set $\endgroup$ – user3380251 Feb 19 at 15:09
  • $\begingroup$ Sometimes dynamic programming just isn't the right technique. $\endgroup$ – Yuval Filmus Feb 19 at 15:54
  • $\begingroup$ That is true, and I realize that, however out of interest I would still want to apply dynamic programming techniques to solve this problem $\endgroup$ – user3380251 Feb 19 at 16:16
  • 1
    $\begingroup$ You'll have to store the shortest path visiting a certain set of points and ending at a specific point. The algorithm will run in exponential time. $\endgroup$ – Yuval Filmus Feb 19 at 16:19

Your Answer

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

Browse other questions tagged or ask your own question.