約束滿足問題是人工智能領域重要的研究方向之一,主要用于求解實際問題和學術問題。約束滿足問題技術解決問題的主要思想是:首先將待求解問題抽象成一個約束網(wǎng)絡模型,然后利用約束滿足問題相關求解算法對得到的約束網(wǎng)絡模型進行求解。目前求解約束滿足問題的算法主要包括:回溯搜索算法、局部推理算法以及啟發(fā)式算法等�；诨厮菟阉鞯腗AC算法是目前求解約束滿足問題使用最廣泛的搜索算法,其算法思想是采用回溯搜索策略,在選擇變量進行實例化后,利用相容性算法對約束網(wǎng)絡進行約束傳播,刪除變量論域中不滿足相容性條件的值,從而壓縮約束網(wǎng)絡,減小搜索空間,簡化求解過程。在使用MAC算法求解規(guī)模較大的約束滿足問題時,不合理的變量實例化順序,常常會導致搜索樹的體積過于龐大,嚴重影響求解效率。然而在回溯搜索過程中,由于約束網(wǎng)絡的狀態(tài)經(jīng)常發(fā)生改變,因此尋找一個最優(yōu)的變量實例化順序的難度非常大。為了解決這一問題,學者們提出了啟發(fā)式的概念。在對變量進行實例化之前,使用啟發(fā)式算法進行變量和值的選擇,盡可能地縮減搜索樹的規(guī)模。變量排序啟發(fā)式算法的作用是根據(jù)啟發(fā)式規(guī)則指導回溯搜索算法選擇變量進行實例化,避免冗余搜索,提高求解效率。變量排序... 

【文章來源】：吉林大學吉林省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：47 頁

【學位級別】：碩士

【部分圖文】：

四皇后問題約束滿足問題模型

foreach value a dom(x) doif seekSupport(c x a) thenremove a from dom(x)return nbElements |dom(x)|圖 2.2 描述的是 4 皇后問題在實例化變量 w 后的約束網(wǎng)絡圖。圖中，Q 表應的取值，X 表示從論域中刪除掉的值。在未經(jīng)過 GAC 算法過濾的左網(wǎng)絡中共還有 12 個值，即在搜索樹的下一層還有 12 條分支。而在經(jīng)過過濾的右圖中，剩余三個變量論域中的 10 個值，由于不滿足 GAC 被刪索樹的下一層僅有 2 條分支，搜索空間被極大地壓縮了。并且由于 dom全部被刪除，可以直接判定 w 1 不是任何解的一部分，無需繼續(xù)向下進因此，在回溯搜索算法中加入相容性技術，能夠有效地過濾掉不存在于解分支，壓縮搜索空間，提高求解效率。

三個部分：分支策略、傳播算法以及回溯機制。其中，分支策略決進行實例化；傳播算法用于過濾約束網(wǎng)絡，壓縮搜索空間；回溯機量實例化失敗或約束傳播失敗后，搜索樹應該如何回退的問題。算法是目前求解約束滿足問題使用最廣泛、最有效的回溯搜索算法二路分支策略，即搜索樹中的每一個結點最多只有兩個孩子結點， x a，如圖 2.3 所示。在圖 2.3 中，在搜索初始時，為變量 x 賦值 結點的左子樹 x a。此時變量 x 實例化成功，繼續(xù)選擇變量 y 賦值左子樹 y a。當在 y a 的子樹上不能求出解時，搜索樹回退到 x (y)中的值 a 刪除，進入分支 x a 的右子樹 y a，重新選擇變量進執(zhí)行上述過程直到搜索過程結束。MAC 算法中的回溯機制是按序回溯的策略（SBT），沿著搜索路徑從下往上依次進行回溯。此出了 CBJ 和 DBT 等回溯機制。

【參考文獻】：
期刊論文
[1]基于實例化次數(shù)的約束求解方法研究[J]. 李占山,張乾,張良.  計算機研究與發(fā)展. 2015(05)

碩士論文
[1]約束滿足問題（CSP）的求解技術研究[D]. 郭勁松.吉林大學 2013



本文編號：3458616