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

【摘要】：約束滿足問(wèn)題是人工智能領(lǐng)域的重要方面,目的是為組合問(wèn)題找到一個(gè)(組)解,這個(gè)過(guò)程稱作約束求解。探索高效的求解算法是當(dāng)前研究的主要課題。目前最為流行的求解算法是回溯搜索算法,在回溯搜索的過(guò)程中使用相容性進(jìn)行縮減搜索空間是最高效的完備求解算法之一。相容性技術(shù)一直是約束求解領(lǐng)域的核心問(wèn)題。常見(jiàn)的相容性技術(shù)有:弧相容(Arc Consistency,AC),路徑相容(Path Consistency,PC),最大限定路徑相容(max-Restricted Path Consistency,max RPC)和單值弧相容(Singleton Arc Consistency,SAC)等,不同的相容性其刪值能力各有不同�；厮菟阉鞯倪^(guò)程不斷進(jìn)行著變量的實(shí)例化,挑選變量和值的標(biāo)準(zhǔn)稱為啟發(fā)式,研究表明,變量排序啟發(fā)式和值排序啟發(fā)式對(duì)于約束求解效率有著重大影響。常見(jiàn)的變量啟發(fā)式有dom啟發(fā)式、dom/deg啟發(fā)式、dom/wdeg啟發(fā)式等。由于處理器條件的限制,摩爾定律被放棄,諸多硬件廠商相繼放棄了單核方案轉(zhuǎn)而推出多核心及GPU等更高效的計(jì)算設(shè)備,這促進(jìn)了并行程序的發(fā)展。GPU做為一種高效的處理器已被廣泛使用于高性能計(jì)算之中,其應(yīng)用范圍包括圖形圖像、科學(xué)研究、工業(yè)設(shè)計(jì)等領(lǐng)域。當(dāng)前很多經(jīng)典串行算法,都可以經(jīng)由并行化取得很大的效能提升。本文基于GPU及一些基本并行算法將現(xiàn)有的算法進(jìn)行優(yōu)化,具體工作如下:1.提出一種約束網(wǎng)絡(luò)(constraint network)在GPU上表示的模型——N-E模型。2.提出在N-E模型上基于GPU的細(xì)粒度弧相容算法AC4GPU及其改進(jìn)算法AC4GPU+。3.提出以并行的方式對(duì)約束進(jìn)行檢查的AC框架ACGPU,該框架可能擴(kuò)展多種約束檢查方法,本文給出一種基于二元表示的檢查方法。4.提出基于GPU的單值弧相容算法SACGPU+bit,該算法將ACGPU算法作為底層算法并以二元表示作為底層數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果說(shuō)明AC4GPU及AC4GPU+對(duì)比原算法在一些規(guī)模較小的問(wèn)題上取得了10%~50%的加速,在一些規(guī)模較大的問(wèn)題上則加速1~2個(gè)數(shù)量級(jí)。SACGPU+bit的算法效率也普遍優(yōu)于當(dāng)前主流SAC算法。最后本文對(duì)采用GPU加速CSP問(wèn)題這個(gè)課題進(jìn)行了展望,總結(jié)多個(gè)國(guó)內(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【相似文獻(xiàn)】

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

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

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

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

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

本文編號(hào)：1909916