基于再聚类和离散优化的k路划分算法

为了寻得集成电路更优的k路划分,提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模,即根据给定划分计算顶点间的评级函数值,依据取值大小进行顶点聚类;然后将超图转换为星型图,并将k路划分问题转换为无约束的离散优化问题;进而设计一个算法迭代移动增益值最大的顶点,在算法求解过程中放宽平衡约束,允许暂时处于不可行域的解,扩大问题的求解空间.在同一平台上使用ISPD98电路测试基准对所提算法、hMETIS-Kway和KaHyPar-K进行测试,并比较最小割值和运行时间.实验结果表明该算法优于hMETIS-Kway,特别是在k=2时,最小割值减少了0.173,速度提升了0.706.此外,该算法对KaHyPar-K也有相应的改进效果.

车辆导航系统基于GIS的动态K最短路递推解法

在对车辆导航系统的路径引导信息进行供需分析的基础上 ,提炼出了对系统设计具有重要意义的动态 K最短路问题 ,建立了路段动态行程时间计算模型 ,提出了将其融入最短路算法中并结合 GIS技术的动态最短路改进 A*算法 ,并设计了通过替换动态最短路的部分路段以搜索动态K最短路的合理前趋替换算法。

基于标号算法搜索过程的K最短路算法设计

K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的Dijkstra标号算法.该算法在搜索过程中得到一条最短路径的同时,获得了大量的临时标号信息;在此基础上,继续采用该算法利用这些临时标号信息进行标号,可以获得其他严密K最短路;将该算法与交叉口有延误的最短路径算法相结合,可方便的计算城市交通网络中交叉口有延误的K最短路径问题;该算法简化了K最短路的计算过程,提高了算法的计算效率.最后,利用一个简单网络介绍了该算法的计算过程.

基于多层k路划分的三维网格并行任务分配策略

为解决传统任务划分方法在三维网格并行计算任务分配阶段产生的通信开销大的问题,提出了一种基于多层k路划分算法的并行任务分配策略。首先利用多层k路划分算法划分三维网格,将任务划分问题转化为图划分问题,然后基于图划分结果给出一个任务映射并行算法将计算任务分配到各计算结点。在深腾1800上求解三维网格模型最短路径问题的实验结果表明,相比于传统的行列划分任务分配策略,该策略在保证负载平衡的同时有效地降低了通信开销,算法的运行时间减少,加速比得到提高。

求解无回路有向连通图中的k阶最短路问题

针对如何在无回路有向连通图中求解k阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径。在该思路的指引下,提出了新的参数概念,如点参数N、弧参数A以及终点的特征参数θ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数N定理和弧参数A定理;利用这些参数和定理,设计出在无回路有向连通图中求解k阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为O(km),m表示弧数;最后,通过应用举例对该算法进行了演示。

映射式K路合并排序算法

本文介绍了映射式排序算法,这种算法附加一定的存储开销,时间复杂性为O(N)。在此基础上,本文还提出了一个新的K路合并算法,关键字与数组下标作映射和链接处理,不实施反复比较和交换关键字的操作,时间复杂性达到O(N),适宜一类特殊问题的大规模信息处理。

二次映射式K路合并排序算法

在映射式K路合并排序算法的基础上提出了一种二次映射式K路合并排序算法，解决了当记录总数较少、关键字最大值较大时，映射式K路合并排序算法存在的存储开销浪费大的问题，并保持时间复杂性不变．

基于轨道交通网络特点的K最短路算法研究

城市轨道交通网络发展带来出行路径选择的复杂性,为了科学掌握线路客流,组织运输,合理引导乘客路径选择,需要开展轨道多路径算法研究;同时,随着生活节奏加快,要求算法高效,注重路径获取的实时性。针对轨道网络特征,将站点之间K最短路搜索转化为线路换乘组合搜索,降低搜索空间复杂度,并利用杭州轨道交通网络进行案例验证。算法明显提升轨道网络K最短路搜索效率,能够更快速响应轨道交通实际运行变化,有助于提升今后轨道交通出行服务应用。

K条路的两个问题

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广———有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k|V|2),同时证明了该算法对于问题是k-近似的.

经髂腹股沟联合K-L入路治疗髋臼骨折的临床研究

目的探讨经髂腹股沟联合K-L入路治疗髋臼骨折的临床疗效。方法将93例复杂髋臼骨折患者随机分成2组,观察组49例采用髂腹股沟和K-L联合入路切开复位重建钢板内固定术治疗,对照组44例采用髂腹股沟入路切开复位重建钢板内固定术治疗,记录手术时间、术中出血量、输血量,用Matta标准评价骨折复位程度,用Brooker标准评价异位骨化情况。结果观察组的手术时间明显长于对照组,术中出血量和输血量多于对照组,复位满意率显著高于对照组,总异位骨化发生率显著低于对照组。结论采用经髂腹股沟和K-L联合入路切开复位重建钢板内固定术治疗复杂髋臼骨折可获得良好效果。

基于分层任务网络的攻击路径发现方法

