Q about Bratko exercise 11.3, iterative deepening

• Previous message: Peter Van Roy: "Preliminary call for participation to MOZ 2004"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Sun, 15 Aug 2004 21:40:12 +0200

Hi,

I got stuck with exercise 11.3 from I. Bratko's Programming for AI,
3rd ed. and I appreciate some help on understanding his iterative
deepening algorithm on page 664.

For the matter of completeness, I am using ESL Prolog-2; this is not a
student task (too old); just pure interest and (my) brain challenge.

When I trace the execution, the id_path precidate is never called
recursively. In the following code, my problem seems to be with the
variable Template. Initially, an empty list is instantiated with
Template and passed through id_path to the path predicate, which
consequently fails because it expects at least one path in Path.

Then, following the disjunction, copy_term is supposed to rename the
variables in Template. However, variable Template is still
instantiated with the empty list, so copy_term([],P) returns P also as
an empty list.

copy_term makes sense with variables as arguments, but how is the
Template filled the first time?

Here seems to be the problem, because the subsequent path(First,_,P)
makes sense only if P equals a list with at least one path or one
variable.

Any help or tip is very much appreciated.

Thanks, Norbert

This is the code from I. Bratko's book (hopefully no typos):

/* Iterative deepening search that stops increasing depth
*/
/* when there is no path to current depth.
*/

iterative_deepening(Start, Solution) :-
  id_path(Start, Node, [], Solution),
  goal(Node).

/* path(First, Last, Path): Path is a list of nodes between First and
Last */

path(First, First, [First]).

path(First, Last, [First, Second|Rest]) :-
  s(First, Second),
  path(Second, Last, [Second|Rest]).

/* Iterative deepening path generator
*/
/* id_path(First, Last, Template, Path): Path is a path between First
and */
/* Last no longer than template list Template. Alternative paths are
*/
/* generated in the order of increasing length.
*/

id_path(First, Last, Template, Path) :-
  Path = Template,
  path(First, Last, Path)
  ;
  copy_term(Template, P),
  path(First, _, P), !, /* At least one path of Template
length */
  id_path(First, Last, [_|Template], Path). /* Longer template
*/

/* My additions */

copy_term(Term, Copy) :- /* Bratko's frequent.pl */
  asserta(term_to_copy(Term)),
  retract(term_to_copy(Copy)),!.

s(a,b).
s(b,d).
s(d,h).
s(b,e).
s(e,i).
s(e,j).
s(a,c).
s(c,f).
s(f,k).
s(c,g).

goal(j).

Norbert Giese, 71116 Gaertringen, A.-Stifter-Weg 10

• Previous message: Peter Van Roy: "Preliminary call for participation to MOZ 2004"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]