約束問題求解

《約束問題求解》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第33卷第2期自動化學報Vol.33,No.22007年2月ACTAAUTOMATICASINICAFebruary,2007約束問題求解季曉慧1張健1摘要約束問題的求解涉及到人工智能、運籌學、計算機科學等領(lǐng)域.它的應用范圍也極為廣泛，包括計算機科學、控制科學、生物學等方面.本文對其發(fā)展歷史、所要求解的問題以及它的基本方法等問題進行了綜述.關(guān)鍵詞約束求解，優(yōu)化問題中圖分類號TP301.6ConstraintProcessingJIXiao-Hui1ZHANGJian1AbstractConstraintprocessinginvol

2、vesthetechniquesofartiˉcialintelligence,operationsresearch,computerscienceandsoon.Ithasfoundmanyapplicationsincomputerscience,controltheory,biologyandsoon.Thispaperisasurveyofitshistory,methodsandtheproblemsitencounters.KeywordsConstraintprocessing,optimization1約束問題求解的

3、發(fā)展開始出現(xiàn)[3].現(xiàn)在用于求解約束問題的工具大多都是基于約束邏輯程序框架的[3].但這并不意味著約束問題的求解研究始于上個世紀70年約束求解僅限于此框架，約束問題也可以在類似于代的SceneLabeling以及60年代的InteractiveC++，Java的命令式語言框架下進行求解[3].在此Graphics[1?3].SceneLabeling試圖用二維的線條之后，隨著約束求解技術(shù)的不斷發(fā)展，求解混合約描繪三維的物體，它的成果在于產(chǎn)生了各種一致束問題的研究也開始發(fā)展起來.(Consistent)算法[1,3].Interact

4、iveGraphics[4?6]的目的是允許用戶在計算機的顯示屏上繪制和處2約束問題理各種幾何圖形，它發(fā)展了約束求解技術(shù)中的局部推演(Localpropagation)及約束編譯(Constraint形式化地講，約束問題由以下三個基本元素組compiling)技術(shù)[3,6].約束求解的早期工作還包括成：變量V，變量的域D以及約束C.變量的域DMIT的電路分析與綜合[7]，這些工作開創(chuàng)了設計能是變量可能取值的集合，變量Vi只能在它的域Di夠求解通用約束問題的語言的研究[3,7].中進行取值；約束C描述了變量V之間必須滿足的約束求解的重

5、要進展在于Gallaire[8]及關(guān)系.求解約束問題就是在各變量的域D中找到一Ja?ar[9]分別在1985年及1987年發(fā)現(xiàn)，邏輯程序設[1]個(或所有的)值S使得各變量之間滿足約束C.計(Logicprogramming)實質(zhì)上是一種特殊的約束約束問題也可以表示為三元組[2].求解問題[1?3].首先，邏輯程序設計語言的描述式根據(jù)約束問題中變量的域D的不同，約束問題(Declarative)特性與約束求解的描述問題而不是可以分為：布爾約束問題、有限約束問題、數(shù)值約束解決問題"的思想很接近；其次，二者所

6、使用的求解問題及混合約束問題等.問題的回溯法也十分的接近.更重要的是，邏輯程序2.1布爾約束問題設計中的等式項實質(zhì)上是一種特殊的約束，而用于布爾約束問題要求V中的各變量只能在0或求解等式項的消解法也只是一種特殊的約束求解方1上取值，即布爾約束問題的域D為f0，1g.它的法.基于這種發(fā)現(xiàn)，約束邏輯程序設計(Constraint約束C實際上就是一組命題邏輯公式.所謂命題邏logicprogramming)[9]作為求解約束問題的新框架輯公式是布爾變量與邏輯連接符按照如下的規(guī)則形收稿日期2005-4-18收修改稿日期2006-6-9成的組

7、合體[10]：1)布爾變量是公式；2)如果'是ReceivedApril18,2005;inrevisedformJune9,2006國家自然科學基金(60125207,60421001)資助公式，則:'也是公式；3)如果á和'是公式，則SupportedbyNationalNaturalScienceFoundationofá¤'也是公式；4)只有上面三條規(guī)則生成的表達式P.R.China(60125207,60421001)1.中國科學院軟件研究所計算機科學國家重點實驗室北京100080是公式.這里:是一元連接符非"，¤可以是

8、任何1.StateKeyLaboratoryofComputerScience,Instituteof一個二元連接符，如^(與)、_(或)、!(蘊含)等.Software,ChineseAcademyofSciences,Beijin