Partition search for non-binary constraint satisfaction |
| |
Authors: | Julian R. Ullmann |
| |
Affiliation: | Department of Computer Science, King’s College London, Strand, London WC2R 2LS, United Kingdom |
| |
Abstract: | Previous algorithms for unrestricted constraint satisfaction use reduction search, which inferentially removes values from domains in order to prune the backtrack search tree. This paper introduces partition search, which uses an efficient join mechanism instead of removing values from domains. Analytical prediction of quantitative performance of partition search appears to be intractable and evaluation therefore has to be by experimental comparison with reduction search algorithms that represent the state of the art. Instead of working only with available reduction search algorithms, this paper introduces enhancements such as semijoin reduction preprocessing using Bloom filtering. |
| |
Keywords: | Constraint satisfaction Non-binary constraints Hash join Multijoin Decision diagram BDD Consistency Forward checking Semijoin reduction Dual search Partition search Random problems |
本文献已被 ScienceDirect 等数据库收录! |
|