【摘要】：約束滿足問(wèn)題(Constraint Satisfaction Problem,CSP)是人工智能領(lǐng)域的一個(gè)重要分支,也是當(dāng)前國(guó)際上人工智能領(lǐng)域研究的熱點(diǎn)。CSP可以模擬各種復(fù)雜的組合問(wèn)題,涵蓋人工智能、運(yùn)籌學(xué)、編程語(yǔ)言、數(shù)據(jù)庫(kù)等廣泛的技術(shù)。CSP現(xiàn)已成功應(yīng)用于資源分配,生產(chǎn)調(diào)度,產(chǎn)品配置,物流規(guī)劃,路由選擇,生物信息學(xué)等領(lǐng)域。解決約束滿足問(wèn)題(CSP)首先要進(jìn)行約束建模。建模過(guò)程是通過(guò)指定變量、論域和約束來(lái)完成的。然后再使用約束求解器進(jìn)行求解。約束求解器通常是啟發(fā)式引導(dǎo)回溯搜索和推理方法的組合,通過(guò)將值分配給滿足給定約束集的給定變量集來(lái)尋找解。回溯搜索算法是解決CSP問(wèn)題的主要搜索算法。在使用回溯搜索來(lái)解決CSP問(wèn)題時(shí),必須對(duì)哪個(gè)變量進(jìn)行分支或?qū)嵗约皩⒛膫�(gè)值賦予變量等問(wèn)題進(jìn)行一系列的決策,這些決策過(guò)程稱為變量和值排序。現(xiàn)有的研究已經(jīng)表明,對(duì)于許多問(wèn)題,變量和值排序的選擇可以極大地影響CSP實(shí)例的求解效率。本文對(duì)目前主流的變量和值排序的啟發(fā)式方法進(jìn)行了詳細(xì)的研究。在回溯搜索過(guò)程中應(yīng)用約束傳播(constraint propagation)是求解約束滿足問(wèn)題的最重要技術(shù)之一�；∠嗳菔羌s束傳播技術(shù)的核心,許多的約束傳播算法都是圍繞弧相容展開的�；∠嗳菔亲罨竞妥钪募s束傳播算法,它要求約束網(wǎng)絡(luò)的每個(gè)論域值都可以在約束中找到支持�，F(xiàn)在已經(jīng)提出了許多AC算法。在眾多AC算法中,粗粒度的AC-3算法由于其一般性和簡(jiǎn)便性已經(jīng)成為當(dāng)今用途最廣泛的弧相容算法。為了建立AC,AC-3算法保留了需要修正的元素列表,并對(duì)元素進(jìn)行連續(xù)修正。AC-3算法在AC過(guò)程中可以采用不同的傳播策略,它有三種經(jīng)典的變體,分別對(duì)應(yīng)的是面向弧的、面向變量的和面向約束的。對(duì)AC-3的三種經(jīng)典變體,有不同的revision啟發(fā)式算法,這些revision啟發(fā)式方法也是基于“失敗優(yōu)先原則(fail-first principle)”。在搜索期間應(yīng)用AC時(shí)對(duì)revision表進(jìn)行排序,可以顯著的提高AC-3算法的性能。本文對(duì)AC-3的三種經(jīng)典變體及應(yīng)用在它們上的revision啟發(fā)式算法進(jìn)行了分析和研究,并在此基礎(chǔ)上提出了一種新的面向變量的傳播策略,新的傳播策略也維持了一個(gè)變量列表,這個(gè)列表需要在建立AC時(shí)進(jìn)行修正。它將傳播過(guò)程分解為兩個(gè)獨(dú)立的階段。本文將展示它如何減少revision和列表操作的次數(shù)。在實(shí)驗(yàn)中,將revision啟發(fā)式應(yīng)用于這種新的面向變量的傳播策略,并將它與現(xiàn)有最有效的傳播策略進(jìn)行比較。來(lái)自各種結(jié)構(gòu)性和隨機(jī)問(wèn)題的結(jié)果表明,新提出的傳播策略減少了revision次數(shù)并加速了搜索過(guò)程。它加快了AC的執(zhí)行,優(yōu)于現(xiàn)有的傳播策略。
【圖文】：

圖 2.1 澳大利亞地圖著色圖著色示例可以由元組(X,D,C)定義，其中：NT, Q, SA, NSW, V, T 表示的是變量，代表地圖 green, blue}，表示每個(gè)變量的論域；NT, WA≠SA, NT≠SA, NT≠Q(mào), SA≠Q(mào), SA≠NSW 表示的是任意兩個(gè)相鄰地區(qū)之間的約束。的賦值為：{WA=red, NT=green, SA=blue, Q僅涉及一個(gè)變量（例如 x>5）的約束，二元約個(gè)變量。通常，非二元約束包括 n 個(gè)變量，，也 + x3 + x4 > 0 稱為四元約束）。一元 CSP 僅包含和二元約束。在一般情況下，非二元或者說(shuō) n的約束。地圖著色問(wèn)題是二元 CSP。

圖 2.2 將地圖著色問(wèn)題轉(zhuǎn)化為約束網(wǎng)絡(luò)量進(jìn)行的完整的賦值，要求這些賦值必CSP 是 NP-hard 問(wèn)題，那么就意味著在可能存在。其最壞情況下的時(shí)間復(fù)雜度算法算法通過(guò)為變量選擇值來(lái)構(gòu)建出部分解。所以，當(dāng)搜索樹訪問(wèn)到死節(jié)點(diǎn)時(shí)，就過(guò)程是系統(tǒng)式的，可以保證所有可能的和逐步測(cè)試所有候選解的方案上進(jìn)行的這個(gè)選擇是否滿足所有的約束條件，而
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 康晴晴;;兒童有聲讀物傳播策略研究——以“凱叔講故事”為例[J];傳播與版權(quán);2017年11期

2 郭嘉慧;;網(wǎng)絡(luò)自制節(jié)目《奇葩說(shuō)》的節(jié)目形態(tài)及傳播策略分析[J];電視指南;2017年05期

3 王爽;;電視養(yǎng)生節(jié)目的科學(xué)思想傳播策略[J];電視指南;2017年13期

4 鄒穎;;非物質(zhì)文化遺產(chǎn)整體性傳播策略[J];中國(guó)民族博覽;2017年02期

5 郁s

本文編號(hào)：2589825