Go backward to Solution to part (c)
Go up to 7 Solving a CSP via backtracking, arc consistency, hillclimbing
Solution to part (c)
Show how hill climbing can be used for the problem. Suppose a
neighbor is obtained by increasing or decreasing the value of one of
the variables by 1, the heuristic function to be maximized is the
number of satisfied constraints, and you always choose a neighbor
with the maximal heuristic value.
- There are many variants. Here is one:
|
A | B | C | D | E | h |
|
1 | 1 | 1 | 1 | 1 | 1 |
|
1 | 1 | 2 | 1 | 1 | 4 |
|
1 | 2 | 2 | 1 | 1 | 5 |
|
1 | 3 | 2 | 1 | 1 | 6 |
|
1 | 3 | 2 | 2 | 1 | 6 |
|
1 | 3 | 2 | 3 | 1 | 6 |
|
1 | 4 | 2 | 3 | 1 | 7
|
Here is another:
|
A | B | C | D | E | h |
|
1 | 1 | 1 | 1 | 1 | 1 |
|
1 | 1 | 2 | 1 | 1 | 4 |
|
1 | 2 | 2 | 1 | 1 | 5 |
|
1 | 2 | 3 | 1 | 1 | 5 |
|
1 | 3 | 3 | 1 | 1 | 5 |
|
1 | 3 | 3 | 2 | 1 | 6 |
|
1 | 4 | 3 | 2 | 1 | 7
|
- Again there are many variants:
|
A | B | C | D | E | h |
|
3 | 3 | 2 | 1 | 4 | 4 |
|
4 | 3 | 2 | 1 | 4 | 5 |
|
4 | 4 | 2 | 1 | 4 | 5 |
|
4 | 3 | 2 | 1 | 4 | 5
|
This can meander for a long time, but it never gets out of the local
minima.
Here is another run:
|
A | B | C | D | E | h |
|
3 | 3 | 2 | 1 | 4 | 4 |
|
3 | 3 | 2 | 1 | 3 | 5 |
|
3 | 4 | 2 | 1 | 3 | 5
|
Again we can't go anywhere except alternate between the last two
assignments.
This is a small plateau.
-
A better heuristic would be to notice that if we have a constraint
X>Y that increasing X, even if it doesn't make it greater than Y
is a useful move. Hence one heuristic is to count a the achievement of
X>Y by 1, but a violation of X>Y by the value X-Y (which could
be negative). This would allow us to avoid the second local minima we
found.
Another may be to count the inequality and the even/odd constraints as
less important on the grounds that they it is often useful to violate
them temporarily, and they are easy to achieve (by moving a value by
one).
Computational
Intelligence online
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999