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

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

【摘要】：計(jì)算機(jī)科學(xué)和人工智能領(lǐng)域中的許多問(wèn)題都可以形式化為加權(quán)約束滿足問(wèn)題(WCSP),如地圖著色、生產(chǎn)調(diào)度、產(chǎn)品配置、路由選擇、物流規(guī)劃、資源分配等問(wèn)題。WCSP的求解目標(biāo)是尋找一個(gè)使得違反約束總代價(jià)值最小的完全賦值。WCSP最基本的求解方法是深度優(yōu)先分支定界(DFBB)算法,Russian Doll Search(RDS)算法是通過(guò)修改DFBB算法框架得到的,其能有效提高搜索中的上下界,但RDS算法的求解效率取決于分解后得到的各個(gè)子問(wèn)題的求解效率。結(jié)構(gòu)化記錄是避免重復(fù)搜索的有效技術(shù)之一,通過(guò)存儲(chǔ)已求解信息,在搜索過(guò)程中判斷是否可以重用已存儲(chǔ)的求解信息,從而提高求解效率。由于在RDS算法求解中,一次只能處理一個(gè)約束值對(duì),不能同時(shí)處理多個(gè)約束值對(duì),而代數(shù)決策圖(ADD)能高效的表示和以集合方式處理數(shù)據(jù),且能減緩因問(wèn)題規(guī)模過(guò)大造成的組合狀態(tài)爆炸問(wèn)題。因此本文對(duì)加權(quán)約束滿足問(wèn)題的RDS符號(hào)求解算法做了相關(guān)研究,主要工作包括:(1)給出改進(jìn)RDS符號(hào)ADD求解算法�；赗DS算法思想,將DFBB算法中的一次搜索用m個(gè)子問(wèn)題的相繼搜索來(lái)替代。通過(guò)改進(jìn)最多約束變量(MCV)的變量選擇法,引入RDS變量來(lái)引導(dǎo)原問(wèn)題的子問(wèn)題分解,進(jìn)而減少RDS算法中分解的子問(wèn)題個(gè)數(shù)。為提高各個(gè)子問(wèn)題的求解效率,用桶消元算法求解非RDS變量,減少DFBB算法處理的變量個(gè)數(shù)。為了進(jìn)一步提高算法的效率,借助WCSP的符號(hào)ADD表示,給出WCSP的改進(jìn)RDS符號(hào)ADD求解算法。(2)給出混合RDS符號(hào)ADD求解算法。通過(guò)研究RDS變量之間的約束關(guān)系,給出RDSV-T子問(wèn)題分解方法;在子問(wèn)題求解中,基于子問(wèn)題之間的結(jié)構(gòu)關(guān)系,存儲(chǔ)當(dāng)前子問(wèn)題的結(jié)構(gòu)化記錄,便于在后續(xù)子問(wèn)題求解中重用此結(jié)構(gòu)化記錄。借助WCSP的符號(hào)ADD表示,給出WCSP的混合RDS符號(hào)求解算法。(3)以隨機(jī)生成的WCSP問(wèn)題作為測(cè)試用例,結(jié)果表明,本文給出的符號(hào)算法優(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

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

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

，

本文編號(hào)：1409584