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

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

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

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

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