2

While watching MIT's lectures about search, 4. Search: Depth-First, Hill Climbing, Beam, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around the 35 mins mark, the professor enqueues the paths in a way similar to greedy best-first search in which they are sorted, and the closer nodes expanded first.

However, I have read elsewhere that hill climbing is different from the best first search. What's the difference between the two then?

nbro
  • 39,006
  • 12
  • 98
  • 176
calveeen
  • 1,251
  • 7
  • 17

1 Answers1

3

Let's see their definition first:

  1. Best First Search (BFS): ‌

    Best-first search is a search algorithm that explores a graph by expanding the most promising node chosen according to a specified rule.

    estimating the promise of node n by a "heuristic evaluation function ${\displaystyle f(n)}$ which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most importantly, on any extra knowledge about the problem domain."

  2. Hill Climbing (HC):

    In numerical analysis, hill climbing is a mathematical optimization technique that belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

Base on the definition, we can find the following differences:

  • The aim of BFS is reaching to a specified goal by using a heuristic function (it might be greedy) vs. HC is a local search algorithm
  • BFS is mostly used in the graph search (in a wide state space) to find a path. vs. HC is using for the optimization task.
OmG
  • 1,731
  • 10
  • 19
  • 1
    It's not true that BFS algorithms don't look at history. A* is a BFS algorithm and it looks at the history (in fact, its evaluation function is $f(n) = g(n) + h(n)$, where $h$ is an admissible heuristic and $g$ is the history (i.e. cost of the path from the start node to $n$), but it also looks at the estimates to the goal. That's the idea. – nbro Apr 25 '20 at 00:04
  • 1
    @nbro Many thanks for the comment. You're right. I wanted to explain about the locality of HC as I've explained in the first difference! So, I've removed that statement. Do you suggest any more differences? – OmG Apr 25 '20 at 00:09
  • 2
    Yes, actually, I think you should explain how BFS algorithms (e.g. A*) choose to "move" (i.e. just explain a little bit about the evaluation function I talked about in my comment above) and how HC also "moves" in order to solve the optimization problem. – nbro Apr 25 '20 at 00:10
  • 1
    Also, note that the OP was specifically asking about "greedy" BFS. I think it's important to distinguish a greedy from a non-greedy BFS. A* is non-greedy. (At least, in the title). But I guess he was also confused ;) – nbro Apr 25 '20 at 00:12