This paper develops the idea that variable ordering heuristics for CSPs can be characterised in terms of a small number of distinguishable actions or strategies, and that while specific heuristics may be classified differently depending on the problem type, the basic actions that determine their classification are the same. These strategies can be described as building up contention and propagating effects to future, uninstantiated variables. The propagation-of-effects type of action is related to the "simplification hypothesis" of Hooker and Vinay, but since this is only one of two independent actions, this work gives a more complete account of the basis of heuristic performance. The basic technique uses factor analysis to simplify the set of correlations between performance scores for a particular set of problems. The present work shows that the results of this analysis are robust, and that amenability of a problem to one or the other kind of heuristic action is also a robust effect. This approach also elucidates the effectiveness of modern adaptive heuristics by showing that they balance the two kinds of heuristic action, which is known to enhance performance. The two heuristic actions are distinguished by descriptive measures such as depth of failure and depth at which a problem becomes tractable, that reflect differences in rapidity of effects with respect to search depth. Other experiments indicate that the effectiveness of propagation-of-effects depends on the degree to which nonadjacent assignments can interact in the future part of the problem. Extensions to structured problems suggest that the theoretical analysis can be generalised, although the factor analysis of performance becomes more complicated due to the interaction of the basic actions with specific parts of the problem. This work contributes to the goals of explaining heuristic performance and putting heuristic selection on a rational basis.
展开▼
