better heuristic then A*

Question

I am enrolled in Stanford's ai-class.com and have just learned in my first week of lecture about a* algorithm and how it's better used then other search algo.

I also show one of my class mate implement it on 4x4 sliding block puzzle which he has published at: http://george.mitsuoka.org/StanfordAI/slidingBlocks/ While i very much appreciate and thank George to implement A* and publishing the result for our amusement.

I (and he also) were wondering if there is any way to make the process more optimized or if there is a better heuristic A*, like better heuristic function than the max of "number of blocks out of place" or "sum of distances to goals" that would speed things up? and Also if there is a better algo then A* for such problems, i would like to know about them as well.

Thanks for the help and in case of discrepancies, before down grading my profile please allow me a chance to upgrade my approach or even if req to delete the question, as am still learning the ways of stackoverflow.

Answer 1

It depends on your heuristic function. for example, if you have a perfect heuristic [h*], then a greedy algorithm(*), will yield better result then A*, and will still be optimal [since your heuristic is perfect!]. It will develop only the nodes needed for the solution. Unfortunately, it is seldom the case that you have a perfect heuristic.
(*)greedy algorithm: always develop the node with the lowest h value.

However, if your heuristic is very bad: h=0, then A* is actually a BFS! And A* in this case will develop O(B^d) nodes, where B is the branch factor and d is the number of steps required for solving.
In this case, since you have a single target function, a bi-directional search (*) will be more efficient, since it needs to develop only O(2*B^(d/2))=O(B^(d/2)) nodes, which is much less then what A* will develop.
bi directional search: (*)run BFS from the target and from the start nodes, each iteration is one step from each side, the algorithm ends when there is a common vertex in both fronts.

For the average case, if you have a heuristic which is not perfect, but not completely terrbile, A* will probably perform better then both solutions.

Possible optimization for average case: You also can run bi-directional search with A*: from the start side, you can run A* with your heuristic, and a regular BFS from the target side. Will it get a solution faster? no idea, you should probably benchmark the two possibilities and find which is better. However, the solution found with this algorithm will also be optimal, like BFS and A*.