Changeset 4307 for trunk

Show
Ignore:
Timestamp:
06/09/08 11:40:36 (3 months ago)
Author:
pmoura
Message:

Updated all the search methods in the "searching" example to delegate checking for cycles to the state space being searched (thus allowing state descriptions to carry additional information that should not be taken into account when comparing states).

Location:
trunk
Files:
7 modified

Legend:

Unmodified
Added
Removed

  • trunk/examples/searching/best_first1.lgt

    r2383 r4307  
    55 
    66    :- info([ 
    7         version is 1.1, 
     7        version is 1.2, 
    88        author is 'Paulo Moura', 
    9         date is 2005/10/22, 
     9        date is 2008/6/9, 
    1010        comment is 'Best first heuristic state space search strategy.', 
    1111        source is 'Example adopted from the book "Prolog Programming for Artificial Intelligence" by Ivan Bratko.', 
    … …  
    3434        F =< Threshold, 
    3535        (bagof(Next/Cost2, 
    36             (Space::next_state(State, Next, Cost2), \+ member(Next, Path)), 
     36            (Space::next_state(State, Next, Cost2), \+ Space::member_path(Next, Path)), 
    3737            Successors) -> 
    3838                succlist(G, Successors, Trees, Threshold, Space), 

  • trunk/examples/searching/breadth_first1.lgt

    r2383 r4307  
    55 
    66    :- info([ 
    7         version is 1.1, 
     7        version is 1.2, 
    88        author is 'Paulo Moura', 
    9         date is 2005/10/22, 
     9        date is 2008/6/9, 
    1010        comment is 'Breadth first state space search strategy.', 
    1111        source is 'Example adopted from the book "Prolog Programming for Artificial Intelligence" by Ivan Bratko.', 
    … …  
    2323    breadt(Space, Tree, Bound, Solution) :- 
    2424        expand([], Tree, Tree2, Solved, Solution, Space, Bound), 
    25         (Solved -> 
     25        (   Solved -> 
    2626            true 
    27             ; 
    28             breadt(Space, Tree2, Bound, Solution)). 
     27        ;   breadt(Space, Tree2, Bound, Solution) 
     28        ). 
    2929 
    3030 
    … …  
    3434    expand(Path, l(State), t(State, Subs), fail, _, Space, Bound) :- 
    3535        Bound > 0, 
    36         bagof(l(Next), 
    37             (Space::next_state(State, Next), 
    38             \+ member(Next, [State| Path])), 
    39             Subs). 
     36        bagof(l(Next), (Space::next_state(State, Next), \+ Space::member_path(Next, [State| Path])), Subs). 
    4037 
    4138    expand(Path, t(State,Subs), t(State, Subs2), Solved, Solution, Space, Bound) :- 
    … …  
    4946        Bound2 is Bound -1, 
    5047        expand(Path, Tree, Tree2, Solved2, Solution, Space, Bound2), 
    51         (Solved2 -> 
     48        (   Solved2 -> 
    5249            Solved = true 
    53             ; 
    54             expandall(Path, Trees, [Tree2| Trees2], Subs2, Solved, Solution, Space, Bound)) 
     50        ;   expandall(Path, Trees, [Tree2| Trees2], Subs2, Solved, Solution, Space, Bound) 
     51        ) 
    5552        ; 
    5653        expandall(Path, Trees, Trees2, Subs2, Solved, Solution, Space, Bound). 

  • trunk/examples/searching/depth_first1.lgt

    r2383 r4307  
    55 
    66    :- info([ 
    7         version is 1.1, 
     7        version is 1.2, 
    88        author is 'Paulo Moura', 
    9         date is 2005/10/22, 
     9        date is 2008/6/9, 
    1010        comment is 'Depth first state space search strategy.', 
    1111        parnames is ['Bound']]). 
    … …  
    2626        Bound > 0, 
    2727        Space::next_state(State, Next), 
    28         \+ member(Next, [State| Path]), 
     28        \+ Space::member_path(Next, [State| Path]), 
    2929        Bound2 is Bound - 1, 
    3030        depth(Space, Next, Bound2, [State| Path], Solution). 

  • trunk/examples/searching/hill_climbing1.lgt

    r1401 r4307  
    55 
    66    :- info([ 
    7         version is 1.1, 
     7        version is 1.2, 
    88        author is 'Paulo Moura', 
    9         date is 2004/8/15, 
     9        date is 2008/6/9, 
    1010        comment is 'Hill climbing heuristic state space search strategy.', 
    1111        parnames is ['Threshold']]). 
    1212 
    1313 
    14     :- uses(list, 
    15         [member/2, reverse/2, sort/2]). 
    16  
    17     :- private(hill/7). 
     14    :- uses(list, [member/2, reverse/2, sort/2]). 
    1815 
    1916 
    … …  
    3027            (Estimate, Cost, Next), 
    3128            (Space::next_state(State, Next, Cost), 
    32              \+ member(Next, [State| Path]), 
     29             \+ Space::member_path(Next, [State| Path]), 
    3330             Space::heuristic(Next, Guess), 
    3431             Estimate is Guess + Cost), 

  • trunk/examples/searching/salt3.lgt

    r2738 r4307  
    2828    instantiates(state_space)). 
    2929 
    30  
    3130    :- info([ 
    32         version is 1.0, 
     31        version is 1.1, 
    3332        author is 'Paula Marisa Sampaio', 
    34         date is 2005/06/08, 
     33        date is 2008/6/9, 
    3534        comment is 'Salt state-space search problem.']). 
    3635 
    37  
    3836    % each state is represented by a compound term with four arguments: (Acumulator, Measure1, Measure2, Step) 
    39  
    4037    initial_state(initial, (0, 0, 0, all_empty)). 
    4138 
    42  
    4339    % the intended salt quantity must end up on the acumulator 
    44  
    4540    goal_state(acumulator, (Acumulator, _, _, _)) :- 
    4641        parameter(1, Acumulator). 
    4742 
    48  
    4943    % state transitions: 
    5044 
    51  
    5245    % emptying a measure into the accumulator 
    53  
    5446    next_state((Acc, X, Y, _), (NewAcc, 0, Y, transfer(m1, acc))) :- 
    5547        X > 0, 
    5648        NewAcc is Acc + X. 
    57  
    5849    next_state((Acc, X, Y, _), (NewAcc, X, 0, transfer(m2, acc))) :- 
    5950        Y > 0, 
    6051        NewAcc is Acc + Y. 
    61          
    6252 
    6353    % filling up of one of the measures 
    64  
    6554    next_state((Acc, X, Y, Step), (Acc, MaxX, Y, fill(m1))) :- 
    6655        parameter(2, MaxX), 
    6756        X < MaxX, 
    6857        Step \= empty(m1). 
    69  
    7058    next_state((Acc, X, Y, Step), (Acc, X, MaxY, fill(m2))) :- 
    7159        parameter(3, MaxY), 
    … …  
    7361        Step \= empty(m2). 
    7462 
    75  
    7663    % either pouring of a measure into the other till it is filled up 
    7764    % or all content of a measure into the other one 
    78  
    7965    next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m2, m1))) :- 
    8066        parameter(2, MaxX), 
    … …  
    8874            Z = 0 
    8975         ). 
    90  
    9176    next_state((Acc, X, Y, _), (Acc, W, Z, transfer(m1, m2))) :- 
    9277        parameter(3, MaxY), 
    … …  
    10186         ). 
    10287 
    103  
    10488    % throwing out the contents of a measure; does not afect the accumulator 
    105   
    106     next_state((Acc, X, Y, Step), (Acc, 0, Y, empty(m1))) :- 
     89    next_state((Acc, X, Y, Step), (Acc, 0, Y, empty(m1))) :- 
    10790        X > 0, 
    10891        Step \= fill(m1). 
    109   
    110     next_state((Acc, X, Y, Step), (Acc, X, 0, empty(m2))) :- 
     92    next_state((Acc, X, Y, Step), (Acc, X, 0, empty(m2))) :- 
    11193        Y > 0, 
    11294        Step \= fill(m2). 
    11395 
     96    member_path((Acc, X, Y, _), [(Acc, X, Y, _)| _]) :- 
     97        !. 
     98    member_path(State, [_| Path]) :- 
     99        member_path(State, Path). 
    114100 
    115101    print_state((Acc, X, Y, Step)) :- 
    116102        write('('), write((Acc, X, Y)), write(')    '), write(Step), nl. 
    117103 
    118  
    119104:- end_object. 

  • trunk/examples/searching/state_space.lgt

    r2381 r4307  
    66 
    77    :- info([ 
    8         version is 1.0, 
     8        version is 1.1, 
    99        author is 'Paulo Moura', 
    10         date is 1998/3/23, 
     10        date is 2008/6/9, 
    1111        comment is 'State space description predicates.']). 
    1212 
    … …  
    4242         argnames is ['Name', 'State']]). 
    4343 
     44    :- public(member_path/2). 
     45    :- mode(member_path(+nonvar, +list), zero_or_one). 
     46    :- info(member_path/2, 
     47        [comment is 'True if a state is member of a list of states.', 
     48         argnames is ['State', 'Path']]). 
     49 
    4450    :- public(print_state/1). 
    4551    :- mode(print_state(+nonvar), one). 
    … …  
    6773 
    6874 
     75    member_path(State, [State| _]) :- 
     76        !. 
     77    member_path(State, [_| Path]) :- 
     78        member_path(State, Path). 
     79 
     80 
    6981    print_path([]). 
    7082 

  • trunk/RELEASE_NOTES.txt

    r4306 r4307  
    4343    Added missing implementation of the predicate as_dictionary/2 to the  
    4444    "bintree" library object. Thanks to Victor Noel for the bug report. 
     45 
     46    Updated all the search methods in the "searching" example to delegate  
     47    checking for cycles to the state space being searched (thus allowing  
     48    state descriptions to carry additional information that should not be  
     49    taken into account when comparing states). 
    4550 
    4651    Updated the syntax coloring support for the Vim text editor to properly