Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T07:09:58.828Z Has data issue: false hasContentIssue false
  • English
  • Français

Domain generating functions for solving constraint satisfaction problems

Published online by Cambridge University Press:  10 August 2016

François Major ,
Guy Lapalme  and
Robert Cedergren
François Major
Affiliation:
Département d'informatique et de Recherche Opérationnelle, Université de Montréal, Canada
Guy Lapalme
Affiliation:
Département d'informatique et de Recherche Opérationnelle, Université de Montréal, Canada
Robert Cedergren
Affiliation:
Département d'informatique et de Recherche Opérationnelle, Université de Montréal, Canada
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 presents an application of functional programming: searching a domain for elements which satisfy certain constraints. We give a very general formulation of the problem and describe ‘generate and test’, ‘backtracking’ and ‘forward checking’ algorithms. We then introduce the concept of domain generating functions to capture a common optimization during the search process: using partial solutions to reduce the size of the search space. We compare the efficiency of the original algorithms and those using domain generating functions first with the ‘classical’ n-queens example, and then with a problem having larger domains to search which was inspired by an application in macromolecular structure determination. Using algorithms coded in Miranda, Haskell and Common Lisp, we show that a high order (lazy) functional language is a useful and efficient tool for prototyping search methods in large complex domains.

Type
Research Article
Information
Journal of Functional Programming , Volume 1 , Issue 2 , April 1991 , pp. 213 - 227
Copyright
Copyright © Cambridge University Press 1991

References

Augustsson, L. and Johnsson, T. 1989. The Chalmers Lazy-ML compiler. The Computer Journal, 32 (2): 127–41.Google Scholar
Bird, R. and Wadler, P. 1988. Introduction to Functional Programming. Prentice-Hall.Google Scholar
Fasman, G. D. 1989. Protein conformation prediction. Trends Biol. Sci., 14: 295–99 (Jul.).Google Scholar
Haralick, R. M. 1980. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14: 263–313.Google Scholar
Hentenryck, P. V. 1989. Constraint Satisfaction in Logic Programming. MIT Press.Google Scholar
Hudak, P. and Wadler, P. (eds). 1990 Report on the programming language Haskell, a non-strict purely functional language (Version 1.0). Technical Report YALEU/DCS/RR777, Yale University, Department of Computer Science. (Apr.)Google Scholar
Jaffar, J. and Michaylov, S. 1987. Methodology and implementation of a constraint logic programming system. In Proceedings of the Fourth International Conference on Logic Programming: 196–218. MIT Press.Google Scholar
Knuth, D. E. 1975. Estimating the efficiency of backtrack programs. Mathematics of Computation. 29 (1): 121–36.Google Scholar
Kolata, G. 1986. Trying to crack the second half of genetic code. Science, 233: 1037–39.Google Scholar
Major, F., Feldmann, R., Lapalme, G. and Cedergren, R. 1988. FUS: a system to simulate conformational changes in biological macromolecules. CABIOS, 4 (4): 445–51.Google Scholar
Major, F., Gautheret, D., Turcotte, M., Lapalme, G., Jolicoeur, L., Fillion, E. and Cedergren, R. J. The prediction of RNA 3-D structures by combining symbolic and numerical computation. (Submitted for publication, 1990).Google Scholar
Rich, A. and RajBhandary, U. L. 1976. Transfer RNA: molecular structure, sequence, and properties. Annual Review of Biochemistry, 45: 805–60.Google Scholar
Steele, G. 1990. Common Lisp, the Language. Digital Press.Google Scholar
Turner, D. A. 1985. Miranda—a non-strict functional language with polymorphic types. In Jouannaud, P. (editor) Conference on Functional Programming and Computer Architecture, volume 201 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Wadler, P. 1985. How to replace failure by a list of successes. In Jouannaud, P. (editor), Conference on Functional Programming and Computer Architecture, volume 201 of Lecture Notes in Computer Science, Springer-Verlag.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.