It’s funny how two of the most studied algorithms of a discipline, that are considered polynomially optimal for decades under a set of well-accepted assumptions, turn out not to be so great. That’s the case of the famous A* and IDA* algorithms, cornerstones in AI and currently implemented in thousands of computer games because there were thought to be polynomial in the search space since 1968 under a set of broadly defined heuristics, even though nobody has found practical instances of them after hundreds of proposal and attempts. Their optimality is finally debunked in “How Good is Almost Perfect”: general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the most optimistic assumption of estimators with heuristic error bounded by a small additive constant. What is worse, other similar search techniques cannot perform better than A*.

These are the kind of results that reminds you to always revisit assumptions, to search more closely where others may have obviated, no matter how well-accepted and reputed are the sources, in particular with folklore wisdom, beliefs and other uncanny heuristics.