On the optimality of A∗