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

摘要

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