Hacker News Reader

Comment by psycovic23 | Hacker News Reader

This isn't true. An admissible heuristic guarantees the optimal solution. With an inconsistent heuristic, A* can re-expand states multiple times, but will still end with an optimal path.

In other words, if the heuristic is consistent, then it implies that A* will expand the optimal number of states.

View on HN

If we operate under the assumption that each intermediate path found is shortest for its respective endpoint (which is the fundamental insight for Dijkstra's), we could potentially throw away the solution because it travels through the "visited set."

Edit: The paper you cited uses a traversal slightly different from traditional A*.

If you use an inconsistent heuristic, it may be possible to revisit a node a second time via a cheaper path. And thus, as you say, if you generate a node a second time but with a cheaper path, you may not find the optimal solution if you discard the regenerated node.

So if you do A* with an inconsistent heuristic, you need to revisit nodes if you explore them a second time with a cheaper cost (i.e., you can re-expand nodes in your closed list). If you do this, you will find optimal solutions even with an inconsistent heuristic.

The only requirement on your heuristic if you A* to find optimal solutions is that it be admissible.

I am talking about frontier A* where you discard all nodes that have already been visited. This requires the heuristic to be consistent. As opposed to the breadth-first heuristic search which revisits nodes.

Ah. Yes, in frontier A* you definitely need a consistent heuristic, although I'd be surprised if frontier A* is the most popular form of the algorithm used, particularly for grid search. You really only want it in a very large implicit domain where the closed list would be too large to fit in memory. If the problem space is small enough then the traditional form of A* with an explicit closed list is much easier to think about.

A nitpick: "breadth-first heuristic search" is an algorithm developed by Zhou and Hansen and, while it's related to A* (in that it uses an admissible heuristic to prune the search space), it's not actually a variant of A*. (It's not a best-first search algorithm, since it doesn't expand nodes in increasing order of f cost.)

Reply on news.ycombinator.com