🚀 go-pugleaf

In article <1992Apr10.152629.23461@newcastle.ac.uk> Shinji.Kono@newcastle.ac.uk (Shinji KONO) writes:
>In article <13856@star.cs.vu.nl> erwvegm@cs.vu.nl (Erwin van Egmond) writes:
> ...
>How about try DIFD search?
>	0) let depth  = 1
>	1) do depth first search once
>	2) if no solution increment depth and goto 1)
>
> ...
>I find it in the book called Search method in AI, but I can't remember exactly.

Some references on DFID (= Depth-First Iterative Deepening;
or, in Mark Stickel's terminology, consecutively-bounded
depth-first search):

@ARTICLE{Korf-DFID,
	AUTHOR="Richard E. Korf",
	TITLE="Depth-First Iterative-Deepening:
		An Optimal Admissible Tree Search",
	JOURNAL=AImag,
	VOLUME=27,
	NUMBER=1,
	YEAR=1985,
	PAGES="97-109"
	}

@ARTICLE{Korf-Planning,
	AUTHOR="Richard E. Korf",
	TITLE="Planning as Search:  A Quantitative Approach",
	JOURNAL=AImag,
	VOLUME=33,
	NUMBER=1,
	YEAR=1987,
	PAGES="65-88"
	}


@INPROCEEDINGS{Korf-AStar,
	AUTHOR="Richard E. Korf",
	TITLE="Iterative-Deepening A*:
		An Optimal Admissible Tree Search",
	BOOKTITLE=ijcai9,
	PAGES="1034-1036",
	PUBLISHER="Morgan Kaufmann Publishers, Inc.",
	ADDRESS="Los Altos, CA",
	YEAR=1985
	}

@INPROCEEDINGS{Korf-RealTimeHeuristic,
	AUTHOR="Richard E. Korf",
	TITLE="Real-Time Heuristic Search:  First Results",
	BOOKTITLE=aaai87,
	PAGES="133-138",
	PUBLISHER="Morgan Kaufmann Publishers, Inc.",
	ADDRESS="Los Altos, CA",
	YEAR=1987
	}

@INPROCEEDINGS{PTTP1,
	AUTHOR="Mark E. Stickel",
	TITLE="A Prolog Technology Theorem Prover",
	BOOKTITLE=slp84,
	PAGES="211-217",
	ADDRESS="Atlantic City",
	YEAR=1984
	}


@INPROCEEDINGS{PTTP2,
	AUTHOR="Mark E. Stickel",
	TITLE="A Prolog Technology Theorem Prover:
		Implementation by an Extended Prolog Compiler",
	BOOKTITLE=AD8,
	EDITOR={J\"org H. Siekmann},
	PAGES="573-587",
	PUBLISHER="Springer-Verlag",
	ADDRESS="New York",
	YEAR=1986
	}


@TECHREPORT{PTTP-Report,
	AUTHOR="Mark E. Stickel",
	TITLE="A Prolog Technology Theorem Prover:
	       Implementation by an Extended Prolog Compiler",
	TYPE="Technical Note",
	NUMBER="382R",
	INSTITUTION="SRI International",
	ADDRESS="Menlo Park, CA",
	MONTH=nov,
	YEAR=1987
	}

@INPROCEEDINGS{CBDFS,
	AUTHOR="Mark E. Stickel and W. Mabry Tyson",
	TITLE="An Analysis of Consecutively Bounded Depth-First Search
		with Applications in Automated Deduction",
	BOOKTITLE=ijcai9,
	PUBLISHER="Morgan Kaufmann Publishers, Inc.",
	ADDRESS="Los Altos, CA",
	PAGES="1073-1075",
	YEAR=1985
	}

For a discussion of the technique specifically in Prolog,
see Section 2.12 of Richard's Craft of Prolog.
-- 
------------------------------------------------------------------
Francois-Michel Lang          (202) 752-6067   FAX: (202) 752-4463
uunet!almserv!alufml ........ Fannie Mae; Asset/Liability Strategy
lang@linc.cis.upenn.edu ..... Dept of Comp & Info Science, U of PA