东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2016, Vol. 37 ›› Issue (5): 629-633.DOI: 10.12068/j.issn.1005-3026.2016.05.005

• 信息与控制 • 上一篇    下一篇

基于时间约束的人气最优路径搜索

鲍金玲1， 王斌1， 刘刚2， 杨晓春1   

  1. (1. 东北大学 计算机科学与工程学院， 辽宁 沈阳110819; 2. 白城师范学院 计算机科学学院， 吉林 白城137000)
  • 收稿日期:2015-04-01 修回日期:2015-04-01 出版日期:2016-05-15 发布日期:2016-05-13
  • 通讯作者: 鲍金玲
  • 作者简介:鲍金玲(1977-)，女，吉林白城人，东北大学博士研究生，白城师范学院副教授； 杨晓春(1973-)，女，辽宁沈阳人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61572122，61322208，61173031，61129002，61532021)； 教育部高等学校博士学科点专项科研基金资助项目(20110042110028)； 吉林省教育厅科研计划项目(吉教科合字2015第420号).

Popularity-Optimal Path Search Based on Time Constraint

BAO Jin-ling1， WANG Bin1， LIU Gang2， YANG Xiao-chun1   

  1. 1. School of Computer Science & Engineering， Northeastern University， Shenyang 110819， China; 2. School of Computer Science， Baicheng Normal College， Baicheng 137000， China.
  • Received:2015-04-01 Revised:2015-04-01 Online:2016-05-15 Published:2016-05-13
  • Contact: WANG Bin
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

726

摘要： 当旅游景点数目庞大，而限定时间不足以访问任何路径中的所有景点时，现有的搜索方法找不到事实上存在满足条件的路线.提出了一种高效的最优路径近似搜索算法PSScaling，使用修整参数δ，将景点的人气分数调整为一个整数，然后利用路径标签上缩放后景点的人气分数和子路径的时间代价选择最优的子路径向终点扩展，在同一路径中挑选最佳的访问景点组合.最后，通过实验分析，验证了本文提出的算法能够在很高的执行效率下找到近似的最优路线.

关键词: 基于位置的服务, 行程规划, 时间约束, 最优路径搜索, 路网

Abstract: When the permitted time is not enough to visit all attractions in any path， the path satisfying the constraints could not be found by the existing search methods. An approximation algorithm PSScaling to solve this problem was presented， making a choice on any node (visit or pass by) according to the tradeoff between permitted time and popularity score of attractions， and selecting the best combination of attractions to access in the same path. The experimental results on real data sets reveal that the proposed algorithm is able to find the approximate optimal path efficiently.

Key words: location-based services, trip planning, time constrained, optimal path search, road network

中图分类号: