Disregarding the cost/length calculation, a brute force search algorithm would look something like this:
Code: Select all
predicates
findPath : (string Start, string End) -> string* Path determ.
clauses
findPath(Start, End) = list::reverse(findPath2(Start, End, [Start])).
predicates
findPath2 : (string Start, string End, string* PathSoFar) -> string Path determ.
clauses
findPath2(C, C, PathSoFar) = [C|PathSoFar] :-
!.
findPath2(A, C, PathSoFar) = Path :-
edge(A, B),
not(list::isMember(B, PathSoFar)),
Path = findPath2(A, B, [B|PathSoFar]),
!.
I assume that "edge" is a non-deterministic predicate (or fact database) that given
A returns all
Bs that have a direct edge from
A.
The important things (with respect to your questions) is having access to already visited nodes (and since we want to find a path we may use the
PathSoFar for both purposes). The other important thing is to disregard those
B's which are already on the
PathSoFar.
When collecting the result on the way in rather than the way out you end up with a reverse solution, hence the call to reverse:
PathSoFar is actually a
PathBackSoFar.
One more thing is ! (cut). It is seldom correct to place a cut last in a long clause, but here it is correct. Choosing
B is nondeterministic, when we have found a
B, which will bring us to the end we don't want to try other
B's. So the correct place to cut the
B-nondeterminism is after having found a path.