王海燕,管 瑩,李 闖,楊明明
(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ā)式;效率
約束滿足問題(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]。……