a_star.pl

   1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   2 % Author:       Tom Schrijvers
   3 % Email:        Tom.Schrijvers@cs.kuleuven.ac.be
   4 % Copyright:    K.U.Leuven 2004
   5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   6 :- module(a_star,
   7         [
   8                 a_star/4
   9         ]).
  10
  11 :- use_module(library(lists)).
  12
  13 :- use_module(binomialheap).
  14
  15 :- use_module(find).
  16
  17 a_star(DataIn,FinalData,ExpandData,DataOut) :-
  18         a_star_node(DataIn,0,InitialNode),
  19         empty_q(NewQueue),
  20         insert_q(NewQueue,InitialNode,Queue),
  21         a_star_aux(Queue,FinalData,ExpandData,EndNode),
  22         a_star_node(DataOut,_,EndNode).
  23
  24 a_star_aux(Queue,FinalData,ExpandData,EndNode) :-
  25         delete_min_q(Queue,Queue1,Node),
  26         ( final_node(FinalData,Node) ->
  27                 Node = EndNode
  28         ;
  29                 expand_node(ExpandData,Node,Nodes),
  30                 insert_list_q(Nodes,Queue1,NQueue),
  31                 a_star_aux(NQueue,FinalData,ExpandData,EndNode)
  32         ).
  33
  34 final_node(D^Call,Node) :-
  35         a_star_node(Data,_,Node),
  36         term_variables(Call,Vars),
  37         chr_delete(Vars,D,DVars),
  38         copy_term(D^Call-DVars,Data^NCall-DVars),
  39         call(NCall).
  40
  41 expand_node(D^Ds^C^Call,Node,Nodes) :-
  42         a_star_node(Data,Score,Node),
  43         term_variables(Call,Vars),
  44         chr_delete(Vars,D,DVars0),
  45         chr_delete(DVars0,Ds,DVars1),
  46         chr_delete(DVars1,C,DVars),
  47         copy_term(D^Ds^C^Call-DVars,Data^EData^Cost^NCall-DVars),
  48         term_variables(Node,NVars,DVars),
  49         find_with_var_identity(ENode,NVars,(NCall,EScore is Cost + Score,a_star:a_star_node(EData,EScore,ENode)),Nodes).
  50
  51 a_star_node(Data,Score,Data-Score).
  52
  53
  54 chr_delete([], _, []).
  55 chr_delete([H|T], X, L) :-
  56         (   H==X ->
  57             chr_delete(T, X, L)
  58         ;   L=[H|RT],
  59             chr_delete(T, X, RT)
  60         ).