Re:Ask HN: What is the weirdest or most surreal (recent) tec...
by kragen on Tuesday January 24, 2023 @01:28PM
(#34507777)
i would rather say that a* is an optimization of dijkstra's algorithm
they both solve the single-pair shortest-path problem in digraphs with nonnegative arc weights
a* which explores nodes in a different, better order thank dijkstra's algorithm, but can only be applied in cases where you can compute an admissible heuristic
that makes it less general than dijkstra's algorithm, which works to find shortest paths in any digraph with nonnegative arc weights, not just the ones where an admissible heuristic can be computed
any problem you can solve with a* can be solved with dijkstra's algorithm (usually more slowly) but the converse is not true
now, in a sense, a* with an inadmissible heuristic such as h(v)≡0 is 'more general' in the sense that it can emulate dijkstra's algorithm and also do other things; you could say that a* is a class of algorithms of which dijkstra's algorithm is one
they both solve the single-pair shortest-path problem in digraphs with nonnegative arc weights
a* which explores nodes in a different, better order thank dijkstra's algorithm, but can only be applied in cases where you can compute an admissible heuristic
that makes it less general than dijkstra's algorithm, which works to find shortest paths in any digraph with nonnegative arc weights, not just the ones where an admissible heuristic can be computed
any problem you can solve with a* can be solved with dijkstra's algorithm (usually more slowly) but the converse is not true
now, in a sense, a* with an inadmissible heuristic such as h(v)≡0 is 'more general' in the sense that it can emulate dijkstra's algorithm and also do other things; you could say that a* is a class of algorithms of which dijkstra's algorithm is one