# Questions tagged [a-star]

For questions related to the A* (or A) search algorithm, which is a very famous state-space search algorithm and widely taught in Computer Science and Artificial Intelligence. A* is a best-first search algorithm that is guaranteed to find the optimal solution given an admissible heuristic function, so A* is also an informed search algorithm, as opposed to e.g. depth-first search, which is an uninformed search algorithm.

33 questions
Filter by
Sorted by
Tagged with
50 views

### Where can I find Norvig's version of the pseudocode for the A* search algorithm?

Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing. It's the version that uses the Unexplored/Frontier/Explored data ...
55 views

### Is possible to perform an early goal test with A* using a consistent heuristic?

I have a doubt about A* goal test. As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
91 views

### Is there an error in A* optimality proof Russel-Norvig 4th edition?

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
• 71
112 views

• 1,201
604 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 ...
• 165
115 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 ...
246 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 ...
• 179
1k views

### How do we determine whether a heuristic function 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 heuristic functions. Currently, I explored the Manhattan and Euclidean ...
• 303