最短路问题

摘要： 群体单调分配方案(Population Monotonic Allocation Scheme,后简称PMAS)是合作博弈的一类分配机制。在合作博弈中,PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案,从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论,利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案,将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题,并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。

摘要： 高校数学类课程不仅是学生学习专业知识的工具,更是培养学生数学素养、科学思维、道德修养、树立正确人生观、价值观的载体。本文以《离散数学》课程中的“最短路问题”教学为例,探索如何将该课程思政元素有效融入到专业知识传授过程中,以求达到立德树人、润物细无声的教育教学效果。

摘要： 为了更好地指导多式联运路径决策实践,研究了带时间窗和时刻表双重约束的多式联运路径优化问题,建立了以运输成本和中转成本构成的总成本最小化为目标的数学模型,并设计了相应的改进蚁群算法。在原有网络节点编号基础上增加一级编号区分两点间不同的运输方式,以实现蚂蚁对平行边的识别,同时在状态转移概率中加入方向启发因子,以加快算法收敛速度。最后,构建了测试算例,测试结果表明:提出的算法具有较好的稳定性,且在最优解质量方面优于对照的遗传算法和蚁群算法,能够用于此类问题的求解;时间窗和时刻表对多式联运路径决策具有显著影响,在多式联运路径决策中应予以重视。

摘要： 最短路算法是图论中的核心问题之一,也是信息学竞赛考察的重点。主要讲解了在竞赛中求解最短路径问题常用到的四种算法,包括Floyed-Warshall算法、Dijkstra算法、Bellman-Ford算法、SPFA算法,并指出了四种算法的优劣,提出了四种算法的适用情况。

摘要： 最短路算法是图论中的核心问题之一,也是信息学竞赛考察的重点.主要讲解了在竞赛中求解最短路径问题常用到的四种算法,包括Floyed-Warshall算法、Dijkstra算法、Bellman-Ford算法、SPFA算法,并指出了四种算法的优劣,提出了四种算法的适用情况.

摘要： 基于神经动力系统模型,给出了求解赋权图中最短路问题的连续化优化方法,最后2个具体的实例验证了该方法的可行性.

摘要： 为了更好地指导多式联运路径决策实践,研究了带时间窗和时刻表双重约束的多式联运路径优化问题,建立了以运输成本和中转成本构成的总成本最小化为目标的数学模型,并设计了相应的改进蚁群算法.在原有网络节点编号基础上增加一级编号区分两点间不同的运输方式,以实现蚂蚁对平行边的识别,同时在状态转移概率中加入方向启发因子,以加快算法收敛速度.最后,构建了测试算例,测试结果表明:提出的算法具有较好的稳定性,且在最优解质量方面优于对照的遗传算法和蚁群算法,能够用于此类问题的求解;时间窗和时刻表对多式联运路径决策具有显著影响,在多式联运路径决策中应予以重视.

摘要： 构建了一个包含原料采购、生产和销售过程的集成供应链模型,研究了由原料、生产商和销售商产品构成的三层库存系统的生产订货问题.在有限的规划期内,销售商每次进货量相同,生产商按照EOQ模型采购原材料.以最小化供应链系统的总运营成本为目标,构建一个混合整数非线性规划模型,寻找销售商最优订货方案和生产商最佳生产策略.首先利用网络优化方法求解生产商的最优生产计划,其次利用定界穷举法寻求销售商最优的订货周期,给出了具体的计算方法和Matlab程序.通过算例分析验证了算法的有效性,并研究了各参数对最小费用及最优解的影响.

摘要： 随着网络功能虚拟化的发展,为带有服务功能链限制的数据流的传输选择最短路变得更加灵活也更加重要.已有的算法都是在单个域内为流选择满足服务功能链限制的最短路.而在多域或者说分布式的网络中,各个成员网络彼此之间的信息往往是不共享的,因此,利用原有算法计算出的最短路可能不再是真正的最短路.该文提出了一个新的算法,解决了跨域的流的传输问题,使得成员网络可以在保护了自己内部的隐私信息的同时为数据流选择成本最低路径.

