No more “Partial” and “Full Looking Ahead”

✍ Scribed by Edward Tsang

• Book ID: 104105440
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 702 KB
• Volume: 98
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(97)00064-7

✦ Synopsis

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 fhe literature. @ 1998 Elsevier Science B.V.