攻击路径发现是辅助网络资产安全评估的一项关键任务。现有基于智能规划的攻击路径发现方法因建模语言丰富和规划算法完备而深受安全从业者青睐,但其存在的扩展性问题不容忽视。为此,提出一种基于分层任务网络的攻击路径发现方法。具体而言,围绕网络规模逐步扩展、路径发现任务愈加复杂和安全推演场景频繁变化所引发的扩展性问题,将所提方法分解为3个阶段。第一阶段,针对路径生成性能差的问题,引入面向目标拓扑的多层级K路划分算法;第二阶段,针对领域问题描述难的问题,构建融入专家经验的路径规划分层任务网络;第三阶段,针对路径更新效率低的问题,设计应对局部信息更替的攻击路径维护方案。实验结果表明,所提方法适用于大规模网络,执行效率更高,具备良好的扩展性。

几类笛卡尔乘积图的k路顶点覆盖数问题

对于任意图G和正整数k,如果图G中所有长度为k的路都至少含有其顶点子集S中的点,那么我们称顶点子集S为k路顶点覆盖集。我们定义最小的集合S的基数为φk(G),并且称它为图G的k路顶点覆盖数.本文我们主要研究了笛卡尔乘积图的k路顶点覆盖数问题,并给出了φk(Cm□PN2)的估计值。

k-路形式的Konig-Egervary图

推广了Konig-Egerváry图的概念,提出了k-路形式的Konig-Egerváry图,证明树是k-路形式的Konig-Egerváry图;同时研究了单圈图的k-路形式的Konig-Egerváry性质。

基于图多层K路划分的仿真节点映射策略

为了提高网络仿真系统中,多物理服务器情况下,服务器资源的利用率,提出一种基于图多层K路划分的仿真节点映射策略。首先对仿真网络拓扑图进行多层K路划分,将节点映射问题转化为图划分问题,然后依据划分结果将仿真节点映射到物理服务器。经过试验表明,相对于随机映射策略,该策略在保证物理服务器负载均衡的同时,可以有效减少物理服务器资源的消耗。

城市交通紧急疏散路径优化

提出了两种不同疏散路径选择策略,即用户最优疏散策略(UE)和系统最优疏散策略(SO).前者依照个人最优路径,疏散车辆可以自由移动到另一条疏散路径使得相应疏散时间最短,后者通过疏散者之间相互协作或接受统一管理使得系统范围内出行总成本最小.通过对两者的比较研究,确立了疏散路径优化方案.以总疏散时间和疏散距离最小化为目标构建系统最优疏散目标方程,并给出算法步骤.首先用k最短路算法给出一系列疏散路径,再用嵌入式M/G/c/c相互独立排队模型评价各条道路出行时间.最后采用MGCC仿真软件对疏散路径选择方案在路网清空时间、出行距离、拥堵水平等方面表现加以评价.仿真实验结果表明,在高密度疏散交通量情况下,采用系统最优疏散策略可以大幅节省路网清空时间,降低路网阻塞发生的概率.这对增强疏散决策的科学性,提高城市交通应对突发事件疏散能力有重要意义.

铁路客运服务网络路径搜索算法的研究与实现

基于反映旅客出行链的有向换乘服务网,采用一种拼接和去冗相结合的K最短路算法,设计并实现客运服务网络路径搜索系统。该系统可根据客流计划和列车开行方案,以多种路径搜索模式得到合理的乘车方案。以某高速铁路及相关路网的列车开行方案和相应的客流计划为例,对客运服务网络路径搜索算法进行测试,取得了预期的结果,但需在乘车效用的丰富和优化方面进行深入研究。

多层分割算法在构建层次道路网络中的应用

在大规模道路网络上使用"分层"策略构建层次道路网络能够显著降低路径规划算法的搜索空间,对分层道路网络进行分区可改进数据结构,进一步提升算法效率。现有多种网络图分割算法,介绍一类名为METIS的多层分割算法,此类算法通过概化(coarsening phase)、分割(partitioning phase)、还原(uncoarsening phase)三阶段将网络图划分为均等分区,且算法效率高。将两种典型多层分割算法:多层递归二分算法(MLRB)及多层k路分割算法(MLKP)应用于层次道路数据,以检验此类算法是否适用于强调拓扑连通性的道路网络的分区。结果分析表明,多层算法的分区结果并不适合层次道路网络构建,但多层分割的思想值得借鉴。

基于LSP路径规划的自适应流量分配

随着网络流量大规模的增长,ISP(Internet Service Provider)在骨干网中大量部署MPLS[1]网络以解决各种网络问题提高性能。在MPLS网路中流量工程[2]技术被广泛应用,其中多路径自适应流量分配算法可是流量工程[中一项关键技术。在本文中对自适应流量算法MATE[3][4]进行了分析,提出了它的不足,通过最小化最大链路重叠度对LSP(Label Switch Path)进行路径规划,将静态离线算法和自适应动态在线算法结合起来,仿真实验证明这一结合提高了动态算法的收敛速度和稳定性。

车辆导航系统中多路径选择算法的研究

路径选择算法是车辆导航系统中的核心内容之一。采用单亲遗传算法求解路径选择子系统中的大规模路网的K最短路问题,并结合实际路网对算法进行了验证。结果表明,该算法能有效的生成多条备选路径供出行者选择,对出行者的路径选择决策以及对路径选择子系统相关技术的研究开发均具有参考价值。