摘要： 为了尽可能地解决搜索分组密码线性逼近较困难的问题,本文通过重新定义线性特征将搜索线性逼近问题转化为在赋以权重的有向图上找最短路问题;在此基础上,首次提出了一种运用蚁群算法搜索分组密码线性逼近的算法模型。将该模型运用到DES(Data Encryption Standard)上,本文搜索到了与文献[1]同样的线性逼近,从而为搜索分组密码线性逼近开辟了一种新的途径。

摘要： 在用"奇偶点图上作业法"求解"中国邮路问题"时,需检查图中的每一个回路.当图中回路较多时,检查不便且容易出错.对此,文章给出了求解"中国邮路问题"的Excel解法,并给出算例.

摘要： 在用"奇偶点图上作业法"求解"中国邮路问题"时,需检查图中的每一个回路.当图中回路较多时,检查不便且容易出错.对此,文章给出了求解"中国邮路问题"的Excel解法,并给出算例.

摘要： 在用"奇偶点图上作业法"求解"中国邮路问题"时,需检查图中的每一个回路.当图中回路较多时,检查不便且容易出错.对此,文章给出了求解"中国邮路问题"的Excel解法,并给出算例.

摘要： 在用"奇偶点图上作业法"求解"中国邮路问题"时,需检查图中的每一个回路.当图中回路较多时,检查不便且容易出错.对此,文章给出了求解"中国邮路问题"的Excel解法,并给出算例.

摘要： 本发明公开了一种用于面向最短路径问题的图结点属性存储器实现方法和装置，本发明的图结点属性存储器包括多个图结点属性存储器单元；每个存储器单元包括图结点属性初始化、结点属性写成功、读成功机制；图结点属性初始化，源结点属性值初始化为0，非源结点属性值初始化为正无穷大（存储数据区所有二进位初始化为全1）；结点属性写成功，当且仅当要写结点的属性值小于等于存储器中结点属性值时，才能写成功，否则忽略该写操作；图结点属性读，对于结点属性存储单元的读操作立即返回结点属性数据。本发明为最短路径问题实现了一种图结点属性存储器实现方法，减少了随机读操作对性能的影响。

摘要： 本发明公开了一种最短路径引导方法和最短路径引导系统，其包括以下步骤：S1、通过一GPS系统定位用户当前位置，并读入用户的目的地位置；S2、在一地图数据库中获取用户当前位置和目的地位置之间的所有路径信息，并生成用户当前位置和目的地位置之间路径的拓扑结构；S3、通过所述地图数据库获取所述拓扑结构中各个节点之间长度和拥塞信息；S4、分别设定节点之间长度和所述拥塞信息的权重值，并计算各个节点之间的有效长度；S5、基于所述拓扑结构和各个节点之间的有效长度并计算所述用户当前位置和目的地位置之间的最短路径。本发明还考虑了配送路线中各个路段的道路状况信息，从而能够得到时间上最短的配送路线。

摘要： 本发明公开了一种用于面向最短路径问题的图结点属性存储器实现方法和装置，本发明的图结点属性存储器包括多个图结点属性存储器单元；每个存储器单元包括图结点属性初始化、结点属性写成功、读成功机制；图结点属性初始化，源结点属性值初始化为0，非源结点属性值初始化为正无穷大（存储数据区所有二进位初始化为全1）；结点属性写成功，当且仅当要写结点的属性值小于等于存储器中结点属性值时，才能写成功，否则忽略该写操作；图结点属性读，对于结点属性存储单元的读操作立即返回结点属性数据。本发明为最短路径问题实现了一种图结点属性存储器实现方法，减少了随机读操作对性能的影响。

摘要： 本发明公开了一种基于改进Q‑learning算法的最短路径问题的解决方法，具体包括：建立位置‑动作的价值表格，将Q表全部初始化为0，选择合适的更新步长、贪婪参数、奖赏折扣及平滑参数；根据最短路径问题的要求设置初始位置记作x

