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

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

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