兩種智能值排序啟發(fā)式研究

王海燕，管 瑩，李 闖，楊明明

(1.吉林師范大學(xué)計算機學(xué)院，吉林四平136000;2.吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院，長春130012; 3.阜新高等?？茖W(xué)校計算機信息技術(shù)系，遼寧阜新123000)

兩種智能值排序啟發(fā)式研究

王海燕1，2，管 瑩3，李 闖2，楊明明2

(1.吉林師范大學(xué)計算機學(xué)院，吉林四平136000;2.吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院，長春130012; 3.阜新高等?？茖W(xué)校計算機信息技術(shù)系，遼寧阜新123000)

為提升約束滿足問題求解效率，對最受推崇的智能值排序啟發(fā)式Look-ahead和Survivors-first進行深入研究。比較兩種值排序啟發(fā)式在常規(guī)和自適應(yīng)兩種環(huán)境下的效率表現(xiàn)。結(jié)果顯示，在多數(shù)問題類上，常規(guī)情況下Survivors-first效果更好，而在自適應(yīng)環(huán)境下效率有所下降;在不同環(huán)境下使用不同啟發(fā)式可提升約束滿足問題求解效率。

約束滿足問題;約束求解;值排序啟發(fā)式;效率

0 引 言

約束滿足問題(CSP:Constraint Satisfaction Problems)［1］一直是人工智能的一個重要研究方向，相關(guān)技術(shù)被廣泛應(yīng)用于航天、配置及組合問題求解等領(lǐng)域。約束求解是CSP的關(guān)鍵問題，其效率備受矚目。經(jīng)典的求解基于回溯搜索與約束傳播的結(jié)合模式，搜索過程在分支策略與變量排序啟發(fā)式(VOH: Variable Ordering Heuristic)和值排序啟發(fā)式(V-O-H:Value Ordering Heuristic)配合下探索問題的解。一段時間在某種程度上，V-O-H被忽略了，因為很多情況下它需要大量計算資源，但越來越多的研究證明，它是影響約束求解效率的一個重要因素。

V-O-H指變量選擇值進行優(yōu)先實例化的順序，值排序的變化會直接影響搜索樹各個結(jié)點產(chǎn)生分支的變化。值排序最初的評判依據(jù)是CSP解的數(shù)量［2］。……