约束 (数学)
在数学中，约束（英语：Constraint）是一个优化问题的解需要符合的条件。约束可分为等式约束及不等式约束。符合所有约束的解的集合称为可行集（feasible set）或是候选解（candidate solution）。
范例
[编辑]以下是一个优化的问题：
其拘束条件为
and
其中 表示向量 (x1, x2)。
上例中，第一行定义要优化的函数（称为目标或费用函数），第二、三行定义二个约束条件，一个是不等式约束，另一个是等式约束，这二个约束定义了候选解的范围。
若没有约束条件，优化的解为，因此处的有最小值，但这个值不符合约束条件。考虑约束条件的优化问题，其解为，是符合所有约束条件的解当中，使函数有最小值的解。
术语
[编辑]- 若一约束条件在特定点时为一等式，称为束缚约束，因为此点无法在约束的方向自由移动，就算往该方方向可能会让目标函数有更好的结束，也无法移动。
- 若一约束条件在特定点时为一不等式，称为非束缚约束，因为此点仍可以在约束的方向自由移动（不过有可能是因为移动后对目标函数没有好的影响，因此不移动）。
- 若在特定点下，约束条件中有至少一个无法满足，此点就称为不可行。
硬约束以及软约束
[编辑]若问题中有要求所有的约束都要符合，这称为“硬约束”（hard constraints），上述所提的都是硬约束。另外有一种约束问题，称为flexible constraint satisfaction problems。有些约束希望可以满足，但不强制。这类非强制的约束称为软约束，例如preference-based planning。在MAX-CSP的约束满足问题问题中，可以允许违反一定数量的约束，会依满足约束的数量来评估解的品质。
全域约束
[编辑]全域约束（Global constraints）[1]是将所有变数一起考虑的约束。像其中一个全域约束是alldifferent，可以用较简单的语言写成一连串原子约束的组合：n个变数的alldifferent约束，若将所有变数二二比较，都不相等，约束即成立。在语意上等价于以下许多不等式的交集：。也有其他的全域约束，全域约束的出现扩展了约束架构可以可表达的范围。在这些例子中，全域约束常会对应一种特殊组合问题的结构。例如确定有限状态自动机可以接受Regular（正则约束）的约束。
全域约束有用在[2]简化约束满足问题的建模，扩展了约束语言的表示范围、也可以促进约束编程。将所有变数一起考虑，可以在求解过程比较早发现一些不可行的情形。
相关条目
[编辑]外部链接
[编辑]- ^ Rossi, Francesca; Van Beek, Peter; Walsh, Toby. 7. Handbook of constraint programming 1st. Amsterdam: Elsevier. 2006. ISBN 9780080463643. OCLC 162587579.
- ^ Rossi, Francesca. Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings. Berlin: Springer-Verlag Berlin Heidelberg. 2003. ISBN 9783540451938. OCLC 771185146.