The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [a-star]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
31 views

Graph Search Version of A*

I am going through Russel and Norvig's AI A Modern Approach 3rd Edition. I was reading the A* algorithm and it reads A* Graph Search Version is optimal when heuristic is consistent and Tree Search ...
4
votes
1answer
63 views

How do we determine whether a heuristic is better than another?

I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics. Currently, I explored the Manhattan and Euclidean distances. ...
2
votes
1answer
63 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
57 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
132 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
45 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
6k views

What are the 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?
4
votes
1answer
2k 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 ...
2
votes
2answers
6k views

What are the differences between greedy best-first and the A* search algorithms? [duplicate]

What are the differences between greedy best-first and the A* search algorithms? How is A* better than the greedy best-first search algorithm?
7
votes
1answer
5k views

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...