论文部分内容阅读
时至今日,人们使用智能手机上所推荐的最短路径服务,有时候并不是我们真正所需要的.其实只有我们驾驶汽车的时候,智能手机上所提供的最短路径才是我们需要的.但在步行的时候,我们会更多的考虑周围的环境(比如噪声/空气质量/环境是否优美以及是否安全等)来决定选择哪条路线步行.在大多数情况下,我们想要穿过恬静优雅的地方,那里绿意盎然,环境优美,阳光明媚.然而,目前的研究只考虑了部分相关的环境因素,并没有把这些因素统一放到一个模型里面统一研究.本文以圣彼得堡为例,通过综合考虑各种环境因素,构架了一个统一的模型,并依据该模型开发了一个简单的导航服务.我设计了 一个调查问卷,用来调查一个地方对喜欢步行的人的吸引力.该问卷获得了来自不同年龄和性别的58个人的反馈,所有这些反馈形成了一个城市不同地区的五星评分样本。我基于获得的样本,利用随机森林算法,创建了位置吸引力模型,该模型通过考虑一个地方的喧闹程度,建筑风格,来自社交媒体的照片,离水域的距离,绿化程度,是否是工业区域来度量一个地方所处位置的吸引力程度(很好,一般,不好).模型在实验数据集上,总体上的f1分数约为0.6,好的和坏的f1分数分别为0.83和0.65,取得了较好的效果.基于该模型,我对圣彼得堡所有的人行通道的吸引力程度进行了评估.为了创建导航服务,我们比较了两种路径优化方法:一种是基于经典的Dijkstra最短路径算法,将路径的权重设置为吸引力模型所得到的位置吸引力程度,另一种则使用Yen的k-最短路径算法,在找到的前N个最短路径中寻找位置吸引力均值最大的.通过比较,我发现Dijkstra最短路径算法优于Yen的k-最短路径算法,并且使用加权Dijkstra最短路径算法所得到的最短路径和实际的最短路径长度基本相同(长6%).最后,基于加权的Dijkstra最短路径算法,我设计并开发了导航的原型系统.该系统给出算法推荐的几条步行路径,并给出相关的结果比如路径吸引力程度以及路径步行时间,以便用户进行比较选择.人工分析表明,在城市的各个地方,该系统都能够有效的推荐出相关的路径。