-1

Is there a difference at all? I've been told the greedy selects the child with the highest value of the heuristic function i.e. the locally best successor. My confusion is what happens in an greedy best first algorithm which do not track it's visited nodes, meets the same node in a different path? I'll draw the problem out to depict it clearly ;enter image description here

What node C will the greedy best-first algorithm expand when it reaches C through B, C(x) or C(y), and what would the output path be? ABCG or ACG?

Note this tree is a graphical representation of a shortest path evaluation of a grid, the child nodes are the valid neighboring nodes of the parent node in the grid.

Ashen Jayawardena
  • 177
  • 2
  • 15
  • Is this a tree or a graph you're searching? You show a tree structure, but claim that the `C` nodes are the same. I'm not clear on the problem you're trying to solve; is it to find a path to C in a non-tree graph? – Prune Feb 07 '20 at 18:23
  • I'm sorry for not giving a better context, pls have a look at the note I edited now – Ashen Jayawardena Feb 07 '20 at 18:37
  • Does this answer your question? [Is the greedy best-first search algorithm different from the best-first search algorithm?](https://stackoverflow.com/questions/8374308/is-the-greedy-best-first-search-algorithm-different-from-the-best-first-search-a) – Prune Feb 07 '20 at 18:48
  • It sort of does with a doubt, the answer is edited in by the author of the question itself and that too with not much confidence. By that way does that mean A-B-C-G is the path greedy best first delivers? Since it will consider only the children of node B for the next selection? – Ashen Jayawardena Feb 07 '20 at 19:22

2 Answers2

1

By that way does that mean A-B-C-G is the path greedy best first delivers? Since it will consider only the children of node B for the next selection?

Yes: a strict "greedy" algorithm considers only the best short-term choice at each juncture. At the first step, B is cheaper than C, so it starts down that path. From here, it treats B as the start node. The cheapest move from there is to C, then to G.

In contrast, a "best-first" algorithm such as A* or Dijkstra's will make some notice of the cheapest total path. It starts with the state (A, 0) -- it cost nothing to get to A. Then it generates moves (AB, 2), (AC, 3), and (AD, lots); it takes the cheapest move, (AB, 2), but retains the others on the list. Now it generates moves from B with total cost: (ABE, 7) and (ABC, 5). At this point, it drops (ABC, 5) because there's a known cheaper path to C.

Now the cheapest path on the list is (AC, 3), and the algorithm will generate moves from there: (ACG, 3+unknown).

Does that clear up enough for you?

Prune
  • 76,765
  • 14
  • 60
  • 81
0

In general, an algorithm is called "greedy" if it just takes the locally best step and never reconsiders decisions. "Best first" would be some sort of exhaustive search, where you order the alternative steps by some heuristic ("sounds sensible, no guarantee") and try them in order. That only makes sense if you combine with some cutoff criterion, i.e., you have some way to weed out alternatives that you can prove won't give the desired result.

Check e.g. $A^*$ (A-star) search.

vonbrand
  • 11,412
  • 8
  • 32
  • 52