# Questions tagged [a-star]

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

24 questions
Filter by
Sorted by
Tagged with
25 views

### Why do we use the tree-search version of breadth-first search or A*?

In Artiﬁcial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
1k views

### What are the differences between Q-Learning and A*?

Q-learning seems to be related to A*. I am wondering if there are (and what are) the differences between them.
103 views

### Is A* with an admissible but inconsistent heuristic optimal?

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows: Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
71 views

### Which heuristics guarantee the optimality of A*?

The following is a statement and I am trying to figure out if it's true or false and why. Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
37 views

### Doesn't the number of explored nodes with IDA* increase linearly?

I think I'm misunderstanding the description of IDA* and want to clarify. IDA* works as follows (quoting from Wiki): At each iteration, perform a depth-first search, cutting off a branch when its ...
34 views

### How does heuristic work with multiple agents?

I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
81 views

132 views

### A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge),...
91 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.
371 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 whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
76 views

### What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
4k views

### How do I show that uniform-cost search is a special case of A*?

How do I show that uniform-cost search is a special case of A*? How do I prove this?
71 views

### How is the cost of the path to each node computed in A*?

How is the cost of the path to each node $n$ computed in the A* algorithm? Do we need to add the cost of the path to the parent node $p$ to the cost of the path of the child node $n$?
20k 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?
5k 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 ...
3k views

### What heuristic to use when doing A* search with multiple targets? [closed]

Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which ...
3k views

### How do you calculate the heuristic value in this specific case?

The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where $g(n)$ = cost of the path from the start node to node $n$ $h(n)$ = estimated cost of the cheapest path from $n$ to the ...
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 ...