Consistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics

摘要

A new parameter is introduced to characterize a type of search problem of broad relevance in artificial intelligence, operations research and symbolic logic. This parameter, which we call inter-variable compatibility, is particularly important in that complexity analyses incorporating it are able to capture the dependence of problem complexity on search order used by an algorithm. Thus compatibility-based theories can provide a theoretical basis for the extraction of heuristics for choosing good search orderings—a long-sought goal for such problems, since it can lead to significant savings during search. We carry out expected-complexity analyses for the traditional backtrack algorithm as well as for two more recent algorithms that have been found empirically to be significant improvements: forward checking and word-wise forward checking. We extract compatibility-based ordering-heuristics from the theory for forward checking. Preliminary experimental results are presented showing the large savings that result from their use. Similar savings can be expected for other algorithms when heuristics taking account of inter-variable compatibilities are used. Our compatibility-based theories also provide a more precise way of predicting which algorithm is best for a given problem.