摘要:本文研究基于用戶偏好的最優(yōu)路徑搜索,在預(yù)算約束下尋找一條滿足用戶偏好即關(guān)鍵字和權(quán)重偏好的最優(yōu)路徑.此研究問題是NP-hard.為了高效地解決這類查詢問題,本文提出新的索引建立方法,在查詢階段利用索引結(jié)構(gòu)過濾出候選節(jié)點(diǎn)集.另外,提出基于A*的路徑搜索算法來做路徑查詢,并利用幾個(gè)有效的剪枝策略加快算法的執(zhí)行速度.在兩個(gè)真實(shí)的簽到數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了本文提出方法的有效性.當(dāng)預(yù)算時(shí)間設(shè)置為4~7h時(shí),與已有最好的PACER算法相比,本文的路徑搜索算法消耗的查詢時(shí)間更短.
注:因版權(quán)方要求,不能公開全文,如需全文,請(qǐng)咨詢雜志社