A* is faster in practice if the heuristics used by the specific implementation are accurate and if the graph is "general" for the problem space. I'm being very

A* is faster in practice if the heuristics used by the specific implementation are accurate and if the graph is "general" for the problem space. I'm being very loose with the word "general" but essentially it should have typical structure for the problem space it represents. There's almost certainly a paper somewhere proving that A* with a given heuristic can always be made O(large) by choosing the right adversarial inputs.