0
$\begingroup$

I am given a minimal cost path problem where a person has a choice of picking where to work for each month from a list of 2 places(NYC,BOSTON). Each place has a living cost and if you decide to switch to another city the next month than you have to pay a fixed switch cost.

$$\begin{array}{c|c|c|} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\ \hline \text{NYC} & 5$ & 20$ & 5$ & 50$ & 1$ \\ \hline \text{BOSTON} & 1$ & 4$ & 400$ & 1$ & 2$ \\ \hline \end{array}$$

So for this example if we assume we calculate for 5 months, and have a switch cost of $20$$ than a minimal cost path would be(assuming we pick NYC as the starting point):

$$\{NYC, NYC, NYC, BOSTON, BOSTON\}=5+20+5+(1+20)+2=52$$

I am trying to come up with a good algorithm to find the minimal cost path and have came up with this:

  • Treat the problem as a shortest path problem.
  • Create a graph and let the nodes represent the city at the $ith$ month(Ex. $NYC_1$, $NYC_2$ $BOS_1$)
  • Make the edges from one node to another represent the cost of switching(Ex. 20$)

$s=$ starting node that you pick

$R$ = {$s$}

for $i = 1$ to $n$(for n months):

for every node $u$ that's adjacent to node $R[i]$:

pick the node that will cost less and add it to $R$

$i+=1$

return $R$

Would this be considered a good algorithm to find the minimal cost path?

$\endgroup$
  • $\begingroup$ Add some backtracking and book keeping to not try the same path twice. $\endgroup$ – Emil Sep 22 '16 at 6:48
1
$\begingroup$

If you wanted to model this as a shortest path in a weighted graph, then you should also use the algorithms that go with it, Dijkstra in particular.

In this case here I'd go for dynamic programming instead, since that's far easier.

Assume that you know the cheapest way to be at location $x$ at the end of month $n$, for all $x$ from your set of locations and for a given month $n$. Then you can compute the same information for the following month $n + 1$:

$$f(n+1, x) = c(n+1, x) + \min(\{f(n, x)\}\cup\{f(n,y)+20\mid y\in X\})$$

In words: The cost to be in place $x$ at the end of month $n+1$ is the cost of living in that place in that month plus the cost of arriving there at the beginning of the month. The latter is either the cost for already being there at the previous month, or the minimal cost for living in a different place up to that point and then switching.

You can easily implement this using nested loops: an outer loop which increments $n$ and an inner loop which iterates over all the $x$. You may take advantage of the fact that the term $\min(\{f(n,y)+20\mid y\in X\})$ does not depend on $x$, so you can compute that only once per $n$, and then you just have to compare two numbers.

This will easily give you the minimal cost after all the months. If you need the path, you should do some bookkeeping: for every $f(n+1,x)$ you compute, remember how you got there. That way you can simply pick the cheapest solution at the end of your months and then go back to see how to get there from the first month.

$\endgroup$
1
$\begingroup$

A greedy algorithm here does not necessarily find a shortest path. Consider the following counterexample. $$\begin{array}{|c|c|c|} \hline & \text{1} & \text{2} \\ \hline \text{NYC} & 5$ & 1$ \\ \hline \text{BOSTON} & 1$ & 100$ \\ \hline \end{array}$$

Your algorithm will choose Boston in the first month and NYC in the second month, with a total cost $1 + 20 + 1 = 22$\$. However, if you choose NYC in both months you would obtain a better plan with $5 + 1 = 6$\$.

$\endgroup$
  • $\begingroup$ I was under the impression that the starting node was input to the problem, something given and not something to be decided. But you can adapt your setup to something which starts in a fixed place and still gives suboptimal results for a greedy algorithm. $\endgroup$ – MvG Sep 22 '16 at 6:50

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.