文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

forward checking with an algorithm that established and maintained full arc consistency. These two algorithms represent extreme points on a spectrum of algorithms t

hat maintain various amounts of arc consistency during search. The conventional wisdom expressed to us by some members of the constraint programming community already runs counter to the second piece of CSP conventional wisdom. Our experiments suggest that the constraint programming community has been conventionally wiser in this regard than the CSP community. The combination of consistency pruning with backtrack search has a long history 5], 6], 7]. Various degrees of consistency processing interleaved with backtrack search were studied experimentally in 2], 8], 9]. A variety of algorithms were considered that alternate choosing a value for a variable with\looking ahead", via a constraint propagation process, to infer the consequences of that choice for pruning the values available for the as yet uninstantiated variables. The algorithms di ered in how much constraint propagation they performed, and thus in the degree of arc consistency they achieved. Forward checking is an algorithm which does a minimal amount of constraint propagation, in the sense that it performs the minimal amount of lookahead needed to avoid having to\look back", i.e. to avoid the need to check new choices against previous ones. In experimental studies forward checking repeatedly proved superior to algorithms interleaving more constraint propagation. Of course, the limitations of these experiments were recognized. However, the repeated success of forward checking began to bias the conventional wisdom in the CSP community in the direction of\less is more". For example, in a recent survey of CSP algorithms 10], the section on\How Much Constraint Propagation Is Useful?" concludes:\Experiments by other researchers in addition to Nadel] with a variety of problems also indicate that it is better to apply constraint propagation only in a limited form". In our laboratory several studies began to suggest that\more could be more". Gevecker studied full arc consistency maintenance 11] and Freuder and Wallace studied a range of hybrid algorithms based on a notion of\selective" or\bounded" constraint propagation 12]. However, these results were still limited in their understanding of the random problem space. Also, they did not employ the powerful search ordering scheme we alluded to above. We conduct here experiments on random problems, focusing on the\hard problem ridge" identi ed in recent studies of\really hard" random problems 13], 14]. Problems that contradict the conventional CSP wisdom appear to be pervasive, and orders of magnitude e ects are found. There are, of course, signi cant caveats to these experimental results. In particular, problems of di erent structure or size may behave di erently. We assume individual constraint checks can be e ciently computed. (Each time we ask if a value v for a variable X and a value u for a variable Y satisfy the constraint between X and Y we are performing a constraint check .) If this were not the case, maintaining full arc consi

stency could conceivably require some very expensive constraint check computation that backtracking or forward checking avoided.

上一页第3页

你可能喜欢

热门文档

相关文档

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