Article View: net.lang.prolog
Article #652Re: Depth First Iterative Deepening in
From: reddy
Date: Mon, 02 Jun 1986 18:09
Date: Mon, 02 Jun 1986 18:09
21 lines
1574 bytes
1574 bytes
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
Technical Details
Message-ID:
<29700026@uiucdcs>Path:
arc1-ca.pugleaf.net!utzoo!linus!philabs!cmcl2!seismo!caip!princeton!allegra!ulysses!mhuxr!mhuxn!ihnp4!inuxc!pur-ee!uiucdcs!reddyReferences:
<3145@decwrl.DEC.COM>Show Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!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