Speeding up the trajectory graph algorithm
I have a rectangular mesh DAG where the horizontal edges always point to the right and the vertical edges always point downward. Edges have positive costs associated with them. Due to the rectangular format, the nodes refer to the null row / column. Here's a sample graph:
Now I want to search. The starting vertex will always be in the left column (column with index 0) and in the upper half of the graph. This means that I will pick up the start as (0,0), (1,0), (2,0), (3,0) or (4,0). The top of the target is always in the right column (column with index 6) and "matches" the start top:
the beginning of the top (0,0) corresponds to the top of the target (5,6)
the beginning of the top (1,0) corresponds to the top of the target (6.6)
the beginning of the top (2.0) corresponds to the top of the target (7.6)
the beginning of the top (3.0) corresponds to the top of the target (8.6)
the beginning of the top (4,0) corresponds to the top of the target (9.6)
I only mention this to demonstrate that the end goal will always be achievable. Perhaps this is not very important for my actual question.
What I want to know is which search algorithm should I use to find the path from start to target? I am using C ++ and have access to the Boost Graph library.
For those interested, I'm trying to implement Fuchs' suggestions from his article "Optimal Surface Reconstruction from Planar Contours .
I looked at A * but honestly didn't get it, and there was no way the heuristic works, or even can I come up with one!
Because of the rectangular shape and correct edge directions, I realized that there might be a well-suited algorithm. I considered Dijkstra
but the doc I mention says that there are faster algorithms (but annoying that no implementation is provided for me), plus that
with one source and I think I want one pair.
source to share
So this is your problem,
- DAG without cycles
- weight> 0
- Left weight <Correct weight.
You can use a simple and comprehensive search that identifies all possible routes. So you have an O (NxN) algorithm. And then you will take the shortest path. This is not a very smart solution, but it is effective.
But I suppose you want to be smarter than that, let's assume that if a particular node can be reached from two nodes, you can find the minimum weights on two nodes, plus the cost to arrive at the current node. You can think of this as an extension of the previous comprehensive search.
Remember DAG can be drawn inline. For DAG linearization, here's an interesting resource.
Now you have just defined a recursive algorithm.
MinimumPath(A,B) = MinimumPath(MinimumPath(A,C)+MinimumPath(A,D)+,MinimumPath(...)+MinimumPath(...))
Of course the starting point of the recursion is
MinimumPath(Source,Source)
which is 0, of course. As far as I know, there is no algorithm from boost for this. But this is quite easy to implement.
Nice implementation here .
If for some reason you don't have a DAG, Dijkstra or Bellman-Ford should be used.
source to share
if I am not mistaken, from the explanation, this is indeed an optimal path problem and not a search problem as the target is known. In optimization, I don't think you can avoid an exhaustive search if you want an optimal path rather than a rough path.
From the article, it seems like you actually split the space many times and then run the algorithm. This will reduce your N closer to a constant in the entire surface context, making O (N ^ 2) not too bad.
Speaking maybe dynamic programming would be a good strategy, where N will be limited to the difference between your start and node target. Here is an example of a genomic alignment shape. Just an illustration to give you an idea of how it works.
Construct an N array of N cost values that are set to 0 or some default values.
#
For i in size N:
For j in size N:
#cost of getting here from i-1 or j-1
cost[i,j] = min(cost[i-1,j] + i edge cost , cost[i,j-1] + j edge cost)
Once your table is complete, start at the bottom right corner. Starting with your target, select to go to the node with the lowest receive cost. Make your way back, choosing the lowest value, until you reach the start node (or rather the array entry corresponding to the start node). This should give you the optimal path very simply.
Dynamic programming works by solving optimizations for smaller subproblems. In this case, sub-problems are optimal paths to previous nodes. I think the rectangular nature of your graph makes this a good fit.
source to share