|
Abstract : |
Abstract. Algorithms that produce consistent constraint networks have been studied greatly in recent years. Most of the effort in this research has been targeted at the efficiency of such algorithms. We have studied the performance of arc consistency algorithms from a different perspective using an implementation independent parameter, the actual amount of pruning required to achieve arc consistency. Our results show that for certain types of problems there is a clear cut off point at which the use of arc-consistency algorithms can be considered useless as a preprocessing technique. These results appear to confirm the predictions made by Van Beek and they provide us with a potentially useful criterion for deciding when not to use arcconsistency preprocessing. CSM-236 page- 2, |
