Questions tagged [a-star]

For questions related to the A* (or A) search algorithm.

Filter by
Sorted by
Tagged with
2
votes
1answer
55 views

Understanding the proof that A* search is optimal

I don't understand the proof that $A^*$ is optimal. The proof is by contradiction: Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
0
votes
2answers
52 views

How can the A* algorithm be optimized?

How can the A* algorithm be optimized? Any references that shows the optimization of A* algorithm are also appreciated.
2
votes
1answer
93 views

Why Nilsson's Sequence Score isn't an admissible heuristic?

I understand what an admissible heuristic is, I just don't know how to tell if one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
1
vote
1answer
43 views

What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
0
votes
1answer
56 views

Is the parent cost in A* added in every extended child?

How do we determine the cost of the parent path to its child in A* ("A star") search?
3
votes
1answer
4k views

What are the practical differences between A* and greedy best-first search?

What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
3
votes
1answer
1k views

How is iterative deepening A* better than A*?

The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals. The A* algorithm evaluates nodes by combining the ...