Increasing Tree Search Efficiency for Constraint Satisfaction Problems¶
Haralick, R. M., & Elliott, G. L. (1980). Increasing Tree Search Efficiency for Constraint Satisfaction Problems. Artificial Intelligence, 14(1), 263-313.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Backtracking
- The structure also makes the constraint-propagation-versus-search distinction concrete: forward-checking (eliminating candidates from peer cells the moment a placement is made) is work done between backtracking steps that shrinks the next subtree, complementing rather than replacing the rollback.
This sourceEstablishes forward-checking and constraint propagation as work done between backtracking steps that shrinks the remaining search tree.
- The structure also makes the constraint-propagation-versus-search distinction concrete: forward-checking (eliminating candidates from peer cells the moment a placement is made) is work done between backtracking steps that shrinks the next subtree, complementing rather than replacing the rollback.
Mechanisms¶
- Forward-Checking Table
- It only looks one commitment deep into each neighbor, so a conflict that emerges two moves out slips past it — which is why maintaining full arc consistency prunes more, at more cost.
This sourceShows that forward checking uses limited lookahead, while maintaining stronger arc consistency detects and prunes deeper conflicts at greater cost.
- It only looks one commitment deep into each neighbor, so a conflict that emerges two moves out slips past it — which is why maintaining full arc consistency prunes more, at more cost.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 2 citations of this work carries a recorded support check.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:cd94edf42a76 · see in the full table