摘要：最短路径计数是图计算中的一个重要研究问题,旨在查询顶点间的最短路径数,在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图,但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比,时序图增加了时间信息,结构更复杂,在查询顶点间的路径数时必须考虑边的激活时间,因此静态图中最短路径计数方法不再适用于时序图,并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题,提出一种基于树分解构建TG-TL(Temporal Graph-Tree Label)索引的方法。该方法包含构建索引和在线查询两个阶段,构建索引阶段根据时序图的属性设计时序树分解算法,将时序图转化为树结构;然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法;在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明,与基于TG-base(Temporal Graph-base)索引的查询算法相比,所提算法在查询效率上至少提升了61%,因此所提算法在时序图最短路径计数问题上具有高效性和有效性。

摘要：为了解决路网中考虑偏好的空间文本对象多目标最短路径查询问题,设计了包含属性的IR树索引结构;然后利用类别约束,排序约束构建限定的有向无环图.提出了支持属性的局部贪婪算法SALG_SPG,以对最短路径查询进行处理;为进一步提高查询处理效率,提出了支持属性的全局优化算法SAGO_SPG,该算法利用阈值和缓存机制减少了大量无效、重复的计算;最后,通过与现有的FEBF算法的对比实验,分析并验证了所提算法的高效性.

摘要：计算模型(概念模型、形式模型)是计算学科最基础的概念,针对传统算法类教学存在的忽视计算模型的问题,以最短路径求解的Dijkstra算法为例,探讨如何构造其形式模型,给出基于模型的算法,以及算法的正确性证明、复杂性分析和算法实现,介绍用抽象、理论和设计3个学科形态拆分该算法求解问题的整个过程,以达到控制和降低问题求解复杂性,提高学生求解复杂问题能力的目的。

摘要：道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图,查询给定节点间距离最短的路径。然而,道路网络具有时序性,将道路网络建模为时序图更符合实际情况。与静态图相比,时序图的规模更大,结构也更为复杂,增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下,时序图上源节点和目的节点之间旅行时间最短的路径。因此,时序最短路径的结果受给定出发时间影响,为时序最短路径的查询带来了新的挑战,传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图,并基于树分解提出了TD-H2H索引,利用该索引可以快速准确地实现时序最短路经查询。首先,研究了时序图上的树分解问题,提出时序树分解算法,将图结构转变为树结构。然后,通过树分解快速确定索引结构,提出了高效的索引构建算法,用以构建TD-H2H索引。最后,基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验,结果表明提出算法的查询效率优于现有算法1~2个数量级,证明了提出算法的有效性和效率。

摘要：装配体功能尺寸最短路径树能够描述装配体中全部功能尺寸与相关零件尺寸之间的关系,建立装配体全相关尺寸模型。但对于复杂装配体,其要素众多,尺寸关系复杂,功能尺寸最短路径树及尺寸模型的建立很困难,不便在实际中应用。文中提出复杂装配体尺寸分级建模方法,研究复杂装配体分级的一般原则,基于最短路径理论对某装配体进行分级尺寸建模,证明该方法对复杂装配体的尺寸建模与求解是行之有效的。

摘要：最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。

摘要：常规的识别方法在光网络关键链路识别中,存在多用户并行、大量无效链路等问题,导致其整体有效性较差。提出了一种基于信息传输最短路径的光网络关键链路识别方法。采用矩形窗平滑处理光网络内链路,通过离散化处理分解各个链路,计算每个链路的信息传输最短路径,获得局部最优解集合,将集合中最小值视为待识别目标,在此基础上,计算各个链路和节点的时差,获得时差向量,以时差向量作为识别标签,设定识别门限值,实现对光网络关键链路的识别。实验结果表明:在多用户并发的情况下,设计的关键链路识别方法识别精度高达478 Hz,其关键链路的有效性较好,优于常规的链路识别方法。

摘要：电缆路径设计是船舶电气设计的重要环节,是决定全船电缆长度的关键步骤。随着计算机辅助设计日益普及,利用计算机编程对电缆敷设路径进行设计,设计最短电缆敷设路径,对提高设计效率、设计精准度及设计成果具有重大意义。本文通过对最短电缆长度计算方法以达到最短电缆路径设计做以下介绍,旨在对同行业中船舶电缆最短路径设计提供参考。

摘要：最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.

摘要：为了改进传统算法求解最短路径时运算量大且无法计算交叉口转向延误的不足,提出可直接求解受限路网中两点之间最短路径的改进拍卖算法.将价格矢量扩展至二维,解决了价值量被不同转向行为共用的问题.设计了节省存储空间的数据存储结构,可准确描述交叉口转向行为,且便于检索.针对不同规模和密度的随机路网,比较了改进算法和Dijkstra算法求解单一起、终点之间的最短路径问题.结果表明,在含5 000个结点、20 000条路段的高密度路网中,改进拍卖算法的搜索时间约为Dijkstra算法的30%,能准确求解受限路网中的最短路径,并保留了原Auction算法可并行计算的基本性质.