% "BESTFAST" search program
%
% Copyright 1996, David Lee Winston Miller.
%
% All rights reserved. This software is not shareware or freeware. The
% software may be used only to evaluate the research presented and may not
% be used for any commercial purpose. The sofware may not be distributed to
% others. (The only distribution allowed is from my Web site.) The
% software may not be modified. There is no warranty implied or given with
% this software. Use it at your own risk. The author assumes no liability
% for any damages resulting from the use of this software. Portions of the
% software may be covered under other copyrights.
%
%
% The "BESTFAST" search program is a fast version of the best-first search
% algorithm. The search program in the text is limited to 64KB. However,
% the program presented here is limited to about 2GB. This is more than
% enough power to solve the eight-puzzle and many other problems.
% In addition, this program can do special searches such as breadth-first
% and, in some cases, A* searches even if the exiting heuristic algorithm is
% not h*. This is accomplished by making the Mh input parameter small enough
% so that (Mh * h) is h*. The use of the Mg and Mh input parameters (see
% below) make the search program very flexible.
%bestfast(Start,Solution,Mg,Mh): Solution is a path from Start node to a
% goal. Mg is a multiplication factor that determines how much accumulated
% costs are counted. Mh is a mult. factor that determines how much the
% heuristic is considered. If the costs are properly calulated and the
% heuristic is very accurate but always an underestimate, set Mg and Mh to
% 1. If the heuristic sometimes overestimates, you can compensate by setting
% Mh so that the resulting product will be an underestimate. In fact, if you
% set Mh to 0, the search will be a breadth-first search. However, if the
% memory overflows or the search is too slow, you may set Mg to 0 so that
% the program will always ignore the costs thus far and search the tree that
% seems to offer the quickest solution from the nodes thus far explored.
bestfast(Start, Solution, Mg, Mh) :-
abolish(type/2), %Abolish previous search info
asserta((type(Mg,Mh))), %type of search to be performed
abolish(t/3), %Abolish all old trees
removeallb(l), %Remove l btree.
defineb(l,17,false,+,0), %leaf btree, 17splitsize, etc...
abolish(root/0), %Abolish old root
asserta((root)), %root is beginning of search tree
key(root,RootKeyRef), %Find database ref # for root key
nref(RootKeyRef,RootRef), %Find database ref # for root. (1st in key.)
%OBS: asserta((t(RootRef,Start,))),
%l(Predecessor'sReferenceNumber,StartingNode
% starting node's predecessor is root
%OBS: key(l,LKeyRef), %Find database ref # for l (leaf)
%OBS: nref(LkeyRef,LRef), %Find database ref # for l(RootRef,Start).
P=2147483647, %Assume that start node is not very promising
C=0, %Cost of getting to start node is zero
%OBS: LR=LRef, %LeafRef#=LeafRef#
recordb(l,P,l(P,C,RootRef,Start)), %l(Promise,Costs,ParentRef#,LeafNode)
%Promise depends on the Mg & Mh search para-
% meters and are usually based on a heuristic
% accumulated costs. Promise is a measure of
% how promising a node is. Promise may repre-
% sent the estimated number of moves for the
% entire path, or it may represent the est.
% number of moves from this leaf on. (Not
% including the number of moves leading to
% this leaf. Or, promise may be a measure
% that is a compromise of the two. In any
% event, the leaf that "promises" the least
% number (whatever measure used) will be
% selected for expansion first.
solve(Solution).
solve(SolPath) :-
repeat,
[!retrieveb(l,P,l(P,C,PR,N))!], %get most Promising leaf in leaf btree
% leaf(Promise,Costs,ParentRef#,Node)
((goal(N), %See if leaf satisfies the goal
gpath(l(P,C,PR,N),SolPath)); %GetFullPath Node,Start or leaves??? XStart?
(expand(l(P,C,PR,N)), %Try to expand the leaf
fail)).
gpath(l(P,C,PR,N),Path) :-
gp(PR,T),
reverse([N|T],Path).
gp(Ref,SolPath) :-
instance(Ref,root),
SolPath=[].
gp(Ref,[N|T]) :-
instance(Ref,t(PR,N,NS)),
gp(PR,T).
reverse(L,R) :- rev(L,[],R).
rev([H|T],Acc,R) :- %uses an accumalator
rev(T,[H|Acc],R).
rev([],Acc,Acc).
%expand(leaf) might better be described as live/die because the leaf may turn
% into a tree or it may die (if it has no successors), possibly causing its
% predicessors to also die if they no longer have successors.
expand(l(P,C,PR,N)) :-
nl,
ctr_set(0,0),
removeb(l,P,l(P,C,PR,N)), %make this a tree if possible
asserta((t(PR,N,0))), % with 0 successors
key(t(PR,N,0),KRef), %Find Reference number for this tree...
nref(KRef,TRef), % TRef is the Reference number for this tree
((s(N,S,CC), %s(Node,Successornode,CostsofstateChange)
%OBS: ifthen(not val(S),(write($!!!!!!NOT VALID STATE!!!!!!!!!$),get0(_))),
[!not onpath(S,TRef), %make sure Successornode not already in path
ctr_inc(0,NS), %Count the NumberofSuccessornodes
SC is C + CC, %SuccessornodeCosts is previousleafCosts + CC
type(Mg,Mh), %Determines the type of search: Mh=0 is
% breadth-first, Mg=0 ignores costs thus far.
h(S,H), %Heuristic estimate of this successor node
write(S),write($ h:$),write(H),
ifthen(H=54,test),
SP is Mg*SC + Mh*H, %SuccessornodePromise value dpends on type of search
% but is based on SuccessornodeCosts & its heuristic
write($ p:$),write(SP),write($ c:$),write(SC),write($ beat:$),write(P),nl,
recordb(l,SP,l(SP,SC,TRef,S))!], %newl(SP,SC,TreeRef#,SucNode)
fail); %Generate all of the Successorleaves
true), %Succeed always
ctr_is(0,NS), %NumberofSuccessornodes
ifthenelse(NS>0, %if successors exist
replace(TRef,t(PR,N,NS)), %then update the number of successors
prune(TRef) %else prune deadend trees on the way to root
).
test.
onpath(S,Ref) :-
instance(Ref,t(PR,N,NS)),
(S=N;onpath(S,PR)).
prune(Ref) :-
nl,write($!!!!!!!!!!!!!!!!!!PRUNING!!!!!!!!!!!!!!!!!!!!!!!!!!$),get0(_),
instance(Ref,t(PR,N,NS)),
Ns is NS - 1, %Newnumberofsuccessors is one lessthan before
ifthenelse(Ns > 0, %if Newnumberofsuccessors indicates successrs
replace(Ref,t(PR,N,Ns)), %then update the number of successors
(hard_erase(Ref), %else cut it off and
prune(PR))). % prune predecessor