Suppose you have a set of parent child relationships stored in a database (see TEACH * DATABASE).
For example you could set up a database like this:
define start_family_tree();
[
[father [tom jones] [dick jones]]
[father [tom jones] [sue smith]]
[mother [ginny jones] [dick jones]]
[mother [ginny jones] [sue smith]]
[father [dick jones] [mary jones]]
[mother [sue smith] [joe smith]]
[mother [sue smith] [fred smith]]
[father [jack smith] [joe smith]]
[father [jack smith] [fred smith]]
[father [fred smith] [angela green]]
[mother [angela green] [willy green]]
] -> database;
enddefine;
Then the following command will set up the initial database:
start_family_tree();
;;; print out database to check
database ==>
Now suppose you had to find out whether someone A is an ancestor of
someone else B.
One way you could do that is set up a search space consisting of a start node A, and all paths from A to descendents of A. Then the solve_problem procedure could be given the task of searching for a path through the family tree starting from A and ending with B. If such a path is found, it would answer the question positively: A is an ancestor of B.
You could represent a state in the search space as consisting of a list of names representing a path found so far through the family tree. For example if we wanted to find out whether [ginny jones] is an ancestor of [angela green] we would have a succession of states showing routes up the tree to ginny jones thus
[[ginny jones]] ;;; initial state
[[dick jones] [ginny jones]] ;;; a successor state
[[sue smith] [ginny jones]] ;;; another successor state
If we use this representation, then it is easy to tell whether the
problem has been solved: check whether the target person B is the first
item of the list.
Thus we can define the following procedures to use with solve_problem
define is_ancestor_goal(state, target) -> boole;
;;; The state is a list of names defining a route up the family tree
;;; Does it start with target?
lvars state, target, boole;
state matches [^target == ] -> boole
enddefine;
However, we also have to create a procedure for generating new states
from a given state. Remember that a state is a list of names of people
[personN ... person3 person2 person1]where person1 represents a parent of person2, person2 a parent of person3, and so on. Person1 is the one given as the original alleged ancestor, and personN is the latest person found in searching down the tree from person1.
Then in order to find successors to this state we need to find individuals who are immediate descendants of personN, and form a set of new routes up the tree from each of them. First we need a procedure to find the immediate descendants. We can use the database searching procedure foreach (described in TEACH FOREACH)
define immediate_descendants(person) -> list;
lvars person, list;
vars next; ;;; a pattern variable used with foreach below
;;; start making a list
[%
;;; first collect all those to whom person is father
foreach [father ^person ?next] do
next; ;;; just leave the next person on the stack
endforeach;
;;; now collect all those to whom person is mother
foreach [mother ^person ?next] do
next; ;;; just leave the next person on the stack
endforeach;
%] -> list
enddefine;
You can test this as follows
immediate_descendants([ginny jones]) =>
** [[dick jones] [sue smith]]
immediate_descendants([sue_smith]) =>
** []
Using the procedure immediate_descendants we can define a procedure to
create extensions to a state represented as a route up the tree
define family_next_states(state) -> newstates;
lvars state, states;
;;; make a list of new states that start with one descendant
;;; and the rest of state
lvars nextpeople, person;
immediate_descendants(hd(state)) -> nextpeople;
;;; Now make a list of the new states
[%
for person in nextpeople do
;;; make a new state and leave it on the stack, to go into
;;; the list being created by [% ... %]
[^person ^^state]
endfor
%] -> newstates
enddefine;
Now test it
family_next_states([[ginny jones]]) ==>
** [[[dick jones] [ginny jones]] [[sue smith] [ginny jones]]]
Note that the output was a list of TWO lists.
[[dick jones] [ginny jones]]and
[[sue smith] [ginny jones]]Try extending the first list:
family_next_states([[dick jones] [ginny jones]] ) ==>
** [[[mary jones] [dick jones] [ginny jones]]]
This time there is only one extension, containing three names. You may
of course get a different answer with your database of names.
We now need a test for whether a state is the same as one we have tried before and for this problem it is easy - just see if the two states are the same. (It is not always that easy.)
define family_same_state(state1, state2) -> boole;
state1 = state2 -> boole
enddefine;
And finally we define the simplest possible state insertion procedure
for combing a new state with a list of states: just put it at the front,
so that it will be examined next. (This defines a depth first search
strategy).
define family_insert(state, states) -> newstates;
[^state ^^states] -> newstates
enddefine;
You should now be able to use the solve_problem procedure to see whether
one person is a descendant of another. We can define a new procedure
called check_ancestor which does the work, as follows:
define check_ancestor(person1, person2) -> result;
;;; use solve_problem to do the work
solve_problem
([^person1], ;;; start state (must be a list with a name)
person2, ;;; goal state information
is_ancestor_goal, ;;; goal state recogniser
family_next_states, ;;; generator for next states
family_same_state, ;;; circle detector procedure
family_insert ;;; insertion procedure
) -> result
enddefine;
;;; Now test it
check_ancestor([ginny jones], [mary jones]) ==>
** [[mary jones] [dick jones] [ginny jones]]
;;; Compare this case, with a different target descendant
check_ancestor([ginny jones], [tom jones]) ==>
** <false>
Try some other tests using an extended version of the database.