Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-11T14:56:54.983Z Has data issue: false hasContentIssue false
  • English
  • Français

PROGRAMMING PEARL: Enhancing a search algorithm to perform intelligent backtracking

Published online by Cambridge University Press:  16 April 2004

MAURICE BRUYNOOGHE
MAURICE BRUYNOOGHE
Affiliation:
Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B3001 Heverlee, Belgium (e-mail: Maurice.Bruynooghe@cs.kuleuven.ac.be)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper illustrates how a Prolog program, using chronological backtracking to find a solution in some search space, can be enhanced to perform intelligent backtracking. The enhancement crucially relies on the impurity of Prolog that allows a program to store information when a dead end is reached. To illustrate the technique, a simple search program is enhanced.

Keywords

intelligent backtrackingdependency-directed backtrackingbackjumpingconflict-directed backjumpingnogood setslook-back
Type
Research Article
Information
Theory and Practice of Logic Programming , Volume 4 , Issue 3 , May 2004 , pp. 371 - 380
Copyright
© 2004 Cambridge University Press