Questions tagged [a-star]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
59 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$ ...
0
votes
1answer
55 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 ...
1
vote
1answer
32 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 ...
2
votes
0answers
27 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 ...
1
vote
1answer
70 views

What does a consistent heuristic become if an edge is removed in A*?

For the A* algorithm, a consistent heuristic is defined as follows: if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$. Suppose the edge $c(...
3
votes
1answer
122 views

A* and uniform-cost search are apparently incomplete

Consider the following diagram of a graph representing a search space. If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm ...
2
votes
0answers
112 views

How can I assign agents to tasks based on time and affinity?

I am working on an assignment problem. Consider $K$ agents $A_1, \dots A_K$ and $N$ tasks $T_1, \dots T_N$. Each task has a certain time $t(T_i)$ to be completed and each agent has a matching (or ...
2
votes
1answer
67 views

In the graph search version of A*, can I stop the search the first time I encounter the goal node?

I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm A* graph search version is optimal when heuristic ...
5
votes
1answer
144 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
114 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 $...
5
votes
1answer
99 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) ≤ d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), ...
0
votes
2answers
66 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
293 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.
2
votes
1answer
63 views

What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
4
votes
1answer
3k 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?
2
votes
1answer
69 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$?
7
votes
3answers
15k 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?
5
votes
1answer
4k 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 ...
8
votes
1answer
8k 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 ...
5
votes
2answers
281 views

How does A* search work given there are multiple goal states?

When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture. These are the heuristic estimates: ...