This is a rephrasing/different approach to Fitting curve with restricted relative orientations.
I have a directed acyclic graph that flows from Level 0 to Level 3500. Edges only occur between levels, not within levels (e.g. a Level 1 node connects to several Level 2 nodes, Level 2 nodes never connect to Level 2 nodes).
Each Level N node is connected to between 1 and 9 Level N+1 nodes. This causes the tree to grow very rapidly – Level 3500 has something like 8^3500 Nodes.
The goal is to find a path from Level 0 to Level 3500 that has the lowest maximum node value. I’ve highlighted a couple paths in the image. I only care about the maximum node value, not the total path value. I can also get a starting path that provides a good but non-optimal path.
While I would like to be able to find the optimal route, I would accept being able to find a route that is within say 20% or 50% of optimal.
My current approach:
- Calculated a good but non-optimal path to give a starting maximum node value (not shown)
- Proceed depth first, calculating node values as they are encountered. Using the right side of the graph I would calculate L0=0.1, L1=0.1, L2=0.2. The cost of this path is then 0.2
- Move up the graph until I reach a cost of <0.2 – in this case it occurs at L1=0.1.
- Investigate the other nodes connected to this node to see if they are lower value. L2=0.3, so no.
- Therefore move up the tree to L0 and investigate down again.
- L2=0.2, therefore it is not an improvement and can be ignored.
- L2=0.1, good, continue to investigate
- L3=0.1, good, therefore best path is now 0.1 and can’t be improved upon because L0=0.1.
Optimization occurs by moving up the tree (up levels) and choosing a different path down.
Due to the number of nodes, even short trees (10 levels) take too long to optimize.
If you are at Level 1, determining the values of the Level 2 nodes connected to you takes about 1/100 of a second.
Is there another approach to this problem?
