文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Contradicting conventional wisdom in constraint satisfaction
侵权投诉

Contradicting conventional wisdom in constraint satisfaction

Abstract. Constraint satisfaction problems have wide application in artificial intelligence. They involve finding values for problem variables where the values must be consistent in that they satisfy restrictions on which combinations of values are allowed

preprocessing that is desirable - additional preprocessing e ort may outweigh subsequent search savings 3]. However, it seems an obvious article of faith that removing values from consideration during a preprocessing step will lead to savings during the subsequent search step - or at the very least do no harm. We demonstrate that there are circumstances in which pruning values by consistency preprocessing can in fact greatly in

crease subsequent search e ort.{ Conventional CSP wisdom says that using consistency inference during search, to prune values that become inconsistent after making search choices, is best limited to the minimalinference embodied in the forward checking algorithm. The feeling is that additional search savings produced by pruning more values will be o set by the additional inference cost. We show that maintaining full arc consistency during search is often in fact very cost e ective. To contradict the rst piece of conventional wisdom we tested the e ects of arc consistency preprocessing on one of the most popular and successful CSP algorithms: forward checking combined with dynamic domain size variable ordering. Dynamic domain size variable ordering prefers to consider variables that have fewer values left to choose from. It is a popular ordering heuristic. In a probabilistic analysis, it was shown optimal under certain assumptions by Haralick and Elliott 2]. It has proven particularly useful in conjunction with forward checking search, and we believe it to be e ective on our test problems. Another counterintuitive demonstration that pruning values can increase search e ort, was obtained recently by Prosser. He showed that pruning values can degrade performance for algorithms that employ\intelligent backtracking" (though the actual exhibited e ects were small) 4]. However, even Prosser concluded that:\We should now assume that increased consistency, or the removal of redundancies, can only guarantee a reduction in search e ort if that search is unintelligent (such as a chronological backtracker)." Forward checking is a chronological backtracker. However, we found that removing values by arc consistency preprocessing made some problems an order of magnitude more di cult to solve by our ordered forward checking search. (In fairness to Prosser though one might argue that\unintelligent" should rule out dynamic search ordering.) The explanation for this counterintuitive phenomenon is that arc consistency preprocessing is counterproductive when it interferes with the functioning of the search ordering heuristic. We interpret our results as implying that eliminating values can move a problem far enough away from the assumptions needed to demonstrate the\optimality" of dynamic domain size search ordering that the advantage of having fewer values is more than o set by the deterioration of the ordering heuristic's performance. We believe this experience is a useful object lesson in the need to exercise some care in combining CSP methods: two rights may make a wrong. This lesson is particularly relevant now as new constraint programming environments are making it easier to combine techniques for customized algorithms. To contradict the second piece of conventional wisdom we compared ordered

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email