Quote:Original post by irreversible
Define "improved upon". If you can improve A* you'll probably become famous and get lots of women. A* can be tweaked and refined or combined with derivatives of itself to improve efficiency, but "improving upon it" seems a bit audacious.
You can "improve upon" A* in many ways. In this particular case I refer to gaining a speedup without trading away completeness or optimality. For example, A* improves upon Dijkstra's Algorithm (although by your definition above, A* is nothing but a "tweak" of that algorithm).
Anyway, I dislike the incredulous attitude and sarcastic tone of your post (and the other poster). I'm not claiming anything very shocking: there are many examples where people have improved on the performance of A* without trading away optimality or using extra memory. Fringe Search for example (Bjornsson 2005) is an iterative deepening technique which is shown to be faster than A* on general graphs. On grid maps other approaches like the dead-end heuristic (Bjornsson06) speed up A* by identifying and pruning areas that A* would necessarily explore but which cannot lead to the goal. A more recent result along these lines (Pochter09) does even better.
My approach is similar to these. It's implemented, tested and I have a draft paper on my desk.
Sheesh.