發(fā)布時間：2018-05-19 11:26

  本文選題：約束滿足問題 + 單值弧相容��； 參考：《吉林大學(xué)》2017年碩士論文

【摘要】：約束滿足問題是人工智能領(lǐng)域的重要方面,目的是為組合問題找到一個(組)解,這個過程稱作約束求解。探索高效的求解算法是當(dāng)前研究的主要課題。目前最為流行的求解算法是回溯搜索算法,在回溯搜索的過程中使用相容性進行縮減搜索空間是最高效的完備求解算法之一。相容性技術(shù)一直是約束求解領(lǐng)域的核心問題。常見的相容性技術(shù)有:弧相容(Arc Consistency,AC),路徑相容(Path Consistency,PC),最大限定路徑相容(max-Restricted Path Consistency,max RPC)和單值弧相容(Singleton Arc Consistency,SAC)等,不同的相容性其刪值能力各有不同。回溯搜索的過程不斷進行著變量的實例化,挑選變量和值的標(biāo)準(zhǔn)稱為啟發(fā)式,研究表明,變量排序啟發(fā)式和值排序啟發(fā)式對于約束求解效率有著重大影響。常見的變量啟發(fā)式有dom啟發(fā)式、dom/deg啟發(fā)式、dom/wdeg啟發(fā)式等。由于處理器條件的限制,摩爾定律被放棄,諸多硬件廠商相繼放棄了單核方案轉(zhuǎn)而推出多核心及GPU等更高效的計算設(shè)備,這促進了并行程序的發(fā)展。GPU做為一種高效的處理器已被廣泛使用于高性能計算之中,其應(yīng)用范圍包括圖形圖像、科學(xué)研究、工業(yè)設(shè)計等領(lǐng)域。當(dāng)前很多經(jīng)典串行算法,都可以經(jīng)由并行化取得很大的效能提升。本文基于GPU及一些基本并行算法將現(xiàn)有的算法進行優(yōu)化,具體工作如下:1.提出一種約束網(wǎng)絡(luò)(constraint network)在GPU上表示的模型——N-E模型。2.提出在N-E模型上基于GPU的細粒度弧相容算法AC4GPU及其改進算法AC4GPU+。3.提出以并行的方式對約束進行檢查的AC框架ACGPU,該框架可能擴展多種約束檢查方法,本文給出一種基于二元表示的檢查方法。4.提出基于GPU的單值弧相容算法SACGPU+bit,該算法將ACGPU算法作為底層算法并以二元表示作為底層數(shù)據(jù)結(jié)構(gòu)。實驗結(jié)果說明AC4GPU及AC4GPU+對比原算法在一些規(guī)模較小的問題上取得了10%~50%的加速,在一些規(guī)模較大的問題上則加速1~2個數(shù)量級。SACGPU+bit的算法效率也普遍優(yōu)于當(dāng)前主流SAC算法。最后本文對采用GPU加速CSP問題這個課題進行了展望,總結(jié)多個國內(nèi)外的研究方向。
[Abstract]:Constraint satisfaction problem (CSP) is an important aspect of artificial intelligence, which aims to find a solution for combinatorial problem, which is called constraint solution. Exploring efficient algorithms is the main research topic. At present, the most popular algorithm is the backtracking search algorithm. It is one of the most efficient and complete algorithms to reduce the search space by using compatibility in the process of backtracking search. Compatibility technology has always been the core problem in the field of constraint solving. The common compatibility techniques are: Arc compatibility, path compatibility, max-Restricted Path contiguity max RPCs and single value arc compatible Singleton Arc consistencyssac, etc. Their erasure ability varies with each other. In the process of backtracking search variables are instantiated and the criteria for selecting variables and values are called heuristics. The research shows that the heuristics of variable ordering and value sorting have great influence on the efficiency of constraint solving. Common variable heuristics include dom heuristics / dom-deg heuristics and dom-wdeg heuristics. Due to processor constraints, Moore's Law has been abandoned, and many hardware manufacturers have abandoned single-core solutions and introduced more efficient computing devices such as multi-cores and GPU. This has promoted the development of parallel programs. GPU as an efficient processor has been widely used in high-performance computing. Its applications include graphics and images, scientific research, industrial design and other fields. At present, many classical serial algorithms can achieve great performance improvement by parallelization. This paper optimizes the existing algorithms based on GPU and some basic parallel algorithms. The specific work is as follows: 1. A constrained network constraint network model, N-E model. 2. 2, which is represented on GPU, is presented in this paper. A fine-grained arc compatibility algorithm (AC4GPU) based on GPU and its improved algorithm AC4GPU. 3 on N-E model are proposed. An AC framework, ACGPU, which checks constraints in a parallel manner, is proposed, which may extend a variety of constraint checking methods. In this paper, a binary representation based checking method .4. A single value arc compatible algorithm based on GPU, SACGPU bit. is proposed, which takes the ACGPU algorithm as the underlying algorithm and binary representation as the underlying data structure. The experimental results show that the AC4GPU and AC4GPU comparison algorithms have achieved 1050% acceleration on some small scale problems, and the algorithm efficiency of 1 ~ 2 orders of magnitude. SACGPU bit is generally superior to the current mainstream SAC algorithm. Finally, this paper looks forward to the problem of accelerating CSP with GPU, and summarizes many research directions at home and abroad.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【相似文獻】

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

1 王秦輝;陳恩紅;王煦法;;分布式約束滿足問題研究及其進展[J];軟件學(xué)報;2006年10期

2 郭冬芬;李鐵克;;基于約束滿足的煉鋼批量計劃的制定方法[J];微計算機信息;2007年12期

3 湯萍萍;王紅兵;;基于層次約束滿足的產(chǎn)品選擇算法[J];現(xiàn)代計算機(專業(yè)版);2007年08期

4 谷學(xué)強;陳t，

本文編號：1909916