This one's a bit of a spin on your ordinary shortest/least-cost path problem, and while I do have some general ideas for approaching it, it's got me a bit stumped. I figured the STEM gods who reside in this sacred place that is Stack Overflow might know of a solution which they'd see fit to bestow upon me, or if not, they might still enjoy taking a crack at this one.
A square grid, aligned to the X and Y axes, exists whose dimensions are n by m (where (0,0) denotes the leftmost and bottommost corner, and (n-1, m-1) denotes the rightmost and topmost corner). From any given position, you are able to move a certain number of steps in a certain direction, as defined by a given move-set. In this problem we consider a move-set which allows any one of the four following moves to be selected from any point on the grid:
From any given position (Xi, Yj), each of these moves has an associated cost given by r1(Xi, Yj), r2(Xi, Yj), u1(Xi, Yj), u2(Xi, Yj), respectively. (Note that the cost of a move may be different depending on which position it is made from).
Your goal is to move from (0,0) to (n-1, m-1) with the minimum total cost.
Design an efficient algorithm to do so. Derive the time complexity.
(problem statement attached image)
Naïve approach: Calculate the total weight of every possible path from (0, 0) to (n-1, m-1), and select the one with the minimum cost.
Problem with this approach: becomes infeasible almost immediately as n and m increase.
Interestingly, it seems that the total possible number of ways to go from X=0 to X = n-1 via some sequence of r1 and r2 moves (without any up-moves) is Fibonacci(n-1), = the n-1th term of the Fibonacci sequence (where Fibonacci(0)=0, Fibonacci(1)=1, Fibonacci(2)=1, etc.). Same story for u1 and u2 moves to get from Y=0 to Y = m-1. Although, I'm not sure if it's actually relevant to consider this? ...
Anyways, it's clear that a more efficient technique will be needed.
Greedy approach: Make the locally optimal choice at each step (e.g. just choose the move with the best (move_weight)/(spaces_moved) ratio at the current position every turn, as long as it doesn't overshoot n-1 or m-1).
Problem with this approach: has good time complexity, but I don't think that simply choosing the locally optimal choice at each position guarantees a globally optimal path. For example, the locally best move at the current position might be r1 with weight 5, followed by u2 next move with weight 8; but it may be the case that moving u2 with weight 7 this turn allows us to move r1 with weight 3 for our next move. Then, it is clear that this greedy approach is not globally optimal, since it produced a path with cost=13 when there existed a different path to the same destination with cost=10.
...And this is about where I'm at right now. I'm considering trying some sort of solution involving trees (like game trees?) or maybe some sort of modification of Dijkstra's Shortest Path algorithm next? Any solutions or insights would be greatly appreciated :)
This is exactly the shortest path problem. You can use Dijkstra's algorithm. The algorithm consists in storing the "shortest distance known so far" from every node to the destination node (n-1, m-1). Or alternatively, storing the "shortest distance known so far" from every node to the start node (0, 0).
So you create an n*m array to store all these distances.
Initially you only know that node (n-1, m-1) is at distance 0 from itself; and you don't know any path from any other node to (n-1, m-1); so you initialize the distance for each node as 0 for (n-1, m-1), and +Infinity for every other node.
Then iteratively, pick a node, and update its shortest known by peeking at its neighbours and choosing the most useful neighbour:
dist[x, y] = min(
dist[x, y],
dist[x+1, y] + cost_r1[x,y], // being careful if x+1 is out of bounds
dist[x+2, y] + cost_r2[x,y], // being careful if x+2 is out of bounds
dist[x, y+1] + cost_u1[x,y], // being careful if y+1 is out of bounds
dist[x, y+2] + cost_u2[x,y], // being careful if y+2 is out of bounds
)
Dijkstra's algorithm stop condition is basically "continue updating until there is nothing to update". This can be implemented in a variety of ways.
In our case, we know the graph is a grid, and we know we only ever move right or up, so we can be smart and update the distances in the correct order directly; the only thing we have to make sure of is that when calculating the distance from (x,y), we must already have calculated the four distances from (x+1,y), (x+2,y), (x,y+1) and (x,y+1).
Because we have to be extra careful with those +1 and +2 not getting us out of the array, you can either handle columns n-1 and n-2 and rows m-1 and m-2 before you handle the rest of the array, or you can write a wrapper function dist(x,y) which returns either dist[x,y] if it exists, or +Infinity if x or y is out of bounds.
Below, I chose not to use wrapper functions, and instead I made separate loops for the cells in which not all four options u1, u2, r1, r2 are available.
dist[n-1, m-1] = 0
dist[n-2, m-1] = cost_r1[n-2, m-1]
for (x = n-3; x >= 0; x--)
dist[x, m-1] = min(dist[x+1,m-1] + cost_r1[x,m-1], dist[x+2,m-1] + cost_r2[x,m-1])
dist[n-1, m-2] = cost_u1[n-1, m-2]
for (y = m-3; y >= 0; y--)
dist[n-1, y] = min(dist[n-1,y+1] + cost_u1[n-1,y], dist[n-1,y+2] + cost_u2[n-1,y])
dist[n-2, m-2] = min(...r1, ...u1)
for (x = n-3; x >= 0; --x)
dist[x, m-2] = min(...r1, ...r2, ...u1)
for (y = m-3; y >= 0; --y)
dist[n-2, y] = min(...r1, ...u1, ...u2)
for (x = n-3; x >= 0; x--)
for (y = m-3; y >= 0; y--)
dist[x,y] = min(...r1, ...r2, ...u1, ...u2)
Once you've done that, you have in every cell of our array dist the distance from (x,y) to (n-1, m-1). In particular, cell (0,0) contains the distance from (0, 0) to (n-1, m-1).
Then if you are interested, not just in the distance, but the actual path to follow, you can retrieve it in linear time using this array by starting at (0, 0) and navigating to the neighbouring cell which minimizes the cost (i.e., the one that was would be chosen by the min(..., ..., ..., ...) operation).