% "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