1
$\begingroup$

With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a problem? For instance, in the 8-queens problem, it is said that it hits a local minima 86% of the time. Can someone please elaborate more on how and what denotes maximas and minimas and given this, how the algorithm can get stuck at a plateau.

What I know so far is the following:

  1. Expand the current state, find the best neighbor, and that becomes the new current state.
  2. No looking beyond one step from where you are, no memory
$\endgroup$
  • 1
    $\begingroup$ What have you read about this topic? In my estimation, any serious source will contain these details. $\endgroup$ – Raphael Apr 18 '16 at 7:01
1
$\begingroup$

Consider the general problem of maximizing such function $f$ on a domain $V$. Now suppose there is a graph $G=(V,E)$ on $G$. A local maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all neighbors $u$ of $v$. A global maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all $u \in V$. Hill climbing can get stuck at a local maximum which isn't a global maximum. Perhaps you can construct such an example yourself.

In the 8-queens problem, the domain $V$ is the set of chess boards with k non-conflicting queens on them for $k=0$ to $k=8$. There is an edge between two such boards if you can reach one from the other by placing one queen. The fitness function is simply the number of queens on the board. Simple hill climbing gets stuck if it ends up in a board with fewer than eight queens where no more queens can be placed, because there is no edge that goes to a board with more queens on it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.