This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Although this part of the course is going to look at "modern" search techniques the same problems with the size of the search space still exist. If it were not for the fact that search spaces are so large (and grow so quickly) then we could simply carry out an exhaustive search and be done with it.
But, as well as the problem of large search spaces there are also some other problems which we will consider now before we look at some search methods that try to address these issues.
To demonstrate the problem we will look at implementing a simple (but sometimes effective) search method.
In these discussions we will assume we are trying to maximize a function. That
is, we are trying to find a point in the search space that is better than all
the others. And by "better" we mean that the evaluation is higher.
We might also say that the solution is of better quality than all the others.
There is no reason why we should not be trying to minimise a function but it makes for easier reading if we assume we are always trying to maximise the function rather than keeping having to remind ourselves than we could be minimising or maximising.
The idea behind hill climbing is as follows.
1. Pick a random point in the search space.
2. Consider all the neighbours of the current state.
3. Choose the neighbour with the best quality and move to that state.
4. Repeat 2 thru 4 until all the neighbouring states are of lower quality.
5. Return the current state as the solution state.
We can also present this algorithm as follows (it is taken from the AIMA book
(Russell, 1995) and follows the conventions we have been using on this course
when looking at blind and heuristic searches).
Function HILL-CLIMBING(Problem) returns a solution state
Inputs: Problem, problem
Local variables: Current, a node
Next, a node
Current = MAKE-NODE(INITIAL-STATE[Problem])
Loop do
Next = a highest-valued successor of Current
If VALUE[Next] < VALUE[Current] then return Current
Current = Next
End
You should note that this algorithm does not maintain a search tree. It only
returns a final solution.
Also, if two neighbours have the same evaluation and they are both the best quality, then the algorithm will choose between them at random.
| Previous Page | Index Page | Next Page |
Last Updated : 26/01/2002