2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – nbro
    Apr 25, 2020 at 0:04
  • 1
    $\begingroup$ @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? $\endgroup$
    – OmG
    Apr 25, 2020 at 0:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – nbro
    Apr 25, 2020 at 0:10
  • 1
    $\begingroup$ 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 ;) $\endgroup$
    – nbro
    Apr 25, 2020 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .