AbstractA 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 intervariable 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 - along-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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).