Information Technology Reference
In-Depth Information
In this case, candidate pairs of values are considered. The first pair generated is Z=john
and X=sue . But the test male(sue) fails, and so the program backtracks and generates
the next pair of values, which is Z=john and X=sam , and which passes the test.
Now consider the following query:
?- male(X), child(Z,X), child(jane,Z).
Tracing the back-chaining, one can see that generate-and-test is used repeatedly:
1.
Using male(X) , generate a first value for X , and get X=john .
a.
Generate a Z for this X using child(Z,X) , which fails.
2.
Backtrack and generate a second value for X , which is X=sam .
a.
Generate a Z for this X using child(Z,X) , and get Z=john .
This fails the test child(jane,Z) .
b.
Backtrack and generate the next Z , which is Z=jane .
This fails the test child(jane,Z) .
c.
Backtrack for yet another Z . However, there are no other values for Z , and so
the program is unable to generate a Z for this X .
3.
Backtrack and generate a third value for X using male(X) , which is X=george .
a. Generate a Z for this X using child(Z,X) , and get Z=sue .
This passes the test child(jane,Z) , and so the program is done.
This generate-and-test process, which back-chaining does automatically, is at the root
of how constraint satisfaction problems can be solved.
A simple example: Map coloring
Look at the map-coloring problem in figure 5.1. We seek a Prolog program that solves
this problem and finds colors for the five countries. A program that does so appears
in figure 5.2. This program can be understood by reading the clause for the solution
predicate in English:
If a , b , c , d , and e are colors, and if
a
e ,
then these colors are a solution to the given map-coloring problem.
=
b , a
=
c , a
=
d , a
=
e , b
=
c , c
=
d ,
and d
=
Since the only colors are the three given ones, red, white, and blue, the solution
predicate produces correct answers:
 
Search WWH ::




Custom Search