Weighted A* on wikipedia

Question

I guess I find a problem on this wiki page:

I think the `

have a cost of at most ε times

in the Weighted A* algorithm part should be

have a cost less than ε times

instead.

Because here it assumes ε > 1. But I am not sure about it, just want to listen anybody's opinion on this..

Thank you for your help in advance :)

Answer 1

I believe the paragraph starting "Weighted A*. If ha(n) is" is correct, and a guarantee that the cost of the path found is at most eta times the cost of the best path is the sort of guarantee you want - since you are looking for the least cost path and trying to reduce cpu time you are settling for a sub-optimal (higher cost) solution but obtaining a guarantee that the cost is not too bad - at most eta times the cost of the best path.

I do think that there is an inconsistency between the use of eta in this paragraph and that in the paragraph above - I don't know whether that is a mistake or whether it derives from an unfortunate difference of conventions between weighted A* and a more general definition of approximate solutions.

The paragraph is consistent with the notes at http://inst.eecs.berkeley.edu/~cs188/sp11/slides/SP11%20cs188%20lecture%204%20--%20CSPs%206PP.pdf - bottom of page 5 on the pdf and with a rough proof. When weighted A* thinks it has a solution with cost g(x) all nodes still in play must have a predicted cost g(y) + eh(y) at least this. To get the largest possible error assume that g(y) is zero and that eh(y) = g(x) for correct solution y and we see that the solution A* thinks it has found is e times as expensive as y - since we presume that the original h() is admissable and therefore an upper bound on cost.