No more “Partial” and “Full Looking Ahead”

摘要

Looking ahead is a commonly used search technique in constraint satisfaction. In this paper, we examine the future role of two long established lookahead algorithms, Partial Looking Ahead (PLA) and Full Looking Ahead (FLA). We prove that PLA is inferior to Directional Arcconsistency Lookahead in that the latter will prune at least as much as the former for no more computation in each problem reduction step. Similarly, FLA is inferior to Bi-directional Arcconsistency Lookahead, an algorithm introduced in this paper. We also point out a couple of errors in the literature.