1
$\begingroup$

Greedy best first search Algorithm take the history and then check value ans then reach to goal.

In A* search Algorithm take history and also cost then calculate value then reach to goal.

When we use greedy best first search Algorithm then start from initial then check value that taken by history then go to next node and so on. When using A* search Algorithm then start from initial then calculate value by adding cost and history value then check value and no next. In this we go back also if we see that in first level there is a small value then all node in first level or sec or so on.

MY QUESTION: Am confuse that we call A* search is best then greedy best first search when we use A* search then if we go back then we stuck in loop so how we say its best then greedy

$\endgroup$
  • $\begingroup$ Please, have a look at my answer here: ai.stackexchange.com/a/8907/2444, which should clarify all your doubts. If not, please, tell me then what you're asking. $\endgroup$ – nbro Nov 11 '18 at 10:40
  • 2
    $\begingroup$ Possible duplicate of How A* search algorithm is better then greedy best search? $\endgroup$ – nbro Nov 11 '18 at 10:41
  • $\begingroup$ Can you clarify the question? (Right now the question is convoluted and hard to understand. Am I correct that you are asking about terminology "best" and "greedy" in relation to the conceptual framework of the two approaches? Feel free to re-edit and submit for re-opening.) $\endgroup$ – DukeZhou Nov 13 '18 at 22:38
  • 1
    $\begingroup$ @DukeZhou you are right am asking about the terminology of best and greedy in conceptual framework $\endgroup$ – Iram Shah Nov 14 '18 at 12:21
0
$\begingroup$

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). We use the Straight Line Distance heuristic, which we will call hSLD. Notice that the values of hSLD cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that hSLD is correlated with actual distance between nodes and is, therefore, a useful heuristic.Greedy best-first tree search is also incomplete and not optimal.
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) . Where 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.

$\endgroup$
  • $\begingroup$ dear you post answer you tell its best i know Asearch is best then greedy but why its best if A is stuck in loop then its take too much time to reaching to goal. If you know about this then tell me THANK YOU $\endgroup$ – Iram Shah Oct 31 '18 at 9:26
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 overestimate the cost of reaching the goal , in this 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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