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).