Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!caip!princeton!allegra!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!reddy
From: reddy@uiucdcs.CS.UIUC.EDU
Newsgroups: net.lang.prolog
Subject: Re: Depth First Iterative Deepening in
Message-ID: <29700026@uiucdcs>
Date: Mon, 2-Jun-86 14:09:00 EDT
Article-I.D.: uiucdcs.29700026
Posted: Mon Jun  2 14:09:00 1986
Date-Received: Wed, 4-Jun-86 19:33:34 EDT
References: <3145@decwrl.DEC.COM>
Lines: 21
Nf-ID: #R:decwrl.DEC.COM:3145:uiucdcs:29700026:000:931
Nf-From: uiucdcs.CS.UIUC.EDU!reddy    Jun  2 13:09:00 1986


DFID can be viewed as an efficient implementation of Breadth-First search.
It has relevance to single solution applications as well as multiple
solution applications.  For multiple solution applications, one naturally
continues searching deeper levels even after one solution has been found.
The solutions obtained by each search should be seen as increasingly better
approximations to the set of all solutions:
	S0, S1, S2, ..... Sinfinity

Whichever way it is used, it is naturally better than pure depth-first search,
because it is complete whereas depth-first is not.

Mark Stickel has implemented a theorem prover using a variant of DFID.  See

	Stickel, A Prolog technology theorem prover, 1984 Intl symp on logic
	programming, Atlantic City.
	Stickel and Tyson, An analysis of consecutively bounded depth-first
	search with applications in automated deduction, (I think) IJCAI 85.

Uday Reddy
reddy@uiuc.arpa, uiucdcs!reddy