摘要： 本发明涉及一种带基于位置学习效应的最短路径问题的精确求解的启发式搜索方法，特别涉及一种机器人路径规划方法。机器人在寻找最短路径的过程中，通过强化学习与环境进行交互，获取经验，意味着机器人可以以更小的代价通过同一条路径，因此该情况下的最短路径与无学习效应时的最短路径很可能是不同的。为了解决此问题，在机器人获取外部环境信息，根据先验知识确定学习效应函数之后，通过启发信息，设计出符合该问题需要的剪枝操作和过滤操作来提前排除确定不会出现在最短路径上的部分路径，从而加速搜索过程，使得机器人在合理有效的时间内寻找到一个精确的全局最短路径，进而用于指导机器人行驶。

摘要： 本发明公开一种基于网络权重优化与两阶段法的城市最短路径获取方法及其应用，包括：1.由实时路况信息构建城市网络；2.变换路段权重，引入新网络下最短距离的上界3.最短距离估计模糊度α；4.通过单队列混合标号修正法，快速获得上界5.通过标号修正法，利用上界得到起点到终点的最短路径。本发明考虑在城市路网中，由于交通设施与交通拥挤，对路段的交通条件造成不同的影响，引入模糊度α，解决导航软件不能处理模糊估计的问题，并有效地提高了导航效率。

摘要： 本发明涉及变电站巡检技术领域，公开了一种变电站无人机巡检单源最短路径规划方法、系统及介质，可以进行无人机最短路径的三维航线规划，以供无人机自动巡检和提高效率。包括采集变电站的激光点云数据，并根据点云数据建立三维点云模型；基于三维点云模型利用三维航线规划软件进行巡检航线自主规划以得到单源最短巡检路径；将单源最短巡检路径至管控平台，由管控平台根据单源最短巡检路径通过任务制定巡检任务；管控平台远程向机巢下发巡检任务；机巢解析巡检任务，协调机巢各机构动作为无人机起飞准备条件，同时向无人机发送任务指令，无人机接收到机巢传送的任务指令，在适飞条件下自动起飞，按既定的巡检路线完成飞巡作业任务。

摘要： 本申请提供了一种分段时空最短路径地图匹配算法，根据运动轨迹的时空性质划分轨迹为多个子轨迹，该划分方法能够规避大部分迂回路线带来的匹配问题，再将轨迹点附近候选路段划分为“微段”，并基于微积分思想调整路段权重，该调整权重方法能够避免轨迹点误匹配到与真实路线相邻的路段上。

摘要： 本发明实施例适用于路径规划技术领域，提供了最短路径的生成方法、系统、设备及存储介质，在本发明实施例提供的最短路径的生成方法中，集合V为所有货架所在点的集合。在初始状态时，将出发点s放进集合S中；当集合V‑S中存在货架υi时，计算出发点s到货架υi的相对于集合S的最短路径dist[s，υi]；在所述货架υj在集合V‑S中时，相对于集合S的最短路径dist[s，υi]中距离最短的货架υj，将货架υj放进集合S中，更新集合V‑S中的货架υi相对于集合S的最短路径dist[s，υi]，能够解决目前技术中无法快速的获取寻找到目标货架的最短路径，使得不能及时的使医护人员拿取到所需的耗材，使用不便，效率比较低的问题。

摘要： 本发明公开了一种使用挂绳移动机器人通过最短路径访问多个目标点的方法。是当移动机器人的工作场景中需要大量电力供应，由机载电源不能完成任务，或在没有无线网络通信的环境中有通信需求时，使用最大长度有限的线缆将机器人与一个固定位置的基点相连接情况下的挂绳移动机器人路径规划方法，在多目标点访问任务的执行过程中，机器人通过一根具有最大长度的绳缆保持与基点的连接，从而获取稳定的能源、网络支持，并且访问所有目标点所需的运行路径长度为最短。而在具有挑战性的环境中执行无人规划任务，也是机器人领域的重要需求之一。本发明高效地求解出了使用挂绳移动机器人访问给定的一组目标点的最短路径，具有实际应用价值。