Finding best path for moving across a matrix

Hi,

So imagine standing on one side of a matrix and then walking to the other, this is the main idea behind the problem.

So I have a 2D matrix of a random size, lets just say 100 x 100, which contains random number which correspond to elevations. So I can start anywhere in the first column and finish anywhere in the last column. However I can only move forward, and either 1 row up, stay in the same row or 1 row down (e.g. you can move from position [3,3] to [2,4] or [3,4] or [4,4]).

I don't have to calculate from the eastern edge of a matrix to the western side, i can do it the other way, or from the middle in both directions but I need to find the most cost effective way. The difference in elevation between the one step and the next one is the cost. Both an increase and decrease in elevation is treated the same (e.g. a change of 2 in elevation is the same as -2 in elevation).

Is there a algorithm which i should look into for this? Maybe any builtin matlab function which might help? Or any idea of how i would approach it.

Currently all i can think of is to figure out how many different possible routes there are from one side to the other and then calculate the 'cost' of each route and then find the one with the minimum cost. But this seems long and laborious. Any help is greatly appreciated. Thanks

By the way this is an assignment for me so please just help me with the idea behind it, and I can code it myself. Thanks

Answer 1

[Walter Roberson]

E = [ ...
    3   6   3   7   2   5
    1   4   2   4   1   4
    7   9   5   6   9   2
    10   8   4   3   10   5];

[r, c] = size(E);
N = @(R,C) sprintf('(%d,%d)',R,C);

M = {};
for R = 1 : r - 1
    for C = 1 : c - 1
        t = {N(R, C), N(R,C+1),  abs(E(R,C)-E(R,C+1)); ...
             N(R, C), N(R+1,C),   abs(E(R,C)-E(R+1,C))};
        M = [M;t];
    end
    t = {N(R,c), N(R+1,c), abs(E(R,end)-E(R+1,end))};
    M = [M;t];
end

for C = 1 : c - 1
    t = {N(r,C), N(r,C+1), abs(E(end,C)-E(end,C+1))};
    M = [M;t];
end

%now cross-check that the array was built correctly
for L = 1 : size(M,1)
    s = M{L,1}; rc1 = sscanf(s, '(%d,%d)');
    d = M{L,2}; rc2 = sscanf(d, '(%d,%d)');
    v = M{L,3};
    t = abs(E(rc1(1),rc1(2))-E(rc2(1),rc2(2)));
    if t ~= v
        fprintf('Error in M(%d,:): from %s to %s expected %d was %d\n', L, s, d, t, v);
    end
end

%cross-check done. Plot the connection graph

G = graph(M(:,1), M(:,2), cell2mat(M(:,3)));

plot(G);

routes = cell(r,r);
routecost = zeros(r,r);
for SR = 1 : r
  for ER = 1 : r
    [routes{SR, ER}, routecost(SR,ER)] = shortestpath(G, N(SR,1), N(ER,6));
  end
end

routesteps = cellfun(@length, routes);
[beststart, bestend] = find(routesteps == min(routesteps(:)) & routecost == min(routecost(:)));

if isempty(beststart)
  fprintf('There are no routes that are both minimum steps and minimum cost');
else
  for IDX = 1 : length(beststart)
    st = beststart(IDX); en = bestend(IDX);
    fprintf('E(%d,1) to E(%d,%d) is %d steps and cost %d\n', st, en, c, routesteps(st, en), routecost(st, en));
    disp(routes{st, en})
  end
end

[Walter Roberson]

Mr. Green commented to me: "Didn't want the code"

[Walter Roberson]

Summary:

1. create a graph object containing the permitted connections, with the cost of the link being the change in elevation
2. use shortestpath() on the graph object to calculate the shortest path between two fixed points.
3. You can repeat the shortestpath() for each pair of potential start and end points

Answer 2

[Lovernicus III]

Probably too late for your assignment, but what you want is called Dijkstra's algorithm, or if you have any information about the random numbers, you can get fancier and use A* (pronounced A star).

Dijkstra's works by looking at all the possible steps you can take from your starting point, p0, and saving the step cost as the lowest known cost to get to each new point p1, p2, etc... (because in the first step that is the only known path to each point). Save all of the new points you've visited and their costs in a 'frontier list' sorted by the cost it took to get there.

Now, look at the lowest cost point in that list, lets say it was p1, and look at where you can go from there in one step, p2, p5, etc... If you haven't been there before, like p5, save the total cost it took to get to p5 as the best known cost of getting there; again, because it is the only known path there, now add p5 to the frontier list. If you have been there before, like p2, keep the better of the previous best cost vs the new total cost, which is the cost of getting to p1 plus the transition cost from p1 to p2. In all cases, take p1 off the frontier list and put it on a 'closed point' list so you don't visit it again.

Next re-sort your frontier list and repeat the above paragraph until you get to your destination and every point left on the frontier list has a cost at least as high as the destination point.

This will always find a shortest path (but only one if there are several) and you avoid looking at every possible path.

If you can start at any point on the side of the matrix, make a 'dummy' starting point that has 0 transition cost to each of the possible starting points and do the same for the end points to another dummy point.

Answer 3

[Image Analyst]

I've done it before with "dynamic programming". Sorry, I don't have any MATLAB code for you.

[Mr.Green]

what is dynamic programming?

[Image Analyst]

See https://en.wikipedia.org/wiki/Dynamic_programming

and http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/