If you want to make money online : Register now

[Answers] Hill Climbing Search

, , No Comments
Problem Detail: 

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
Asked By : Christian

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56100

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback