# Tag Info

7

Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that can use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and a heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$ in the search space (often represented as a graph). ...

7

A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in ...

7

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A consistent ...

5

Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.

5

Yes, UCS is a special case of A*. UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...

3

The evaluation function in A* is $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the starting node to $n$ and $h(n)$ is an estimate of the distance from $n$ to the goal node. To compute $g(n)$, you simply do $g(n) = g(p) + c(p, n)$, where $p$ is the parent node, and $c(p, n)$ is the $c$ost of the edge between $p$ and $n$. So, yes, to compute $... 2 According to the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart Russel and Peter Norvig, specifically, section 3.5.1 Greedy best-first search (p. 92) Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using ... 2 The key phrase here is because heuristics are admissible In other words, the heuristics never overestimate the path length: $$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$ And since the frontier is ordered by$\textbf{cost + heuristic}$, when a completed path$p$is dequeued from the frontier, we know that it must necessarily be$\...

2

Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go from $A \rightarrow B$, plus our guess of the time to go from $B \rightarrow C$. Supposing we remove a given edge $c(n,m)$ from our graph, but that our ...

2

You forgot to calculate and take into account the costs of the actual paths. You forgot to accumulate the cost of the edges for going forward and backward multiple times! The evaluation function of uniform-cost search (UCS) is $f(n) = g(n)$, where $g(n)$ represents the cost of the path from the start node to $n$. The evaluation function of A* is $f(n) = g(n)... 1 In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as $$f(n)=g(n)+h(n)$$ where$g(n)$is the length (or cost) of the cheapest path from the start node to the current node$n$and$h(n)$is the heuristic function that estimates the cost of the ... 1 Check below reference url for A* algorithms ... https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/ https://en.wikipedia.org/wiki/Heap_%28data_structure%29 1 The first step of optimisation is to measure where inside the implementation most time is spent -- you don't actually optimise the algorithm itself, but a specific implementation of it. This step should give you an overview of where you can make improvements. Speculative changes usually don't do much. There are several aspects of A* which would be ... 1 I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a$3 \times 3\$ board of (numbered) squares as follows. +---+---+---+ | 0 | 1 | 2 | +---+---+---+ | 7 | 8 | 3 | +---+---+---+ | 6 | 5 | 4 | +---+---+---+ The numbers in these squares are just used to refer to the ...

1

A* is an informed search algorithm. A* informed because it is based on the use of a heuristic function, which estimates the distance of each node to the goal, that is, the heuristic function provides information about the distance from any node to the goal node. The heuristic function can e.g. be the Euclidean distance (in the case this can be defined). ...

1

What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching the goal. In that case, the A* algorithm is way better than the greedy search algorithm.

1

Question 1: First of all, you state that that the goal G2 will be found first by relying on the expansion order R, B, D, G2. This is wrong. It is extremely easy to see that this is wrong, because A* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never ...

Only top voted, non community-wiki answers of a minimum length are eligible