約束滿(mǎn)足問(wèn)題算法研究及其應(yīng)用.pdf

1、約束滿(mǎn)足問(wèn)題是人工智能領(lǐng)域的一個(gè)重要問(wèn)題，近三十年來(lái)有關(guān)約束滿(mǎn)足問(wèn)題的研究方興未艾,己有的絕大多數(shù)關(guān)子約束滿(mǎn)足問(wèn)題的研究成果都是基于經(jīng)典約束滿(mǎn)足問(wèn)題定義的，是從變量的集合出發(fā)，針對(duì)變量之間的制約關(guān)系來(lái)研究如何得到滿(mǎn)足約束條件的變量的取值本文從變量取值出發(fā)，針對(duì)具有解析約束形式、同一變量多賦值的約柬滿(mǎn)足問(wèn)題，提出了一種新的約束滿(mǎn)足問(wèn)題定義。本文通過(guò)一種特殊約束滿(mǎn)足問(wèn)題的研究提出一套建立在這個(gè)定義基礎(chǔ)之上的概念和三種算法：整數(shù)規(guī)劃法、不等式

2、組法和直接求解不定方程法，詳細(xì)研究了其中的第三種算法，并給出了最壞情況下的時(shí)間復(fù)雜度，從而能夠比較清晰的描述一類(lèi)約束滿(mǎn)足問(wèn)題的一般分析過(guò)程，揭示了約束滿(mǎn)足問(wèn)題同經(jīng)典的整數(shù)規(guī)劃、數(shù)論和整數(shù)環(huán)論的聯(lián)系、這三種算法都屬于精確算法，得到的解是精確解．此外，基于實(shí)際問(wèn)題的需要，本文還提出了用于求解約束滿(mǎn)足問(wèn)題的一類(lèi)近似算法；開(kāi)放一封閉算法及其改進(jìn)算法。本文的后半部分介紹了約束滿(mǎn)足問(wèn)題在自動(dòng)化組卷題庫(kù)系統(tǒng)中的一個(gè)具體應(yīng)用。這部分基本按照結(jié)構(gòu)化軟件開(kāi)