张皓然 孙冬璞 季发虎 徐铭秋 高 尚 徐 杨

（哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080）

1 引言

随着经济的快速发展和社会的飞速进步，我国的旅游市场规模也日益庞大，各类旅游网站和应用软件应运而生。但是这类应用多数以旅游订票、预定酒店或者团购各个景点门票为主，在旅游路线规划方面却鲜少涉及。现实生活中的旅游需求因人而异，每个人期望的旅游内涵都不尽相同。简单举例，比如一个喜欢拍照的大学生来大连旅游，可能并不关心诸如圣亚海洋世界、发现王国这样的娱乐场所，而更多的是想去滨海路、星海广场拍一些与海亲密接触的照片，或者去十五库、猫的天空之城这样的充满文艺气息的场所寻找自己的拍摄灵感，此时各大主流应用软件提供的旅游路线可能就不太适合，而需要的是一个可以自由定制旅行计划、并可以根据计划智能规划旅游路线的应用软件。

要解决上述的旅游路线规划问题，其本质是一个旅行商问题，我们将需求简化即可得到如下问题描述：用户当前所在点为起始位置，给定n 个目标节点以及所有节点之间的两两相互距离（即驾车所需时间），求一个路径使得游览所有的景点后总用时最短。目前暂没有一个多项式时间复杂度的算法来解决这个问题，所以其还是个NP问题。

目前关于最短路径和路径规划方面已经取得了很多研究成果［1～3］。文献［4］给出了兼顾查询者熟悉路径的个性化路径规划框架。文献［5］提出了多目标路径规划，并以事先给出的路网静态属性重要程度来简化最终路径，不同属性的重要程度即为驾驶偏好。文献［6］建立兴趣景点集模型和特征拐点集模型，确定多约束指标，以最短路径规划为基础融合多约束指标设计动态旅游路线规划算法。文献［7］将“巡检路线排班最佳”转化为TSP 动态规划问题，用贪婪算法分析每班每人近似最佳路线，得到可行路线方案，进行均衡度比较从而选定最佳巡查方案。文献［8］提出并探讨了几种团队会合模式，设计了一种基于动态位置的旅游团队自动会合模型。文献［9］采用两阶段法的先分组再定路线的策略，设计了一种基于攻略中景点出现频率的启发式旅行线路规划策略用于自动规划旅游行程。文献［10］提出基于多源异构众包数据的风景路线规划系统，为用户推荐给定两点间景色最优的旅行路线。文献［11］结合群体用户的个人偏好，发现一条带有局部分散兴趣点且群体收益最大的访问路线，设计了基于分支限界搜索策略的优化算法。文献［12～13］根据旅游时间、费用、旅游体验等数据，对全国5A景区旅游路线进行了规划。

通过实际应用需求分析可知，用户对于旅行地点的选择不会很多，所以，在节点不多的情况下，本文采用能记录路径的状态压缩动态规划方法实现用户的个性化旅游路线规划，并基于该方法，结合服务器端与客户端开发技术，设计和开发了应用系统，该系统可以实现用户常用的地点查询、区域查询、最近邻查询、群组查询、天气查询等功能，并可以通过与用户交互，实现个性化旅游路线规划。

2 基本数据结构

数据结构1（Package）客户端和服务器端数据传输的包头结构，用于客户端和服务器端进行数据交换，其内容包括：包的字节数，用户要访问的景点数量和景点列表，具体定义和说明如表1所示。

表1 Package结构

数据结构2（Task）服务器端对得到的请求报文进行解析后交给其他协程进行解析后得到的可供协程处理的结构体，其结构如表2所示。

表2 Task结构

数据结构3（Path）服务器端算法部分用来记录最佳路径的辅助数据结构，结构如表3所示。

表3 Path结构

3 算法

旅行商问题是NP 问题，如果集合表示用set实现效率很低。由于路线规划应用中要保存的数都是不重复的较小整数，所以这里用二进制串表示集合。例如集合｛1，3，5，6，7｝表示成二进制串为1110101，其中集合里面有的数对应的位数写成1，没有的写成0。要判断第3 位是不是1，就把1110101 右移（3-1）位，得到11101，然后结果和00001 进行& 运算，如果结果是1 说明第3 位是1，否则说明第3位是0。

推广一下，对于数字x，要看它的第i 位是不是1，那么可以通过判断布尔表达式的真值来实现，表示如下：

要使用动态规划，需要问题本身有最优子结构，因此需要找到要解决的问题的子问题。

首先将需求抽象，假定出发点编号是0，要去3个景点，编号从1～3，则问题抽象成：从0出发，经过［1，2，3］这三个景点，然后回到0，使得花费最少。要实现这个需求，需要从下面三个实现方案中选择花费最少的方案：

1）从0 出发，到1，然后再从1 出发，经过［2，3］这两个城市，最后回到0，使得花费最少。

2）从0 出发，到2，然后再从2 出发，经过［1，3］这两个城市，最后回到0，使得花费最少。

