Finding lowest cost path - dynamic

Question

I have to write a dynamic algorithm for finding lowest cost path. So I have a point that I have to visit. I can jump only between points by distance - 5 I have an array of distance from 0-point for example (1 3 5 10 15 20 21 22). Each move cost me 1. So the best path will be to move 1->5->15->20->22 (3 and 21 I can skip).

Can you give me so hints, how to program it dynamically? I was thinking to make something like this: Find the solution for array[0] and array[1] (that's easy there is only one solution from to 1 (1->3)) then add array[2], and find the best solution (1->5 also there is a solution 1->3->5 but that's going to cost me 2 moves) then for 4 points, 5 etc.

But don't know how to start to make my algorithm to be written correct and dynamic. I know I can make greedy algorithm, but that's not the point of the task... Can you give me any hints? How to start? How to keep solutions? and find the best ones?

Answer 1

Another approach (graph search):

Step 1: Parse initial data

Consider each point is a node of and each possible move is a path between two nodes.

Create a N*N matrix(graph) and compute the path value between each nodes.

• path(A,B) = 1 : if abs(nodeA - nodeB) <= 5

else

• path(A,B) = MAXINT

Step 2: Compute the shortest path

Apply a fast graph search algorithm (eg: Dijkstra's algorithm) to your matrix.

Answer 2

It would seem to me that, for the problem given, greedy is always the best.

However, in general, I would progress from left to right through the list, keeping a complete list of all the possibilities; if there are two or more possibilities that would land you at the same point, prune every possibility that is not the most efficient (depending on the question, you may also prune all but one of identically efficient solutions). Also regularly prune any solution which is a dead end.

So, for your example (I will list each possibility in brackets):

• Move to the first item in your array - 1. You have to start here, so make this your list of possibilities: (1)
• Move to the next item in your array - 3
• For each item in your list of possibilities, copy it, add the item in your array, and then add it to the list of possibilities: (1),(1,3)
• Eliminate any invalid possibilities, or possibilities which can never be valid (none yet)
• For any pair of possibilities which end in the same place, strip all but the most efficient (none yet)
• Move to the next item in your list - 5
• For each item in your list of possibilities, copy it, add the item in your array, and then add it to the list of possibilities: (1),(1,3),(1,5),(1,3,5)
• Eliminate any invalid possibilities, or possibilities which can never be valid (none yet)
• For any pair of possibilities which end in the same place, strip all but the most efficient. (1,5) and (1,3,5) both end on 5, and (1,5) is more efficient, so delete (1,3,5).
• Move to the next item in your list - 10
• For each item in your list of possibilities, copy it, add the item in your array, and then add it to the list of possibilities: (1),(1,3),(1,5),(1,10),(1,3,10),(1,5,10)
• Eliminate any invalid possibilities, or possibilities which can never be valid. (1,10) and (1,3,10) are invalid, and (1) and (1,3) will never be valid (hypothetically, (1,5) could be valid, if this 10 is followed by another 10). This leaves (1,5),(1,5,10)
• For any pair of possibilities which end in the same place, strip all but the most efficient (none found).
• Move to the next item in your list - 15
• For each item in your list of possibilities, copy it, add the item in your array, and then add it to the list of possibilities: (1,5),(1,5,10),(1,5,15),(1,5,10,15),
• Eliminate any invalid possibilities, or possibilities which can never be valid. (1,5,15) is invalid, and (1,5) will never be valid. This leaves (1,5,10),(1,5,10,15)
• For any pair of possibilities which end in the same place, strip all but the most efficient (none found).
• Wash, rinse, repeat.

So the general method is:

• make things a little more complicated
• remove any you can remove