Changes between Version 1 and Version 2 of Ticket #15303, comment 41


Ignore:
Timestamp:
10/21/13 18:03:37 (9 years ago)
Author:
nbruin
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #15303, comment 41

    v1 v2  
    88> - 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.
    99
    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 storing 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.
     10Just 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.
    1111
    1212> - 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.