Changes between Version 1 and Version 2 of Ticket #15303, comment 41
- Timestamp:
- 10/21/13 18:03:37 (9 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #15303, comment 41
v1 v2 8 8 > - Breadth first search might be a good idea. I don't know how to efficiently implement it, but I guess this should be done at some point. 9 9 10 Just keep track of all discovered shortest paths (ordered by domain) into the codomain, and try to extend the shortest path. Merge the new-found paths (only store them if you found a shorter path or a path from a new domain). As soon as you found a path from the required domain, prune by cost (you only need to store keep storingpaths that could possibly lead to a cheaper path). Continue until all paths you have stored have been examined (and further path is longer than what you've found). The expensive part is still determining there is NO path, because no pruning can occur then.10 Just keep track of all discovered shortest paths (ordered by domain) into the codomain, and try to extend the shortest path. Merge the new-found paths (only store them if you found a shorter path or a path from a new domain). As soon as you found a path from the required domain, prune by cost (you only need to store paths that could possibly lead to a cheaper path). Continue until all paths you have stored have been examined (and further path is longer than what you've found). The expensive part is still determining there is NO path, because no pruning can occur then. 11 11 12 12 > - Calibrating the costs, such that `A->C->B` is guaranteed to have less cost than `A->D->B` for any example in which `A->C` is independent of but `A->D` is dependent on `A->B`, requires a case-by-case analysis. Not very practical, and moreover choosing parameters such that "it works" is kind of arbitrary. This is not a very clean solution either.