本文關(guān)鍵詞：基于RDS技術(shù)的加權(quán)約束滿足問題的符號算法研究　出處：《桂林電子科技大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 加權(quán)約束滿足問題 RDS(Russian Doll Search) 桶消元算法 結(jié)構(gòu)化記錄 代數(shù)決策圖

【摘要】：計算機科學(xué)和人工智能領(lǐng)域中的許多問題都可以形式化為加權(quán)約束滿足問題(WCSP),如地圖著色、生產(chǎn)調(diào)度、產(chǎn)品配置、路由選擇、物流規(guī)劃、資源分配等問題。WCSP的求解目標(biāo)是尋找一個使得違反約束總代價值最小的完全賦值。WCSP最基本的求解方法是深度優(yōu)先分支定界(DFBB)算法,Russian Doll Search(RDS)算法是通過修改DFBB算法框架得到的,其能有效提高搜索中的上下界,但RDS算法的求解效率取決于分解后得到的各個子問題的求解效率。結(jié)構(gòu)化記錄是避免重復(fù)搜索的有效技術(shù)之一,通過存儲已求解信息,在搜索過程中判斷是否可以重用已存儲的求解信息,從而提高求解效率。由于在RDS算法求解中,一次只能處理一個約束值對,不能同時處理多個約束值對,而代數(shù)決策圖(ADD)能高效的表示和以集合方式處理數(shù)據(jù),且能減緩因問題規(guī)模過大造成的組合狀態(tài)爆炸問題。因此本文對加權(quán)約束滿足問題的RDS符號求解算法做了相關(guān)研究,主要工作包括:(1)給出改進RDS符號ADD求解算法。基于RDS算法思想,將DFBB算法中的一次搜索用m個子問題的相繼搜索來替代。通過改進最多約束變量(MCV)的變量選擇法,引入RDS變量來引導(dǎo)原問題的子問題分解,進而減少RDS算法中分解的子問題個數(shù)。為提高各個子問題的求解效率,用桶消元算法求解非RDS變量,減少DFBB算法處理的變量個數(shù)。為了進一步提高算法的效率,借助WCSP的符號ADD表示,給出WCSP的改進RDS符號ADD求解算法。(2)給出混合RDS符號ADD求解算法。通過研究RDS變量之間的約束關(guān)系,給出RDSV-T子問題分解方法;在子問題求解中,基于子問題之間的結(jié)構(gòu)關(guān)系,存儲當(dāng)前子問題的結(jié)構(gòu)化記錄,便于在后續(xù)子問題求解中重用此結(jié)構(gòu)化記錄。借助WCSP的符號ADD表示,給出WCSP的混合RDS符號求解算法。(3)以隨機生成的WCSP問題作為測試用例,結(jié)果表明,本文給出的符號算法優(yōu)于RDS算法、EDAC-FC-DFBB算法和DFBB-ADD算法。
[Abstract]:Many problems in the field of computer science and artificial intelligence can be formalized as a weighted constraint satisfaction problem (WCSP), such as map coloring, production scheduling, product configuration, route selection, logistics planning, solving.WCSP resource allocation problem is to find a violation of the constraint of minimum total cost value assignment completely.WCSP the basic method is a depth first branch and bound algorithm (DFBB), Russian Doll Search (RDS) algorithm is obtained by modifying the DFBB algorithm framework, which can effectively improve the upper and lower bounds of the search, but the efficiency of solving solution obtained after the decomposition efficiency is determined for each sub problem. RDS algorithm is one of the structured record effective technology to avoid repeated search, through storage solution has been in the process of searching information, whether can solve information reuse has been stored, so as to improve the efficiency of the algorithm. By solving the RDS algorithm That one can only handle a constraint on, cannot simultaneously handle multiple constraints on the values, and the algebraic decision diagram (ADD) can efficiently represent and to set data, and the combination of the state explosion problem slowed because of excessive size. So this paper RDS algorithm for solving constraint satisfaction problems symbol the weight was studied. The main work includes: (1) an improved RDS symbol ADD algorithm. RDS algorithm based on the idea of a search in the DFBB algorithm with successive search m sub problems instead. By improving the most constrained variable (MCV) method to select variables, sub problem decomposition into RDS to guide the variables of the original problem, and then reduce the number of decomposition of the sub problem of the RDS algorithm. In order to improve the efficiency of solution of each sub problem, eliminating non RDS variable element calculation with the bucket, reduce the number of variables in DFBB algorithm. In order to further improve the algorithm The efficiency of ADD WCSP with symbolic representation, improved RDS symbol ADD algorithm for solving WCSP. (2) are mixed RDS symbolic ADD algorithm. Through the constraint relationship between RDS variables, given the RDSV-T sub problem decomposition method; in sub problems, the relationship between the structure of sub problems based on a structured record the current storage sub problem, easy to reuse in solving sub problems in the subsequent structured records. By means of symbol ADD WCSP said the hybrid algorithm for solving RDS symbol WCSP. (3) the WCSP problem is randomly generated as a test case, the results show that the symbolic algorithm outperforms the RDS algorithm presented in this paper, EDAC-FC-DFBB algorithm and DFBB-ADD algorithm.

【學(xué)位授予單位】：桂林電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP301.6

【參考文獻】

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

1 呂宗偉,林爭輝,張鐳;OBDD在組合邏輯電路測試中的應(yīng)用研究[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2001年06期

，

本文編號：1409584