3）从0 出发，到3，然后再从3 出发，经过［1，2］这两个城市，最后回到0，使得花费最少。

根据分析，设置一个二维的动态规划表dp，定义｛1，2，3｝表示经过［1，2，3］这三个城市，然后回到0。则目标函数表示为dp［0］［｛1，2，3｝］。依据前面讨论的集合二进制串表示方式，将｛1，2，3｝表示成二进制串111，其对应的十进制数为7，则最终目标函数表示为dp［0］［7］。

求解上述三个方案的最小值意味着：

其中Costa®b表示从a 出发到b 的距离。dp［3］［｛｝］即是从3出发，不经过任何城市回到0的花费，所以dp［3］［｛｝］=Cost3®0。

观察可知，三个小问题的解决方案的最优解，构成了大的解决方案，所以这个问题具有最优子结构，可以用动态规划来实现。

假设算上起点后四个景点之间的车行距离如表4所示。

表4 车行距离（单位：min，-1代表不可达）

首先确定dp 表的大小，有n 个景点，从0 开始编号，那么dp 表的行数为n，列数为2（n-1）。在求解时，第一列的值可以从邻接矩阵导出，后面的列可以由前面的列结合邻接矩阵导出，所以求出的动态规划表如表5所示。

表5 动态规划表（-1代表不可达）

关于最佳路径的记录问题，只需要在状态转移过程中记录下每一状态是从已经计算出来的哪个状态转移过来并实时更新即可。

路线规划具体算法如算法1和算法2所示。

算法1.GetMinTime（Q）

输入：数据点集Q；

输出：最佳路径Path；

Begin

mp¬计算所有点之间的相互距离；

for（State¬from 0 to（1＜＜n）-1）

for（i¬from 0 to n）

for（j¬from 0 to n）

if（i=j）then continue；

NewState¬State|（1 ＜＜j）；

if（dp［NewState］［j］>mp［i］［j］+dp［State］［i］）

Path［NewState］［j］.pre=State；

Path［NewState］［j］.id=i；

dp［NewState］［j］=mp［i］［j］+dp［State］［i］；

return P；

End.

算法2.GetBestPath（Path）

输入：得到的最佳路径记录数据结构Path；

输出：最佳访问路径BestP；

Begin

PState¬Path［State］［i］.pre；

j¬P［State］［i］.id；

if（PState！=1&&j=0）then GetBestPath（Path）

append（BestP）；

return BestP；

End.

4 服务器端的构建

本服务器的构建采用Reactor 模式［14］进行设计。Reactor 要求主线程只负责监听是否有事件发生，如果有就立即将该事件通知工作线程，除此之外不进行任何实质性工作，读写数据、接受新连接以及处理客户请求都由工作线程完成，主线程只负责监听和分发事件。这种模式很适合Golang 编程语言，主线程负责监听端口并接受报文，接收到请求后直接调起一个协程对数据进行处理并返回结果。

进行TCP 编程时应注意当面对高并发时TCP的沾包问题［15］，所以在设计数据结构时首先设计了整个包的数据长度，当主线程接收到请求时，首先判断其字节数与包大小是否相符，再决定是继续读取还是丢弃。具体算法如算法3所示。

算法3.CheckData（P）

输入：数据包P；

输出：工作协程的任务T；

Begin

if（len>0）then tot+=len；

if（len>=4）then get（P.numByte）；

if（len>=8）then get（P.numSpot）；

if（tot=P.numByte）then return T；

else return Error；

End.

5 客户端的构建

客户端的构建使用传统安卓程序设计架构，具有轻、快、小且节省资源的特点。软件使用XML 语言设计友好的交互界面，可以良好地反馈结果以及准确的反馈异常。客户端使用Java 语言处理事务逻辑，并且考虑到移动端计算能力的限制和网络传输的压力，将复杂的功能交于服务器端进行计算，与服务器端通信的方式采用SOCKET中的TCP编程。

客户端向用户提供地点查询、区域查询、最近邻查询、群组查询等必要的空间查询服务接口，并调用API向用户提供可能需要的服务接口，比如定位、天气查询等。例如对于用户的地点查询及区域查询需求，查询请求及相应查询结果如图1 和图2所示。

图1 地点查询

图2 区域查询

对于旅游路线规划功能，使用列表视图供用户自由选择，用户提交后分步显示服务器返回的景点顺序和具体路径，并将其在地图上直观地显示出来，用户可以根据返回的时间和路径，灵活地安排和调整计划，如用户想要游览金龙山、龙凤山和中国亭园，可以进入助手界面并选中这三个景点提交查询，结果如图3和图4所示。

图3 旅游路线规划结果（1）

图4 旅游路线规划结果（2）

如果想要得到具体路线，也可点击详情。

6 结语

动态规划在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路径、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其他方法求解更为方便。本文利用动态规划算法，结合服务器端与客户端开发技术，实现了交互查询和旅游路线规划，给出了实际解决方法和过程，同时讨论了基于路径记录的状态压缩动态规划策略在解决带有节点数量限制的旅游路线规划问题中的应用。