Loading AI tools
来自维基百科,自由的百科全书
在數學中,約束(英語: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]簡化約束滿足問題的建模,擴展了約束語言的表示範圍、也可以促進約束編程。將所有變數一起考慮,可以在求解過程比較早發現一些不可行的情形。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.