約束滿足問題的模型構造和相變現(xiàn)象.pdf_第1頁
已閱讀1頁,還剩81頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、約束滿足問題(Constraint Satisfaction Problem,簡稱CSP)由一個變量集合和一個約束集合組成,通過為一組變量賦值來滿足一組給定的約束.約束滿足問題在人工智能、計算機科學等眾多應用領域都具有十分重要的意義.隨機CSP模型是隨機CSP研究的基礎.一個好的隨機CSP模型,尤其是能產(chǎn)生難解實例的模型,對于我們研究CSP的性質和測試CSP算法的性能具有重要的作用.經(jīng)典的CSP模型存在平凡漸近無解性問題,為了克服這個缺

2、點,一些值域固定的模型在約束關系中加入特殊的組合結構,另一方面,一些學者開始研究值域可變的模型,如RB模型.
   在第二章中,受k增長的隨機k-SAT模型和RB模型的啟發(fā),我們提出了一個新的隨機CSP模型,稱為d-k-CSP模型.對于d-k-CSP模型,如果值域大小d和約束作用域的長度k滿足條件:對任意的正實數(shù)s有kind≥(1+s)1nn,則d-k-CSP模型存在精確相變現(xiàn)象.如果值域大小d是常數(shù),約束作用域的長度k隨變量個

3、數(shù)n的增加而呈對數(shù)增長,在這種情況下,d-k-CSP模型就是k-CSP模型;如果值域大小d=nα,約束作用域的長度k是常數(shù),在這種情況下,d-k-CSP模型就是RB模型.
   在第三章中,我們分析了d-k-CSP模型的歸結復雜性,在d≥nα的情況下,約束作用域的長度k固定,d-k-CSP模型的不可滿足實例對于樹型歸結證明有指數(shù)下界.對于d為常數(shù)和d=1nn這兩種情況我們給出了實驗結果,實驗結果顯示在這兩種情況下,d-k-CSP

4、模型會發(fā)生可滿足性相變現(xiàn)象,且在相變點附近的實例是難解的.在d為常數(shù)和d=1nn的情況下,當變量個數(shù)n充分大時,值域大小d和約束作用域的長度k并不是很大,因此d-k-CSP模型可以產(chǎn)生非平凡的具有小值域的隨機CSP實例,這對測試CSP算法是非常有用的.
   在第四章中,結合線性CSP模型和d-k-CSP模型的特點,我們提出了一個隨機線性CSP模型,k-hyper-F-lincar CSP模型,這個模型每個變量的值域都取相同的有

5、限域F,從向量空間Fk中隨機選取超平面作為約束關系,n是變量個數(shù),k是約束作用域的長度,這里k是關于,n的整值函數(shù).我們證明了k-hyper-F-linear CSP模型存在精確的可滿足性相變現(xiàn)象.與一些已有的線性CSP模型的結果相比,本文提供了一個基于一般討論上的新證明,給出了更一般的結果;同時,隨機產(chǎn)生的有限域上的n元線性方程組可看成k-hyper-F-linear CSP模型的特例.此外,討論了高斯消去法判斷隨機線性方程組是否有解

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論