1. 13
    1. 1

      It seems to me that the breadth first search approach is analogous to Dijkstra’s algorithm, with some parts of Dijkstra’s algorithm skipped over that are made unnecessary by the fact that all edges have a length of either 1 or 0.

      Anywhere where Dijkstra works, A* should work too iff you can find a useful admissible heuristic function. Perhaps “minimum number of non-diagonal moves which definitely must be performed”? e.g. on a 3x3 square, this would be the number 0 for the coordinate (0,0) and 1 for the coordinates (2, 3) and (1, 2).

Stories with similar links:

  1. The Myers diff algorithm: part 1 via teymour 9 months ago | 7 points | no comments