2
$\begingroup$

This question already has an answer here:

What are the differences between greedy best-first and the A* search algorithms? How is A* better than the greedy best-first search algorithm?

$\endgroup$

marked as duplicate by DukeZhou Sep 9 at 20:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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 just the heuristic function; that is, $f(n) = h(n)$.

In this same section, the authors give an example that shows that greedy best-first search is neither optimal nor complete.

In section 3.5.2 A* search: Minimizing the total estimated solution cost of the same book (p. 93), it states

A* search evaluates nodes by combining $g(n)$, the cost to reach the node, and $h(n)$, the cost to get from the node to the goal $$f(n) = g(n) + h(n).$$

Since $g(n)$ gives the path cost from the start node to node $n$, and $h(n)$ is the estimated cost of the cheapest path from $n$ to the goal, we have $f(n)$ = estimated cost of the cheapest solution through $n$.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of $g(n) + h(n)$. It turns out that this strategy is more than just reasonable: provided that the heuristic function $h(n)$ satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to uniform-cost search except that A* uses $g + h$ instead of $g$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ dear can you elaborate your answer. sorry to say but i did not get your point. $\endgroup$ – Iram Shah Oct 31 '18 at 9:22
  • $\begingroup$ @IramShah - TemmanRafk is talking about the proof that A* is both optimal and complete. To do so it is shown due to the triangle inequality that the heuristic that estimates the distance remaining to the goal is not an overestimate. To see a fuller explanation see en.wikipedia.org/wiki/Admissible_heuristic $\endgroup$ – Simon May 18 at 20:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.