A* with Iterative Deepening Search

This is a framework for an A* with Iterative Deepening (IDA*) search, inspired by the other similar search frameworks given in Sterling and Shapiro's "The Art of Prolog".

Only one solution is found.

A more efficient version is obtained if, instead of incrementing Limit by 1 in idastar_1/4, the minimum value of F when F exceeds Limit in idastar_2/6 is used for the new value of Limit. This is left as an exercise for the reader!

idastar(Moves):-
  initial_posn(Position),
  value(Position, H),
  idastar_1(Position, H, H, Moves), !.
  
idastar_1(Position, F, Limit, Moves):-
  idastar_2([Position], 0, F, Limit, Moves).
idastar_1(Position, F, Limit, Moves):-
  Limit1 is Limit + 1,
  idastar_1(Position, F, Limit1, Moves).

idastar_2([Position|_], _, _, _, []):-
  final_posn(Position), !.
idastar_2(Positions0, G, F, Limit, [Move|Moves]):-
  Positions0 = [Position|Positions],
  F =< Limit,
  move(Position, Move),
  update(Position, Move, Position1),
  legal(Position1),
  \+ member(Position1, Positions),
  value(Position1, H1),
  G1 is G + 1,
  F1 is G1 + H1,
  idastar_2([Position1|Positions0], G1, F1, Limit, Moves).

/*
 * Test data
 * Five Jealous Husbands - Sterling and Shapiro - Exercise 18.1 (iii)
 * Goal: idastar(Moves).
 */

/* p(WhereTheBoatIs, PeopleOnIsle, PeopleOnBank) */

  initial_posn(p(isle, [h1,h2,h3,h4,h5,w1,w2,w3,w4,w5], [])).
% initial_posn(p(isle, [h1,h2,h3,h4,w1,w2,w3,w4], [])).
% initial_posn(p(isle, [h1,h2,h3,w1,w2,w3], [])).

final_posn(p(bank, [], _)).

move(p(isle, I, _), [P1]):-       /* Move one person from isle to bank   */
  member(P1, I).
move(p(isle, I, _), [P1,P2]):-    /* Move two people from isle to bank   */
  rest(I, P1, I1),
  member(P2, I1), 
  legal_1([P1,P2]).
move(p(isle, I, _), [P1,P2,P3]):- /* Move three people from isle to bank */
  rest(I, P1, I1), 
  rest(I1, P2, I2), 
  member(P3, I2), 
  legal_1([P1,P2,P3]).
move(p(bank, _, B), [P1]):-       /* Move one person from bank to isle   */
  member(P1, B).
move(p(bank, _, B), [P1,P2]):-    /* Move two people from bank to isle   */
  rest(B, P1, B1), 
  member(P2, B1), 
  legal_1([P1,P2]).
move(p(bank, _, B), [P1,P2,P3]):- /* Move three people from bank to isle */
  rest(B, P1, B1), 
  rest(B1, P2, B2), 
  member(P3, B2), 
  legal_1([P1,P2,P3]).

update(p(isle, I1, B1), Boat, p(bank, I2, B2)):-
  ord_delete(Boat, I1, I2), 
  ord_insert(Boat, B1, B2).
update(p(bank, I1, B1), Boat, p(isle, I2, B2)):-
  ord_delete(Boat, B1, B2), 
  ord_insert(Boat, I1, I2).

/* This uses a crude (under)estimation of the number of remaining voyages  */
/*   as the evaluation function.                                           */
value(p(isle, Xs, _), L):-length(Xs, M), L is (M // 2) * 2 - 1.
value(p(bank, Xs, _), L):-length(Xs, M), L is (M + 1) // 2 * 2.

legal(p(_, Xs, Ys)):-legal_1(Xs), legal_1(Ys).

legal_1(Xs):-only_wives(Xs), !.
legal_1(Xs):-wives_with_husbands(Xs, Xs).

only_wives([]).
only_wives([W|Xs]):-couple(_, W), only_wives(Xs).

wives_with_husbands([], _).
wives_with_husbands([H|Xs], Ys):-
  couple(H, _), !, 
  wives_with_husbands(Xs, Ys).
wives_with_husbands([W|Xs], Ys):-
  couple(H, W), 
  member(H, Ys), 
  wives_with_husbands(Xs, Ys).
  
couple(h1, w1). couple(h2, w2). couple(h3, w3). 
couple(h4, w4). couple(h5, w5). 

/* ord_delete(Xs, Ys, Zs) is true if Zs is the ordered list obtained       */
/*   by deleting the ordered list Xs from the ordered list Ys.             */
ord_delete([], Ys, Ys).
ord_delete([X|Xs], [X|Ys], Zs):-
  !, ord_delete(Xs, Ys, Zs).
ord_delete([X|Xs], [Y|Ys], Zs):-
  X @> Y, !, Zs = [Y|Ws], ord_delete([X|Xs], Ys, Ws).
ord_delete([_|Xs], Ys, Zs):-
  ord_delete(Xs, Ys, Zs).

/* ord_insert(Xs, Ys, Zs) is true if Zs is the ordered list obtained       */
/*   by inserting the ordered list Xs in the ordered list Ys.              */
ord_insert([], Ys, Ys).
ord_insert([X|Xs], [Y|Ys], Zs):-
  Y @=< X, !, Zs = [Y|Ws], ord_insert([X|Xs], Ys, Ws).
ord_insert([X|Xs], Ys, [X|Zs]):-
  ord_insert(Xs, Ys, Zs).

/* rest(Xs, Y, Zs) is true if Zs is the list of elements following the     */
/*   element Y in the list Xs.                                             */
rest([X|Xs], X, Xs).
rest([_|Xs], Y, Zs):-rest(Xs, Y, Zs).

LPA Index     Home Page

Valid HTML 4.01 Strict