表約束是一種外延的知識(shí)表示方法,每個(gè)約束包含一組變量上所有支持或禁止的元組。廣義弧相容（GAC）是求解多元約束滿足問題應(yīng)用最廣泛的相容性。簡(jiǎn)單表縮減（STR）是一類在表約束上維持GAC的算法,基于動(dòng)態(tài)維持元組集有效部分的策略,在搜索的每一階段維持相容性時(shí),STR移除當(dāng)前的無效元組,從而降低了查找支持的開銷。在搜索發(fā)生回溯時(shí),STR擁有單位時(shí)間的恢復(fù)元組集有效部分的代價(jià)。STR在高元表約束上獲得了廣泛運(yùn)用,大量基于STR的改進(jìn)算法被提出,其中元組集的壓縮表示是目前研究較多的方法。本文提出的STR2*同樣基于動(dòng)態(tài)維持元組集有效部分的策略,但采用一種新的基于列的方式存儲(chǔ)約束關(guān)系中的元組,并將刪除無效元組以及為變量值查找支持的操作分別轉(zhuǎn)化為與之對(duì)應(yīng)的列操作。此外,STR2*使用時(shí)間戳標(biāo)記變量和約束上的操作次序,降低了獲取論域發(fā)生改變的變量的計(jì)算開銷,并精簡(jiǎn)了數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明該算法在表約束上維持GAC的效率普遍高于現(xiàn)有的非基于壓縮表示的STR算法,并且在一些實(shí)例上的效率高于最新的基于元組集壓縮表示的STR算法。MDDc、STR2和STR3均是表約束上維持GAC的算法,MDDc將約束關(guān)系構(gòu)建... 

【文章來源】：吉林大學(xué)吉林省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：53 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

sparseset操作的演示圖3.1sparseset操作的演示，(a)初始階段，S為空，S.members=0，t指向的數(shù)組的下標(biāo)表示S.members在t階段的值；(b)在t=1階段加入元素3；(c)在t=2

第 3 章 一種效率更高的 STR 算法下進(jìn)行，元組集規(guī)�？s減較快，avgP<30%，STR2*優(yōu)于 STR3，少數(shù)元組集縮減較慢的實(shí)例上，avgP>30%，并且表約束規(guī)模足夠大時(shí)，STR3 優(yōu)于 STR2*。表3.1 和圖 3.2 中右圖可以看出絕大多數(shù)實(shí)例上 STR2*優(yōu)于 STR3，部分實(shí)例上STR2*的效率是 STR3 的 20 倍以上。

圖 3.3 不同算法求解時(shí)間的對(duì)比STRbit: 在一些拓?fù)浣Y(jié)構(gòu)復(fù)雜且表約束規(guī)模較小 和 dubois 兩種算法維持元組集有效部分的代價(jià)據(jù)結(jié)構(gòu)簡(jiǎn)單維護(hù)代價(jià)較低，求解效率稍優(yōu)于 S快的實(shí)例上，例如 rand-15-23、rand-8-20 和 bd超過兩倍的效率提升。表 3.2 可以看出 STR2*STRbit。由于不同類問題的實(shí)例集中的實(shí)例個(gè)數(shù)的 rand-3、rand-5、crossword 三類問題的實(shí)例總圖 3.3 的散點(diǎn)圖中才會(huì)有 STRbit 在多數(shù)實(shí)例上


本文編號(hào)：3601798