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

Contradicting Conventional Wisdom in Constraint Satisfaction Daniel Sabin and Eugene C. Freuder Department of Computer Science, University of New Hampshire, Durham NH 03824, USA

Abstract. Constraint satisfaction problems have wide application in

arti cial intelligence. They involve nding values for problem variables where the values must be consistent in that they satisfy restrictions on which combinations of values are allowed. Two standard techniques used in solving such problems are backtrack search and consistency inference. Conventional wisdom in the constraint satisfaction community suggests: 1) using consistency inference as preprocessing before search to prune values from consideration reduces subsequent search e ort and 2) using consistency inference during search to prune values from consideration is best done at the limited level embodied in the forward checking algorithm. We present evidence contradicting both pieces of conventional wisdom, and suggesting renewed consideration of an approach which fully maintains arc consistency during backtrack search.

1 Introduction ables subject to constraints that are restrictions on which combinations of values are allowed 1]. They have many applications in arti cial intelligence. (We restrict our attention here to binary CSPs, where the constraints involve two variables.) The basic solution method is backtrack search. Often consistency inference (constraint propagation) techniques are used to prune values before or during search. The basic pruning technique involves establishing or restoring some form of arc consistency. If a value v for a variable V is not consistent with any value for some other variable U, then v is arc inconsistent and can be removed. Full arc consistency is achieved when all arc inconsistent values are removed. One of the most successful forms of backtrack search has proven to be forward checking 2]. Forward checking combines backtrack search with a limited form of arc consistency maintenance. Some values are removed that become inconsistent when the problem is modi ed by the choices made during the search process. This paper provides strong experimental evidence contradicting two wellestablished pieces of conventional wisdom in the CSP community: Constraint satisfaction problems (CSPs ) involve nding values for problem vari-

{ Conventional CSP wisdom says that using consistency inference in a preprocessing step, to prune values before search, will reduce the subsequent search e ort. There has been some question as to the degree of consistency

第1页

你可能喜欢

热门文档

相关文档

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