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?
Let's see their definition first:
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."
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:
