約束滿足問題的模型構(gòu)造和相變現(xiàn)象.pdf

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

2、點,一些值域固定的模型在約束關(guān)系中加入特殊的組合結(jié)構(gòu),另一方面,一些學(xué)者開始研究值域可變的模型,如RB模型.
　　 在第二章中,受k增長的隨機(jī)k-SAT模型和RB模型的啟發(fā),我們提出了一個新的隨機(jī)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模型的歸結(jié)復(fù)雜性,在d≥nα的情況下,約束作用域的長度k固定,d-k-CSP模型的不可滿足實例對于樹型歸結(jié)證明有指數(shù)下界.對于d為常數(shù)和d=1nn這兩種情況我們給出了實驗結(jié)果,實驗結(jié)果顯示在這兩種情況下,d-k-CSP

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

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