作者：张子寒; 张落成图论模型旅行商问题遗传算法动态规划南京景区
摘要：如何在有限的时间内参观较多自己喜爱的景点并且获得较高的满意度,针对现实生活中的最佳旅游线路问题,给出了以旅行商模型和动态规划为基础的解法,并且提供了启发式的近似算法。模型一是NP问题,算法一、算法二以旅行商模型的动态规划解法为基础。算法三利用遗传算法,给出了编码方式及种群繁衍方式。模型二是P问题,由于存在单调关系,没有后效性,使用动态规划的方式解决了此问题,通过对冗余信息的处理得到了改进的高效算法,并且进行了常数优化。结果显示,旅游时限不同,游览的景点选择是截然不同的,最优解并不是仅仅选择最喜爱的景点参观,而是要在景点的喜爱程度与路径距离、游览时间之间权衡。以游览南京鼓楼沿线及钟山景区为例,如果只有3个小时的游览时间,就可以考虑游览鼓楼、鸡鸣寺再返回,获得满意度18,耗时150 min;如果有10 h游览时间,可以考虑按照鼓楼、鸡鸣寺、总统府、中山陵的顺序游览,获得满意度73,耗时570 min。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
