3 ms·
This is interesting. I wonder whether the perceived (in a few minutes of testing) superiority of best-first-search with Chebyshev is some feature of the impleme
by glogla 15y ago
This is interesting. I wonder whether the perceived (in a few minutes of testing) superiority of best-first-search with Chebyshev is some feature of the implementation or fact, because they "forgot" to tell us about both the algorithm and the metric in AI classes.
- keeperofdakeys 15y agoThe problem is Best-First Search (Best First Search) isn't optimal (finds the path of lowest cost), whereas A* and Dijkstra/UCS (Uniform Cost Search) are. (It should be noted Best-First Search is a family of search algorithms, of which A* and Dijkstra are a part of). Here, Best-First Search uses geometric distance (estimated with a heuristic) from the goal to prioritise nodes. UCS uses pathcost only and A* uses the sum of pathcost and heuristic. This means this implementation of Best-First Search will expand nodes that are closest to the goal first, even if it has a high path cost. A simple example is a straight path and a path with lots of twists, with the straight path starting a few nodes further away from the goal. Best-First Search will proceed on the path with twists first, till it reaches the goal. The result of this Best-First Search isn't optimal, since the straight path is shorter. Both A* and UCS will get the shorter path (there are conditions though, UCS needs strictly positive path weights, and the distance heuristic must be an underestimate).
- _delirium 15y agoChebyshev distance is the right metric to use if you can move on a grid horizontally/vertically/diagonally, which is the case here. Manhattan distance corresponds to h/v but no diagonal movement, and Euclidian distance corresponds to arbitrary non-gridded movement. (That said, which one functions best as a heuristic can vary problem to problem.)