Show
Ignore:
Timestamp:
06/09/08 16:46:15 (6 months ago)
Author:
pmoura
Message:

Updated the "salt" state-space search example to support heuristics.

Files:
1 modified

Legend:

Unmodified
Added
Removed

  • trunk/examples/searching/salt3.lgt

    r4307 r4308  
    2626 
    2727:- object(salt(_Acumulator, _Measure1, _Measure2), 
    28     instantiates(state_space)). 
     28    instantiates(heuristic_state_space)). 
    2929 
    3030    :- info([ 
    … …  
    3232        author is 'Paula Marisa Sampaio', 
    3333        date is 2008/6/9, 
    34         comment is 'Salt state-space search problem.']). 
     34        comment is 'Salt state-space search problem (updated from the original 1.0 version to support heuristics).']). 
    3535 
    3636    % each state is represented by a compound term with four arguments: (Acumulator, Measure1, Measure2, Step) 
    … …  
    4444 
    4545    % emptying a measure into the accumulator 
    46     next_state((Acc, X, Y, _), (NewAcc, 0, Y, transfer(m1, acc))) :- 
     46    next_state((Acc, X, Y, _), (NewAcc, 0, Y, transfer(m1, acc)), 1) :- 
    4747        X > 0, 
    4848        NewAcc is Acc + X. 
    49     next_state((Acc, X, Y, _), (NewAcc, X, 0, transfer(m2, acc))) :- 
     49    next_state((Acc, X, Y, _), (NewAcc, X, 0, transfer(m2, acc)), 1) :- 
    5050        Y > 0, 
    5151        NewAcc is Acc + Y. 
    5252 
    5353    % filling up of one of the measures 
    54     next_state((Acc, X, Y, Step), (Acc, MaxX, Y, fill(m1))) :- 
     54    next_state((Acc, X, Y, Step), (Acc, MaxX, Y, fill(m1)), 1) :- 
    5555        parameter(2, MaxX), 
    5656        X < MaxX, 
    5757        Step \= empty(m1). 
    58     next_state((Acc, X, Y, Step), (Acc, X, MaxY, fill(m2))) :- 
     58    next_state((Acc, X, Y, Step), (Acc, X, MaxY, fill(m2)), 1) :- 
    5959        parameter(3, MaxY), 
    6060        Y < MaxY, 
    … …  
    6363    % either pouring of a measure into the other till it is filled up 
    6464    % or all content of a measure into the other one 
    65     next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m2, m1))) :- 
     65    next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m2, m1)), 1) :- 
    6666        parameter(2, MaxX), 
    6767        Y > 0, 
    … …  
    7474            Z = 0 
    7575         ). 
    76     next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m1, m2))) :- 
     76    next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m1, m2)), 1) :- 
    7777        parameter(3, MaxY), 
    7878        X > 0, 
    … …  
    8787 
    8888    % throwing out the contents of a measure; does not afect the accumulator 
    89     next_state((Acc, X, Y, Step), (Acc, 0, Y, empty(m1))) :- 
     89    next_state((Acc, X, Y, Step), (Acc, 0, Y, empty(m1)), 1) :- 
    9090        X > 0, 
    9191        Step \= fill(m1). 
    92     next_state((Acc, X, Y, Step), (Acc, X, 0, empty(m2))) :- 
     92    next_state((Acc, X, Y, Step), (Acc, X, 0, empty(m2)), 1) :- 
    9393        Y > 0, 
    9494        Step \= fill(m2). 
     95 
     96    heuristic((Acc, Acc, _, _), 0.1) :- 
     97        parameter(1, Acc), 
     98        !. 
     99    heuristic((Acc, _, Acc, _), 0.1) :- 
     100        parameter(1, Acc), 
     101        !. 
     102    heuristic((Acc, X, Y, _), 0.2) :- 
     103        parameter(1, Acc), 
     104        Acc is abs(X - Y), 
     105        !. 
     106    heuristic((Acc, X, _, _), 0.3) :- 
     107        parameter(1, Acc), 
     108        (   X mod Acc =:= 0 -> 
     109            Cost is X // Acc 
     110        ;   Acc mod X =:= 0 -> 
     111            Cost is Acc // X 
     112        ), 
     113        !. 
     114    heuristic((Acc, _, Y, _), 0.3) :- 
     115        parameter(1, Acc), 
     116        (   Y mod Acc =:= 0 -> 
     117            Cost is Y // Acc 
     118        ;   Acc mod Y =:= 0 -> 
     119            Cost is Acc // Y 
     120        ), 
     121        !. 
     122    heuristic((Acc, X, Y, _), 0.4) :- 
     123        parameter(1, Acc), 
     124        Diff is abs(X - Y), 
     125        (   Diff mod Acc =:= 0 -> 
     126            Cost is Diff // Acc 
     127        ;   Acc mod Diff =:= 0 -> 
     128            Cost is Acc // Diff 
     129        ), 
     130        !. 
     131    heuristic((_, _, _, _), 0.5). 
    95132 
    96133    member_path((Acc, X, Y, _), [(Acc, X, Y, _)| _]) :-