Changeset 4308 for trunk

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

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

Location:
trunk
Files:
2 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, _)| _]) :- 

  • trunk/RELEASE_NOTES.txt

    r4307 r4308  
    2525    Corrected two bugs in the implementation of the built-in meta-predicate  
    2626    threaded/1 when canceling individual threads. The first bug resulted from  
    27     out-of-order thread status messages. The second bug resultd from a leak  
     27    out-of-order thread status messages. The second bug resulted from a leak  
    2828    of thread results between calls to the threaded/1 predicate. 
    2929 
    … …  
    4747    checking for cycles to the state space being searched (thus allowing  
    4848    state descriptions to carry additional information that should not be  
    49     taken into account when comparing states). 
     49    taken into account when comparing states). Updated the "salt" example  
     50    to support heuristics. 
    5051 
    5152    Updated the syntax coloring support for the Vim text editor to properly