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

【文章來(lái)源】：吉林大學(xué)吉林省 211工程院校 985工程院校 教育部直屬院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

四皇后問(wèn)題約束滿足問(wèn)題模型

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

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

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

碩士論文
[1]約束滿足問(wèn)題（CSP）的求解技術(shù)研究[D]. 郭勁松.吉林大學(xué) 2013



本文編號(hào)：3458616