导读:本文包含了最优路径搜索论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:路径,算法,最优,不确定性,时间,系统工程,网络。
最优路径搜索论文文献综述
江群,戴戈南,张森,葛又铭,刘玉葆[1]（2019）在《基于用户偏好的最优路径搜索》一文中研究指出本文研究基于用户偏好的最优路径搜索,在预算约束下寻找一条满足用户偏好即关键字和权重偏好的最优路径.此研究问题是NP-hard.为了高效地解决这类查询问题,本文提出新的索引建立方法,在查询阶段利用索引结构过滤出候选节点集.另外,提出基于A*的路径搜索算法来做路径查询,并利用几个有效的剪枝策略加快算法的执行速度.在两个真实的签到数据集上的实验结果证明了本文提出方法的有效性.当预算时间设置为4～7h时,与已有最好的PACER算法相比,本文的路径搜索算法消耗的查询时间更短.(本文来源于《华东师范大学学报(自然科学版)》期刊2019年05期）
沈良[2]（2019）在《不确定条件下的交通网络最优路径搜索算法及其应用》一文中研究指出最优路径搜索问题是算法研究领域长期关注的问题,其在交通、通信以及地理信息系统中有着广泛的应用。从不确定性的角度研究最优路径搜索问题,是近年来新的热点研究问题。本文基于考虑交通网络中通行时间相关性的最优路径搜索算法,重点探讨了在不确定条件下,如何考虑车辆在路口的等待时间模型、不同路网中的电动汽车能耗模型、交通配流模型以及基于车牌识别技术的OD(Origin-Destination)均值和协方差的估计模型。具体如下:第一章绪论部分主要介绍了不确定条件下的可靠路径搜索问题、电动汽车能源消耗问题、交通配流问题以及OD均值和协方差估计问题的研究背景和意义,并且探讨了不确定条件下的可靠路径搜索算法的一些研究历史与现状,论述了部分经典的路径搜索算法和交通配流模型。第二章研究了在不确定条件下,同时考虑路段的随机通行时间、路段通行时间相关性和路口等待时间叁个因素的可靠路径搜索问题,现有的研究中很少有算法能够同时考虑这叁个因素。由于本章中所提出的新的有效通行时间模型具有不可加性,因此传统的路径搜索算法并不适用。据此,本章提出了一个新的基于不等式放缩技巧的算法,通过给出有效通行时间模型的上界和下界,并以最小的有效通行时间的上界为阈值,通过阈值,可以直接判断某条路径是否有可能成为最优的可靠路径,节约了计算量。给出的数值结果表明,若忽略不同路段之间的通行时间相关性或信号交叉口的随机延迟会导致寻找可靠最短路径的结果存在偏差。最后,我们证明了所得到的可靠最短路径可以避免由于网络不确定性和信号交叉口延迟而导致的意外延迟,从而为通行者提供更好的行程规划支持。第叁章通过在第二章中提出的新的可靠路径模型的基础上,同时考虑了不同路网情况下的电动汽车能耗模型。研究了基于这两个目标函数的最优路径问题。并运用多目标规划的理论和方法,结合第二章中提出的算法和现有的K短路算法进行双目标函数的求解,最终给出了搜索非支配解(Non-dominated solution)的方法,最后通过叁个不同规模的小、中、大型网络验证了算法的有效性。第四章在第二章的有效通行时间的基础上,提出了一类考虑路段通行时间相关性和路口等待时间的基于通行时间可靠性的交通配流问题。由于每一天交通需求的随机变化,通行者的通行时间不是确定的,而是随机变量。假设通行者在过去经验的基础上能够得知通行时间的随机分布,通过刻画通行者在通行时间不确定情况下的路径选择行为并将其转化为一个变分不等式模型。对于这类新的考虑路段通行时间相关性和路口等待时间的模型,在本章中给出了模型解的存在性证明,并且采用了相继平均法(MSA)去求解该问题。最后给出的数值算例说明了提出的模型在应用上的特性和算法的有效性。第五章在第四章基础上,研究了基于车牌号码识别的路径流量的均值和协方差的估计。根据前人的研究基础,本章提出了一个基于车牌识别的估计路径流量均值和协方差的最小二乘估计模型。为了求解这个模型,本章将观测的路段流量进行重构,利用车牌识别的技术获得远超观测到的流量数据的信息,最后根据模型的约束条件和给定的先验数值估计最终的OD需求的均值和协方差。并利用均方根误差(RMSE)来描述估计结果的准确性。数值算例结果显示,通过利用车牌识别的技术估计的结果比单纯的利用观测路段流量的数值的结果准确很多。(本文来源于《中国矿业大学》期刊2019-04-01）
凃强,程琳,林芬,孙超[3]（2019）在《考虑出行者风险态度的最优路径搜索》一文中研究指出由于交通系统存在不确定性,路径旅行时间会在一定范围内随机变化,面对随机交通网络,出行者表现出不同的风险态度,可以分为风险规避,风险中立和风险偏好3类。采用正态分布描述路段出行时间的随机性,分别考虑出行时间预算、超额出行时间、低额出行时间3类模型,研究出行者最优路径选择行为,此外还考虑了出行者多兴趣点出行的情况。提出一种标号修改算法,分别设置可靠度α=0. 75和α=0. 25,对不同风险态度出行者最优路径选择结果进行了分析,并在不同规模网络中对算法性能进行了测试。结果表明:在10 000节点大网络中,该算法平均运算时间约为100 ms,相比确定网络下的经典dijkstra算法约慢了42%,通过对比分析可知,该算法运行速度较快,能够满足实际应用需求。(本文来源于《吉林大学学报(工学版)》期刊2019年03期）
朱云虹,袁一[4]（2018）在《基于改进A*算法的最优路径搜索》一文中研究指出最短路径搜索问题是智能交通技术应用中的一个关键问题,而A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。传统的A*算法未考虑到实际路网中交通灯的影响,求得的最短路径并不一定是行程时间最短。但是路径选取在实际应用中主要追求最优而不是最短,因此传统的A*算法有一定的局限性。为了克服以上问题,通过将交通灯的等待时间引入启发式函数,构造一种新的启发式函数并应用于A*算法,利用减少最短路径搜索中路网上等待交通灯的时间来优化路径的总行程时间。通过对Minneapolis的地图基础数据进行路径搜索实验,结果表明,改进的A*算法有助于降低最短路径的总行程时间成本,并且与传统的A*算法搜索消耗的时间效率相似。(本文来源于《计算机技术与发展》期刊2018年04期）
周熙阳,杨兆升,张伟,邴其春,商强[5]（2016）在《考虑干线协调控制的城市最优路径搜索算法》一文中研究指出针对现有最优路径搜索算法没有考虑到干线协调控制的情况,导致搜索到的最优路径实际效果不佳等问题,提出了一种考虑干线协调控制的城市最优路径搜索算法。首先,将相位差引入到干线协调配时方案中,提出了一种改进的信号交叉口等待时间模型。然后,以IDA~*算法为基础,提出了一种考虑干线协调控制的改进IDA~*搜索算法(AICIDA~*算法),以路径总时间费用和运算时间为评价指标进行了算例验证。结果表明:与传统算法和考虑干线协调控制的A~*算法(AICA~*算法)相比,AICIDA~*算法能够在更短的时间内搜索到费用更低的路径。(本文来源于《吉林大学学报(工学版)》期刊2016年06期）
沈良[6]（2016）在《考虑出行时间相关性的最优路径搜索算法及应用》一文中研究指出最优路径搜索问题是算法研究领域长期关注的问题,其在交通、通信以及地理信息系统中有着广泛的应用。从不确定性的角度研究最优路径搜索问题,是近年来新的热点研究问题。本文基于考虑交通网络中出行时间的不确定性的最优路径搜索算法,重点探讨了在考虑不同路段之间的出行时间的相关性条件下,如何搜索最优的可靠路径搜索算法以及节能路径的搜索算法。第一章绪论部分简要介绍了不确定条件下的可靠路径搜索问题的研究背景、意义,并且探讨了不确定条件下的可靠路径搜索算法的研究历史与现状,论述了一些经典的路径搜索算法。第二章研究了考虑路段出行时间相关性的可靠路径搜索问题,现有的研究中很少有算法能够考虑该问题。本章所提出的算法利用不等式放缩的技巧,给出了有效出行时间的上界和下界,以最小的有效出行时间的上界为阈值,避免搜索不可能成为最优的路径,节约了计算量,证明了算法的全局最优性,最后给出了算例验证了算法的有效性和正确性。第叁章研究了基于最优路径的关键路段问题,本章在第二章算法的基础上,给出了相关的数学模型,以整个网络的最小化系统总时间为目标函数,找出对系统总时间影响最大的路段定义为关键路段,通过对关键路段的改进可以最大限度的缓解整个网络的拥堵情况。第四章研究了基于可靠性和车辆节能两个目标的最优路径问题。运用多目标规划的理论,结合K短路算法和第二章的可靠路径搜索算法,给出了搜索Pareto有效解的方法以及相关的证明,最后还通过两个不同规模的中、大型网络验证了算法的有效性。(本文来源于《中国矿业大学》期刊2016-06-04）
鲍金玲,王斌,刘刚,杨晓春[7]（2016）在《基于时间约束的人气最优路径搜索》一文中研究指出当旅游景点数目庞大,而限定时间不足以访问任何路径中的所有景点时,现有的搜索方法找不到事实上存在满足条件的路线.提出了一种高效的最优路径近似搜索算法PSScaling,使用修整参数δ,将景点的人气分数调整为一个整数,然后利用路径标签上缩放后景点的人气分数和子路径的时间代价选择最优的子路径向终点扩展,在同一路径中挑选最佳的访问景点组合.最后,通过实验分析,验证了本文提出的算法能够在很高的执行效率下找到近似的最优路线.(本文来源于《东北大学学报(自然科学版)》期刊2016年05期）
邓竞伟[8]（2015）在《城市公交系统的最优路径搜索算法》一文中研究指出在分析城市公交系统特点的基础上,利用改进的最短路径算法对此问题进行阐述和分析,描述了Dijkstra算法和改进的最短路径算法,并将改进的算法应用于城市公交系统中,最后用一个简单的例子进行验证。结果表明,在搜索效率上改进后的算法比Dijkstra算法好。(本文来源于《河北科技师范学院学报》期刊2015年02期）
滕文[9]（2015）在《GPS车载导航系统最优路径搜索算法研究》一文中研究指出近年来,随着交通运输业的不断进步发展,车载导航系统成为目前交通应用领域里的重要研究课题。车载导航系统为用户提供基于实时路况信息的最优路径规划,可以减少车辆在道路上的停留时间,减少汽车尾气排放量,达到减少雾霾改善环境的目的,也为出行者节省了大量的出行时间,使道路资源得到充分地利用。因此,用户出行的路径规划变的尤为重要。车载导航系统的核心部分是路径规划,路径规划要求系统能够根据存储的电子地图拓扑信息,按照某种规划算法帮助驾驶者从始发地到目的地规划出一条最优路径,车载导航系统中路径规划算法研究具有重要意义。车载导航系统中常见的路径规划算法主要是Dijkstra算法和A术算法,但现有算法在路径规划过程中效率低,不适合直接应用于车载导航系统中,需要对其进行相应的改进和优化。本论文主要从改进算法数据结构和A术算法估价函数两方面入手,对原始算法进行优化。鉴于侦测交通路况的技术目前已经很成熟,本文假设在路段交通情况已知的情况下,对多种经典算法规划的路径进行评估,并在原有算法的基础上进行改良。先研究了Dijkstra算法,对该算法的实现过程进行了描述,由于Dijkstra算法属于贪心算法,计算最短路径的过程是将路网中所有节点进行遍历,算法执行效率很低,并且占用大量存储空间,不适合直接应用于车载系统。然后对A*算法的实现过程进行了描述,通过对Dijkstra算法和A*算法进行比较,重点对启发式搜索算法A*算法进行优化改进。在数据结构优化方面,通过二叉堆排序的方法对节点进行排序,在反复存取节点的过程中节约了大量时间,有效地提高了算法的执行效率。在估价函数的改进方面,在路段搜索时加入方向性判别,选择与终点为同一方向且距离较近的节点,提高算法的执行效率。在实际路况应用中,应充分考虑影响行车时间的各类因素,比如交通拥堵、路段时速等因素。论文提出综合考虑距离和路段时速因素,对距离和路段时速分配不同的权值,规划出距离终点近且速度快的路段,从而规划出行车所需时间最少的路径,使之成为最优路径。论文最后通过微软公司的Microsoft Visual Studio 2010软件和Mapinfo软件,分别产生不同数量的节点和线路,并对路网中的节点和线路进行了路径规划。最终通过实验数据证明,当路网节点为200个时,原始算法规划路径为15.7公里,论文改进算法为13.2公里,规划路径距离减少了2.5公里；原始算法规划时间为53毫秒,论文改进算法为20毫秒,效率提高了33毫秒。当路网节点为1000个时,原始算法规划路径为76.1公里,论文改进算法为64.7公里,规划路径距离减少了11.4公里；原始算法规划时间为164毫秒,论文改进算法为67毫秒,效率提高了97毫秒,改进后的算法无论是在规划路径距离方面还是在执行效率方面都要优于原始算法。(本文来源于《西安电子科技大学》期刊2015-04-01）
陈洁萍,甘泉,张慧[10]（2014）在《一种基于最优路径搜索的图像分类方法》一文中研究指出目前已经有多种基于树的算法来解决多类别图像分类问题,然而由于选择的学习和贪婪预测策略不当,这些算法在分类精度和测试时间效率间不能实现很好的均衡。提出一种新的分类器,当树形架构已知时能在效率和精度间实现很好的折中。首先,将图像分类问题转化为树结构中最优路径的搜索问题,提出新的类似于分支界定的算法来实现最优路径的高效搜索。其次,使用结构化支持向量机(SSVM)在多种边界约束下联合训练分类器。仿真实验结果表明,相对于当前最新"基于树"的贪婪算法,当应用于Caltech-256、SUN和Image Net 1K等数据集时,该算法在效率较高时的精度分别上升了4.65%,5.43%和4.07%。(本文来源于《电视技术》期刊2014年23期）
最优路径搜索论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
最优路径搜索问题是算法研究领域长期关注的问题,其在交通、通信以及地理信息系统中有着广泛的应用。从不确定性的角度研究最优路径搜索问题,是近年来新的热点研究问题。本文基于考虑交通网络中通行时间相关性的最优路径搜索算法,重点探讨了在不确定条件下,如何考虑车辆在路口的等待时间模型、不同路网中的电动汽车能耗模型、交通配流模型以及基于车牌识别技术的OD(Origin-Destination)均值和协方差的估计模型。具体如下:第一章绪论部分主要介绍了不确定条件下的可靠路径搜索问题、电动汽车能源消耗问题、交通配流问题以及OD均值和协方差估计问题的研究背景和意义,并且探讨了不确定条件下的可靠路径搜索算法的一些研究历史与现状,论述了部分经典的路径搜索算法和交通配流模型。第二章研究了在不确定条件下,同时考虑路段的随机通行时间、路段通行时间相关性和路口等待时间叁个因素的可靠路径搜索问题,现有的研究中很少有算法能够同时考虑这叁个因素。由于本章中所提出的新的有效通行时间模型具有不可加性,因此传统的路径搜索算法并不适用。据此,本章提出了一个新的基于不等式放缩技巧的算法,通过给出有效通行时间模型的上界和下界,并以最小的有效通行时间的上界为阈值,通过阈值,可以直接判断某条路径是否有可能成为最优的可靠路径,节约了计算量。给出的数值结果表明,若忽略不同路段之间的通行时间相关性或信号交叉口的随机延迟会导致寻找可靠最短路径的结果存在偏差。最后,我们证明了所得到的可靠最短路径可以避免由于网络不确定性和信号交叉口延迟而导致的意外延迟,从而为通行者提供更好的行程规划支持。第叁章通过在第二章中提出的新的可靠路径模型的基础上,同时考虑了不同路网情况下的电动汽车能耗模型。研究了基于这两个目标函数的最优路径问题。并运用多目标规划的理论和方法,结合第二章中提出的算法和现有的K短路算法进行双目标函数的求解,最终给出了搜索非支配解(Non-dominated solution)的方法,最后通过叁个不同规模的小、中、大型网络验证了算法的有效性。第四章在第二章的有效通行时间的基础上,提出了一类考虑路段通行时间相关性和路口等待时间的基于通行时间可靠性的交通配流问题。由于每一天交通需求的随机变化,通行者的通行时间不是确定的,而是随机变量。假设通行者在过去经验的基础上能够得知通行时间的随机分布,通过刻画通行者在通行时间不确定情况下的路径选择行为并将其转化为一个变分不等式模型。对于这类新的考虑路段通行时间相关性和路口等待时间的模型,在本章中给出了模型解的存在性证明,并且采用了相继平均法(MSA)去求解该问题。最后给出的数值算例说明了提出的模型在应用上的特性和算法的有效性。第五章在第四章基础上,研究了基于车牌号码识别的路径流量的均值和协方差的估计。根据前人的研究基础,本章提出了一个基于车牌识别的估计路径流量均值和协方差的最小二乘估计模型。为了求解这个模型,本章将观测的路段流量进行重构,利用车牌识别的技术获得远超观测到的流量数据的信息,最后根据模型的约束条件和给定的先验数值估计最终的OD需求的均值和协方差。并利用均方根误差(RMSE)来描述估计结果的准确性。数值算例结果显示,通过利用车牌识别的技术估计的结果比单纯的利用观测路段流量的数值的结果准确很多。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最优路径搜索论文参考文献
[1].江群,戴戈南,张森,葛又铭,刘玉葆.基于用户偏好的最优路径搜索[J].华东师范大学学报(自然科学版).2019
[2].沈良.不确定条件下的交通网络最优路径搜索算法及其应用[D].中国矿业大学.2019
[3].凃强,程琳,林芬,孙超.考虑出行者风险态度的最优路径搜索[J].吉林大学学报(工学版).2019
[4].朱云虹,袁一.基于改进A*算法的最优路径搜索[J].计算机技术与发展.2018
[5].周熙阳,杨兆升,张伟,邴其春,商强.考虑干线协调控制的城市最优路径搜索算法[J].吉林大学学报(工学版).2016
[6].沈良.考虑出行时间相关性的最优路径搜索算法及应用[D].中国矿业大学.2016
[7].鲍金玲,王斌,刘刚,杨晓春.基于时间约束的人气最优路径搜索[J].东北大学学报(自然科学版).2016
[8].邓竞伟.城市公交系统的最优路径搜索算法[J].河北科技师范学院学报.2015
[9].滕文.GPS车载导航系统最优路径搜索算法研究[D].西安电子科技大学.2015
[10].陈洁萍,甘泉,张慧.一种基于最优路径搜索的图像分类方法[J].电视技术.2014
论文知识图
