时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。  

随机时间依赖网络的K期望最短路径

首先给出了随机时间依赖网络模型，K期望是短路径问题的形式化描述，并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数，路径期望耗费的计算方法，然后，基于随机一致性假设和胡机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性，最后，给出了公交网络的应用实例和实验结果。  

Anytime算法及其应用

阐述了Ａｎｙｔｉｍｅ算法的基本概念和体系结构，讨论了Ａｎｙｔｉｍｅ算法的应用和发展方向。  

时间依赖有向无环网最小时间路径算法

经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中弧权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算法的正确性。  

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.  

最小时间路径算法的改进及在路径优化中的应用*

由于城市交通网络中路径行程时间是随着时间的变化而变化的，求解最小时间路径比较困难，为此提出把交通网络抽象为时间依赖的网络模型的解决方法。对时间依赖网络模型和理论基础进行分析，指出文献［1］描述的最小时间路径算法存在的不足，即不能正确记录路径；通过引入一个记录路径的数组来对此算法进行改进，改进后的算法不仅解决了原算法存在的问题，而且可以满足n∶1的最短路径搜索，扩展了原算法的应用范围。最后用实验验证了改进算法的正确性和有效性。  

二层SA/GA算法解决时间依赖中国邮路问题

中国邮路问题是图论中的经典问题，得到了深入研究和广泛应用。近年来，由于计算机网络与通信、智能交通系统等复杂应用领域的需求，研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义，然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立，最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题，对随机产生的实例进行了测试，并根据问题下界对算法结果进行了分析。  

战术计划识别模型的分析、描述与设计

分析计划识别问题的共性特点，根据军事领域的需求分析，建立战术计划识别模型的逻辑描述与形式化描述，设计实现一个以“匹配、生成假设、假设排序、动态跟踪预测”为主线的战术计划识别模型，并给出具体的应用实例，数据结果表明该模型比较能够反映实际中战术意图识别的特点，并在知识获取与推理效率等瓶颈问题上有了较大的改进。  

时间依赖代价函数下的最优路径查询问题研究

作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出.然而,在计算具有时间限制的费用代价最优路径时,该性质并不成立.因此,目前解决TDSP问题的方法均不能解决文中面对的问题.对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径.该算法适用于有向图和无向图.作者证明了算法的时间复杂度和空间复杂度分别为O(knlogn+mk2logk)和O((n+m)k).最后,作者通过真实数据集上的实验,验证了该算法的有效性.  

基于预测信息的时间依赖网络路径规划算法

分析最小时间规划算法，针对算法在应用上存在的不足，在研究SPFA静态规划算法的基础上，结合该规划算法的优点，提出一种改进的最小时间路径规划算法。实例验证结果表明，该算法能够提供实时、高效、预测性强的规划路径，在城市交通中较好地满足用户的需求。