4
  • Best-first search - a search that has an evaluation function f(n) that determines the cost of expanding node n and chooses the lowest cost available node
  • Uninformed search - has no knowledge of h(n)
  • Informed search - has knowledge of h(n)
  • Greedy search - is best-first, can be informed or uninformed, f(n) does not contain g(n)
  • Uniform cost search - is best-first, is not greedy, is uninformed, f(n) = g(n)
  • A* search - is best-first, is not greedy, is informed, f(n) = g(n) + h(n)
  • Greedy best-first search - is best-first, is greedy, is informed, f(n) = h(n)

Is this correct? Can someone give concrete and all-encompassing definitions for these terms? It seems that "greedy" and "best-first" are often used interchangeably.

Even Wikipedia has conflicting definitions...

Greedy algorithm - Wikipedia:

Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms

Best-first search - Wikipedia:

The A* search algorithm is an example of a best-first search algorithm, as is B*. Best-first algorithms are often used for path finding in combinatorial search. Neither A* nor B* is a greedy best-first search, as they incorporate the distance from the start in addition to estimated distances to the goal.

Is it that A* is greedy, A* is best-first, but A* is not greedy best-first?

Someone please sort all these terms out...

user10939349
  • 41
  • 1
  • 3
  • 1
    I thought A* was best-first plus the heuristic 'h' . You can turn A* greedy by turning down the H weight. https://stackoverflow.com/questions/8374308/is-the-greedy-best-first-search-algorithm-different-from-the-best-first-search-a for more.. – Matthew Page Jan 26 '19 at 12:39

0 Answers0