Constraint Processing
Constraint Processing
复制标题
DOI：
10.4018/978-1-59904-849-9.ch062
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Barták
中科院分区：
文献类型：
--
作者：
R. Barták
引言约束出现在人类努力的许多领域，从填字游戏（单词只能在同一个字母上重叠）和最近流行的数独（没有数字连续出现两次）等谜题到规划会议（会议室必须容纳所有参与者）等日常问题，直到解决制造调度中的硬优化问题（一项工作必须在另一项工作之前完成）。尽管所有这些问题看起来都来自完全不同的世界，但它们都有一个相似的基础——任务是在尊重给定约束的情况下找到决策变量的值，例如工作的开始时间或董事会中数字的位置。该问题称为约束满足问题（CSP）。约束处理在 20 世纪 70 年代的人工智能研究中出现（Montanary，1974），当时研究了场景标记等问题（Waltz，1975）。场景标记的目标是识别 3D 场景的 2D 图片中的一种线条（然后是一种对象）。可能的类型是凸线、凹线和遮挡线，并且类型的组合被限制在线的交汇处以在物理上可行。这个场景标记问题可能是第一个形式化为 CSP 的问题，并且为解决这个问题而开发的一些技术，即弧一致性，仍然是约束处理的核心。编程系统中约束的系统使用始于 20 世纪 80 年代，当时研究人员发现逻辑编程的统一和约束满足之间的相似性（Gallaire，1985）（Jaffar & Lassez，1987）。约束逻辑编程诞生了。如今，约束编程是一个独立于底层编程语言的独立主题，尽管由于约束自然集成到逻辑编程框架中，约束逻辑编程仍然发挥着重要作用。本文介绍了解决约束满足问题的主流技术。这些技术落后于现有的约束求解器，理解它们对于充分利用可用技术非常重要。
INTRODUCTION Constraints appear in many areas of human endeavour starting from puzzles like crosswords (the words can only overlap at the same letter) and recently popular Sudoku (no number appears twice in a row) through everyday problems such as planning a meeting (the meeting room must accommodate all participants) till solving hard optimization problems for example in manufacturing scheduling (a job must finish before another job). Though all these problems look like being from completely different worlds, they all share a similar base – the task is to find values of decision variables, such as the start time of the job or the position of the number at a board, respecting given constraints. This problem is called a Constraint Satisfaction Problem (CSP). Constraint processing emerged from AI research in 1970s (Montanary, 1974) when problems such as scene labelling were studied (Waltz, 1975). The goal of scene labelling was to recognize a type of line (and then a type of object) in the 2D picture of a 3D scene. The possible types were convex, concave, and occlud-ing lines and the combination of types was restricted at junctions of lines to be physically feasible. This scene labelling problem is probably the first problem formalised as a CSP and some techniques developed for solving this problem, namely arc consistency, are still in the core of constraint processing. Systematic use of constraints in programming systems has started in 1980s when researchers identified a similarity between unification in logic programming and constraint satisfaction (Gallaire, 1985) (Jaffar & Lassez, 1987). Constraint Logic Programming was born. Today Constraint Programming is a separate subject independent of the underlying programming language, though constraint logic programming still plays a prominent role thanks to natural integration of constraints into a logic programming framework. This article presents mainstream techniques for solving constraint satisfaction problems. These techniques stay behind the existing constraint solvers and their understanding is important to exploit fully the available technology.