Merging constraint satisfaction subproblems to avoid redundant search

摘要

When solving a constraint satisfaction problem we may find similar subproblems. Algorithms not exploiting this similarity are condemned to duplicate some work. In this paper we introduce a technique for merging silbing subproblems which avoids redundnacy in search associated to their similarity. We show that, when forward checking is enhanced with this capability, its performance many be increased. Experimental results on hard crossword puzzles support the practical validity of our approach.