局部搜索技術(shù)在析取時(shí)序問(wèn)題中的應(yīng)用.pdf

1、帶有時(shí)序信息的推理問(wèn)題是人工智能領(lǐng)域的重要研究?jī)?nèi)容。析取時(shí)序問(wèn)題(Disjunctive Temporal Problem，DTP)是時(shí)序推理及調(diào)度領(lǐng)域內(nèi)更具表達(dá)能力的問(wèn)題模型，由于其事件間約束的復(fù)雜性，生成問(wèn)題的可行解現(xiàn)已證明是較難解決的問(wèn)題。因此如何快速獲得問(wèn)題的可行解引起了大量研究人員的關(guān)注:一類(lèi)解決方案是將DTP轉(zhuǎn)化為約束可滿足問(wèn)題(Constraint Satisfaction Problems，CSP)，使用標(biāo)準(zhǔn)的CSP求解

2、技術(shù)來(lái)求解;另一類(lèi)是將DTP編碼為一個(gè)命題可滿足問(wèn)題(Propositional Satisfaction Problem，SAT)，使用現(xiàn)有求解SAT的算法來(lái)求解。然而，DTP在問(wèn)題轉(zhuǎn)化、啟發(fā)式策略及搜索技術(shù)的應(yīng)用等方面仍然存在改進(jìn)空間。
　　局部搜索技術(shù)一直受到人工智能界的極大關(guān)注，GSAT算法的出現(xiàn)再次證明該技術(shù)在求解可滿足問(wèn)題時(shí)有著較高的效率。但是，局部搜索技術(shù)目前仍沒(méi)有成功的用于求解DTP。本文主要研究如何將局部搜索技術(shù)

3、應(yīng)用于求解DTP。為此，本文實(shí)現(xiàn)了應(yīng)用局部搜索技術(shù)并加入約束加權(quán)思想的TSAT算法，將其做部分修改，用于對(duì)DTP直接進(jìn)行求解;通過(guò)分析DTP的問(wèn)題結(jié)構(gòu)，我們將TSAT算法與DPC算法結(jié)合，提出了TSAT算法的改進(jìn)算法—mTSAT，并將DTP轉(zhuǎn)化為元約束可滿足問(wèn)題(meta-CSP)，用mTSAT算法在各變量的鄰域內(nèi)搜索并生成簡(jiǎn)單時(shí)序問(wèn)題，然后判斷其一致性，達(dá)到縮小搜索空間以提高DTP求解效率的目的。
　　為了評(píng)估TSAT算法的性能