Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!husc6!harvard!seismo!mcvax!unido!ecrcvax!micha From: micha@ecrcvax.UUCP (Micha Meier) Newsgroups: net.lang.prolog Subject: Re: Depth First Iterative Deepening in parallel PROLOGs Message-ID: <234@ecrcvax.UUCP> Date: Wed, 28-May-86 10:21:47 EDT Article-I.D.: ecrcvax.234 Posted: Wed May 28 10:21:47 1986 Date-Received: Fri, 30-May-86 09:13:21 EDT References: Reply-To: micha@ecrcvax.UUCP (Micha Meier) Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 33 Some points to a possible implementation of DFID search in Prolog: 1. The DFID algorithm always finds the solution; so does a useful Prolog program, unless it goes into an infinite loop. This means that DFID can never find a solution in a shorter time than the usual Prolog: either Prolog's depth-first search is faster or Prolog fails to find anything and it loops. The same holds then for a parallell implementation of DFID, it could only be a way to prevent infinite loops in a better time than a serial DFID rather than speeding up the search in comparison with Prolog. 2. DFID always finds the optimal solution, the usual Prolog finds *any* and maybe all solutions if necessary. If the user wants to find all solutions and the usual Prolog loops, DFID will loop as well; therefore the use of DFID could be only restricted. 3. As Max says, the predicates would have to be divided into two groups, ordered and unordered; this would be the case in any non-sequential processing of the subgoals. If we allow ordered predicates to call the unordered ones and vice versa then the distribution of processors in a parallell execution is no more so easy. There is maybe a simple solution to this problem, otherwise one direction of calls between the two classes of predicates must be forbidden - is it a significant restriction? (I suspect anyway that this is another of George's attempts to bring flames into net.lang.prolog, right? :-) Micha