基于路径优化的A~*算法与Dijkstra算法的性能比较

路径优化成为解决道路拥挤和阻塞的重要途径。传统单源最短路径的Dijkstra算法可以找到从起始点到其他点的最短路径信息,在地图障碍物较多的情况下,其搜索时间较长。人工智能领域带启发式函数的A*算法由于本身就具有记忆性的功能,在路网中可以自主性的选择最优路径,并且随着障碍物信息和地理位置信息的增多,其搜索效率更高。通过实验将A~*算法与传统的Dijkstra算法进行仿真比较,对比它们的搜索速度和搜索效率,结果证明在实际路网中A~*算法的搜索效果更明显。     

结合改进A*算法与拆线重布的有序逃逸布线

逃逸布线是印刷电路板设计的一个重要组成部分.针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法.首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线.接着,优化同长度布线路径,调整拥挤区域布线路径.最后,使用A*算法和广度优先搜索进行拆线重布.实验结果表明,该方法对给出的所有测试用例都实现了100％的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6％,?97.8％,总体线长也接近最优.提出的方法能够明显减少寻找可行解的时间,提高布线质量.     

基于动态网格的135度PCB区域布线算法

由于不断增长的芯片引脚数量、极高的引脚密度和独特的物理限制,印刷电路板(Printed Circuit Board,PCB)的手动布线已成为一项耗时的任务。近年来,高效率的自动化布线技术得到了广泛的研究。区域布线是PCB设计的一个重要组成部分。针对基于静态网格区域布线的方案,布线拥塞、布通率低等问题,本文提出了一套基于动态网格的135度区域布线算法,主要包括以下技术:(1)对当前布线采用实时扩展动态网格;(2)135度布线角度节点调整算法;(3)基于拥塞控制的改进A^*算法;(4)有效的拆线重布机制。实验结果表明,该算法对于所有工业界布线测试用例布通率都达到100%,并且运行时间方面优于工业布线器Free Routing和Allegro。     

一种以时延均衡为优化目标的全局布线算法

本文算法以文献[1]中的A~*－Search算法为基础，对其加以利用和改造，使之满足以时延均衡为优化布线目标的需要，提出了解决大规模并行系统和同步系统中的时延均衡性问题的一种有效方法。实验表明，布线效果良好。     

结合改进A*算法与拆线重布的有序逃逸布线

逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法。首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线。接着,优化同长度布线路径,调整拥挤区域布线路径。最后,使用A*算法和广度优先搜索进行拆线重布。实验结果表明,该方法对给出的所有测试用例都实现了100%的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%, 97.8%,总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间,提高布线质量。     

电子整机三维自动布线技术研究

电子整机的快速布线是影响整机快速制造的瓶颈之一。本文采用三维加权网格,对电子整机三维模型进行网格划分,描述了布线空间。运用基于网格的迷宫算法和最小斯坦纳树生成法,进行线缆敷设的线路搜索,并加入Rubin优化算法改善搜索速度。结合实际工程经验和规则,以自行开发的电子整机三维布线系统(3DRS)验证了该算法的可行性。     

无线电设备、电信设备

TN80,TP391.72006020677电子整机三维自动布线技术研究/吴银锋,吴兆华,李春泉(桂林电子工业学院机电与交通工程系)//电讯技术.―2005,45(2).―76～81.电子整机的快速布线是影响整机快速制造的瓶颈之一。该文采用三维加权网格,对电子整机三维模型进行网格划分,描述了布线空间。运用基于网格的迷宫算法和最小斯坦纳树生成法,进行线缆敷设的线路搜索,并加入Rubin优化算法改善搜索速度。结合实际工程经验和规则,以自行开发的电子整机三维布线系统(3DRS)验证了该算法的可行性。图5表0参3TN8012006020678电子产品质量管理工作探讨/白宏光(东北…     

基于形状的朝向目标布线算法

在传统布线算法的基础上,本文提出了一种无网格布线算法——基于形状的朝向目标线探索法.该布线算法主要针对障碍物外形尺寸多样,已布连线线宽及线间距离可变的布线情况,尤其适用于印刷电路板及集成电路的布线,该算法的基本要素是障碍物的包容矩形和带有预定终点的探索线,且所需存储空间小、布线速度快、布线路径短,具有良好的布线效果.     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

面向动态障碍物的三维A*优化避障算法研究

针对空间站舱内漂浮物、太空碎片密集区域等复杂场景下的动态避障问题,本文提出了一种面向动态障碍物的三维 A*优化避障算法,主要用于完成空间站舱内飞行器和小型空间机器人在上述环境下的路径规划任务。该算法把传统二维 A*算法推广到了三维,然后通过模糊判断规则对路径进行优化,实现运动路径的实时优化,降低在三维无重力环境下的能量消耗。仿真结果表明,该算法可以对三维环境下动态障碍物进行有效避障,并且优化指标提高将近一倍, 能够有效降低能量的消耗。     

PCB外观检查机形态学运算多核并行加速的实现

为了解决PCB外观检查机中存在的速度问题,对其中用到的形态学运算采用多核并行的方式进行加速。给出了腐蚀运算的普通算法和一种优化算法的多核并行实现过程。实验表明,无论是形态学运算的普通串行算法还是优化算法,通过多核并行处理的方式都可使其运算速度大幅提高。当运算规模较大时,并行加速比可趋近参于运算的处理器数量。     

