Some code from The Art of Prolog, 1986
Algorithms that forget their history are doomed to repeat it. (Artificial Intelligence: A Modern Approach)
1. Depth-First-Search
A frame work of dfs:
%: solve_dfs(State, History, Moves) :-
% Moves is the sequence of moves to reach a desired final state from the current State,
% where History contains the states visited previously.
solve_dfs(State, History, []) :-
final_state(State).
solve_dfs(State, History, [Move|Moves]) :-
move(State, Move),
update(State, Move, State1),
legal(State1),
\+ member(State1, History),
solve_dfs(State1, [State1|History], Moves).
The History list can prevent the cycle in the searching tree, but can not avoid to trace several times in the same states.
A iterative version:
%: solve_iter_dfs(State, History, Moves) :-
solve_iter_dfs(State, History, Moves, N) :-
N < MaxIter,
(solve_dfs(State, History, Moves, 0, N)
;
N1 = N+1,
solve_iter_dfs(State, History, Moves, N1)).
solve_dfs(State, History, [], _, _) :-
final_state(State).
solve_dfs(State, History, [Move|Moves], N, NF) :-
N < NF,
move(State, Move),
update(State, Move, State1),
legal(State1),
\+ member(State1, History),
N1 is N + 1,
solve_dfs(State1, [State1|History], Moves, N1, NF).
A example:
wolf, goat and cabbage problem.
initial_state(wgc, wgc(left, [wolf, goat, cabbage], [])).final_state(wgc(right, [], [wolf, goat, cabbage])).move(wgc(left, L, R), Cargo) :- member(Cargo, L).move(wgc(right,L, R), Cargo) :- member(Cargo, R).move(wgc(B,L,R), alone).update(wgc(B,L,R),Cargo,wgc(B1, L1, R1)) :- update_boat(B, B1), update_banks(Cargo, B, L, R, L1, R1).update_boat(left, right).update_boat(right, left).update_banks(alone, B, L, R, L, R).update_banks(Cargo, left, L, R, L1, R1) :- select(Cargo, L, L1), insert(Cargo, R, R1).update_banks(Cargo, right, L, R, L1, R1) :- select(Cargo, R, R1), insert(Cargo, L, L1).insert(X, [Y|Ys], [X, Y|Ys]):- precedes(X, Y).insert(X, [Y|Ys], [Y|Zs]) :- precedes(Y, X), insert(X, Ys, Zs).insert(X, [], [X]).precedes(wolf, X).precedes(X, cabbage).legal(wgc(left, L, R)) :- \+ illegal(R).legal(wgc(right, L, R)) :- \+ illegal(L).illegal(L) :- member(wolf, L), member(goat, L).illegal(L) :- member(goat, L), member(cabbage, L).test_dfs(Problem, Moves) :- initial_state(Problem, State), solve_dfs(State, [State], Moves).
2.Breadth-First-Search:
A frame work of BFS:
solve(Start, Solution) :- breadthfirst([[Start]], Solution). breadthfirst([[Node|Path]|_], [Node|Path]) :- goal(Node). breadthfirst([Path|Paths], Solution) :- extend(Path, NewPaths), conc(Paths, NewPaths, Paths1), breadthfirst(Paths1, Solution). extend([Node|Path], NewPaths) :- bagof([NewNode, Node|Path], (s(Node, NewNode), not member(NewNode, [Node|Path])), NewPaths), !.
A more efficient version:
solve(Start, Solution) :-
breadthfirst([[Start]|Z]-Z, Solution). breadthfirst([[Node|Path]|_]-_, [Node|Path]) :- goal(Node). breadthfirst([[Path|Paths]-Z, solution) :- extend(Path, NewPaths), conc(NewPaths, Z1, Z), Paths \== Z1, breadthfirst(Paths, Z1, Solution). 3. Hill-climbing problem solving framework
solve_hill_climb(State, History, []) :- final_state(State).solve_hill_climb(State, History, [Move|Moves]) :- hill_climb(State, Move), update(State, Move, State1), legal(State1), \+ member(State1, History), solve_hill_climb(State1, [State1|History], Moves).hill_climb(State, Move) :- set_of(M, move(State, M), Moves), evaluate_and_order(Moves, State, [], MVs), member((Move, Value), MVs).evaluate_and_order([Move|Moves], State, MVs, OrderedMVs) :- update(State, Move, State1), value(State1, Value), insert((Move, Value), MVs, MVs1), evaluate_and_order(Moves, State, MVs1, OrderedMVs).evaluate_and_order([], State, MVs, MVs).insert(MV, [], [MV]).insert((M,V),[(M1,V1)|MVs], [(M,V),(M1,V1)|MVs]) :- V >= V1.insert((M,V),[(M1,V1)|MVs], [(M1,V1)|MVs]) :- V =< V1, insert((M,V),MVs,MVs1).