摘要
行程规划问题的研究已经成为人们关注的热点之一,越来越多的人需要这一服务的帮助来确定最优的行程路线.假如用户指定了源点和终点,并且限制了旅行的时间,该如何帮助用户规划一条人气最高的旅游路线呢?已有的方法是按照路线上包含的景点全部游玩的规则进行规划,而在上述需求中,如果还是按照这种规则规划,那么可能找不到事实上存在的满足条件的路线.但是如果在路径规划时按照时间花费和景点人气去确定每个景点是游玩还是越过,就可能会找到一条满意的路线,可是这样就大大增加了路径搜索的代价.求解这类的最优路径问题是一个NP难问题,基于现有知识,已有的处理方法并不能有效的降低那一部分增大的搜索代价.因此,提出一种基于贪心策略的算法来解决这一问题,为了提高搜索的准确性,又提出了两个改进的算法.最后,通过实验分析,得出本文提出的算法能够在很高的执行效率下找到近似的最优路线.
The problem of trip planning has received wide concerns in recent years. More and more people require the service of auto- matically confirming the optimal tour route. When users assign the source and the destination, and the time limit of the tour, how can automatically decide the optimal tour route with the highest sum of the popularity scores of scenic spots. Current methods for trip planning are on the setting that providing with the route which is composed of the scenic spots to travel. These would work poorly for the pre-mentioned problem when the route satisfying the constraints can not be found. Thus we adjust the setting to giving the route composed of the scenic spots which users travel or simply pass by. Obviously, the modified problem would incur larger search cost as each scenic spot in the given route has two states. It can be demonstrated that this new problem is NP hard, making it difficult to find an efficient exact algorithm for the present. In this paper, we propose a algorithm based on greedy strategy to solve the trip planning problem, and we also present two improved algorithms with better performance. The experimental results on synthesized and real data sets reveal that our algorithm is able to find the approximately optimal path in high efficiency.
出处
《小型微型计算机系统》
CSCD
北大核心
2013年第12期2702-2707,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61173031
61272178)资助
国家自然科学基金海外及港澳学者合作基金项目(61129002)资助
教育部博士点基金项目(20110042110028)资助
中央高校基本科研业务费专项资金项目(N110404015
N120504001)资助