基于信号完整性仿真的高速电路板设计研究

随着电子设备信号传输速率的提高,电路板布线密度增大,PCB设计对信号完整性的影响越来越大.为了解决电子产品设计初期信号完整性问题,以DDR4高速并行总线为例,改变DDR4数据传输线PCB设计参数,采用无码间干扰方法仿真测试,得到合理的PCB布线方法,提高信号的完整性.同时对网络负载端阻抗不匹配问题进行RC并联阻抗匹配优...     

一个基于层次式PB角钩链结构的区域布线器

提出一个新的基于层次式PB角钩链结构的多层无网格布线器.该布线器基于PB层次式角勾链数据结构和网块扩展算法,使用朝向目标的加速策略提高算法的运行速度,并使用改进的二叉区间树管理算法的中间数据.还提出了基于拥挤度的无网格拆线重布算法.通过显式记录每个线网段周边的拥挤状况,并将其结合到网块扩展的费用当中,使拆除线网的选择和待布线网的路径搜索统一起来.实验结果表明,该布线器能有效地提高布通率,且算法运行速度较快.     

一个基于层次式PB角钩链结构的区域布线器

提出一个新的基于层次式 PB角钩链结构的多层无网格布线器 .该布线器基于 PB层次式角勾链数据结构和网块扩展算法 ,使用朝向目标的加速策略提高算法的运行速度 ,并使用改进的二叉区间树管理算法的中间数据 .还提出了基于拥挤度的无网格拆线重布算法 .通过显式记录每个线网段周边的拥挤状况 ,并将其结合到网块扩展的费用当中 ,使拆除线网的选择和待布线网的路径搜索统一起来 .实验结果表明 ,该布线器能有效地提高布通率 ,且算法运行速度较快     

面向超大规模集成电路物理设计的通孔感知的并行层分配算法

随着集成电路规模的日益增长,需要处理的线网数量显著增多,层分配算法运行时间增大成为限制高效设计布线方案的重要因素;此外在生产工艺中,通孔的制造成本较高.针对以上两个问题,本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量:(1)一种高效的基于区域划分的并行策略,实现各区域在并行布线阶段负载均衡,以提高并行布线的效率;(2)基于线网等效布线方案感知的通孔优化策略,决定各线网对布线资源使用的优先级,进而减少层分配方案的通孔数量.最终将上述两种策略相结合,提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法.实验结果表明该算法对通孔数量和运行时间均有良好的优化效果.     

飞机/发动机复杂腔体遮挡算法研究

利用电磁场高频近似理论,计算飞机进气道、喷管和座舱等腔体的RCS,需要考虑腔体内表面网格单元感应电流之间的相互影响,即判断网格单元之间的相互遮挡关系。在分析比较直接搜索及改进算法、并行＋直接搜索算法和拓扑法的基础上,提出了快速判断复杂腔体面网格单元相互可见性的新算法一拓扑踪迹算法。计算分析表明,文中算法不仅适用于任意复杂电大腔体遮挡关系判断,计算速度比其他三种算法提高若干倍,且构建腔体的体网格越大计算速度越快。     

基于高效负载均衡的网络任务分配技术

针对传统的网格在分配任务的过程中,当多任务发生竞争的时候,由于多条路径的任务负载不均衡,造成传输速度慢的问题,提出一种基于遗传算法负载均衡的网格工作流算法.通过模拟自然界的生物进化过程对任务空间进行随机化搜索,根据预定任务的适应度函数,并用全局并行搜索方式找到最优节点,避免了传统方法的负载不均衡问题.实验证明,该算法实现了负载的快速均衡,提高了网格工作流系统的工作效率.     

改进D*Lite算法在虚拟士兵路径规划中的应用

针对传统D*Lite算法存在的频繁转弯、过于靠近障碍物的问题提出改进D*Lite算法。该算法使用烟花算法中的映射规则将过于靠近障碍物的格子判定在安全范围之外,并使用烟花算法对D*Lite算法规划好的路径中的关键转折点间的路径进行二次规划以减少不必要的转弯。路径规划结果显示,所提出的改进D*Lite算法能够实现虚拟士兵最优路径搜索并且效率更高。仿真结果分析表明,所提出的算法比已有的改进D*Lite算法更优,可以有效减少路径中不必要的转弯,且使路径与障碍物保持合适的距离。     

融合可见光指纹的迷宫机器人路径规划算法

针对复杂迷宫环境下移动机器人路径规划中存在的寻路时间较长、效率较低等问题,提出了一种将可见光指纹信息与A*算法相融合的迷宫机器人路径规划算法。该算法引入局部、全局障碍密度参量对A*算法的评价函数进行优化,使评价函数可以自适应障碍物密度;同时引入可见光指纹信息,利用障碍物对可见光光源的遮挡程度来判断各方向路径是否通畅,解决了A*算法在寻路进程中无法预见后续障碍物的问题。仿真结果表明,基于可见光指纹的改进A*算法能够有效减少传统A*算法的路径搜索点数量,平均寻路效率提高了43.5%,具有一定的应用价值。