计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
8期
1693-1703
,共11页
宋晓宇%许鸿斐%孙焕良%刘俊岭
宋曉宇%許鴻斐%孫煥良%劉俊嶺
송효우%허홍비%손환량%류준령
路线搜索%短时间体验%签到数据%基于位置的服务
路線搜索%短時間體驗%籤到數據%基于位置的服務
로선수색%단시간체험%첨도수거%기우위치적복무
route search%short-term experience%check-in data%location-based service
路线搜索已经广泛地应用于基于位置的服务和旅游路线推荐等领域.现有的关于路线搜索的研究,通常只考虑景点之间路线的流行程度与用户的需求,因此提供的推荐路线并未考虑景点类别的丰富性,存在类别重复的现象.为了能使用户在短时间内体验所在地区不同类别特色的景点,增强旅游体验效果,文中提出一种新的路线搜索:短时间体验式路线搜索(SERS).该路线搜索方法根据用户给定的查询位置vs、旅行时间限定t以及用户对景点类别选择的集合uc,找到一条非重复多类别且收益最大化的最优景点访问路线.为了有效处理SERS,提出一种预计算结点收益上界值的优化策略,设计了两种优化搜索算法:单收益上界剪枝搜索算法(SUB)和多收益上界剪枝搜索算法(MUB).优化的搜索算法利用收益上界值剪掉了不可能产生结果的分枝,提高了搜索效率.利用Gowalla和Foursquare社交网站真实的签到数据集进行了充分实验,评估了所提出的算法在不同参数设置下的搜索效率,验证了算法的有效性.
路線搜索已經廣汎地應用于基于位置的服務和旅遊路線推薦等領域.現有的關于路線搜索的研究,通常隻攷慮景點之間路線的流行程度與用戶的需求,因此提供的推薦路線併未攷慮景點類彆的豐富性,存在類彆重複的現象.為瞭能使用戶在短時間內體驗所在地區不同類彆特色的景點,增彊旅遊體驗效果,文中提齣一種新的路線搜索:短時間體驗式路線搜索(SERS).該路線搜索方法根據用戶給定的查詢位置vs、旅行時間限定t以及用戶對景點類彆選擇的集閤uc,找到一條非重複多類彆且收益最大化的最優景點訪問路線.為瞭有效處理SERS,提齣一種預計算結點收益上界值的優化策略,設計瞭兩種優化搜索算法:單收益上界剪枝搜索算法(SUB)和多收益上界剪枝搜索算法(MUB).優化的搜索算法利用收益上界值剪掉瞭不可能產生結果的分枝,提高瞭搜索效率.利用Gowalla和Foursquare社交網站真實的籤到數據集進行瞭充分實驗,評估瞭所提齣的算法在不同參數設置下的搜索效率,驗證瞭算法的有效性.
로선수색이경엄범지응용우기우위치적복무화여유로선추천등영역.현유적관우로선수색적연구,통상지고필경점지간로선적류행정도여용호적수구,인차제공적추천로선병미고필경점유별적봉부성,존재유별중복적현상.위료능사용호재단시간내체험소재지구불동유별특색적경점,증강여유체험효과,문중제출일충신적로선수색:단시간체험식로선수색(SERS).해로선수색방법근거용호급정적사순위치vs、여행시간한정t이급용호대경점유별선택적집합uc,조도일조비중복다유별차수익최대화적최우경점방문로선.위료유효처리SERS,제출일충예계산결점수익상계치적우화책략,설계료량충우화수색산법:단수익상계전지수색산법(SUB)화다수익상계전지수색산법(MUB).우화적수색산법이용수익상계치전도료불가능산생결과적분지,제고료수색효솔.이용Gowalla화Foursquare사교망참진실적첨도수거집진행료충분실험,평고료소제출적산법재불동삼수설치하적수색효솔,험증료산법적유효성.