求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题,由于该问题的搜索空间与元胞自动机的结构相似,设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明,该算法要比最小生成树平均改进15%,优于多数已有的基于最小生成树的近似算法,验证了算法的实用性。

绝对值距离Steiner最小树问题的二进制粒子群算法

绝对值距离Steiner最小树问题是在铺设网络线缆等领域应用广泛的一个NP难的经典组合优化问题。针对此问题,提出基于最小生成树问题的二进制粒子群算法。该算法首先对网络节点进行编码,计算适应度函数值,并使用二进制粒子群算法求解Steiner点。数据实验结果表明,该算法具有实用性。

Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.

空间冲突下起重作业安全迹线规划模型

为保证起重作业的安全高效性,减少起重作业空间冲突的风险,设计起重作业Manhattan平面,剖析起重作业空间冲突因素、机械运行条件与施工组织条件,构建吊物迹线的避障最小直角Steiner树(OARMST)模型,集成Dijkstra启发式算法和无载波通信(UWB)定位技术,开发起重作业迹线规划系统,求解多就位点、多障碍物下吊物的安全移动迹线。研究表明:OARMST模型求解的最优起重吊装安全迹线避免了起重作业的空间冲突风险,通过减少吊物转弯次数和位移,可防止吊物多次骤停摆动和驾驶员多余操作,提高起重作业的安全调度水平。