用深度学习解决电路布线中的最短连通难题，速度快且可扩展。
MazeNet: An Accurate, Fast, and Scalable Deep Learning Solution for Steiner Minimum Trees
- 将布线问题转化为迷宫求解，用循环卷积网络并行处理
- 在测试中达到100%准确率，速度比传统算法快数倍
- 训练少量终端即可推广到超大规模问题，适合芯片设计
避障矩形斯坦纳最小树（OARSMT）问题是在矩形平面上寻找给定终端间的最短连通路径，同时避开障碍物，是集成电路设计、网络优化和机器人路径规划中的关键任务。由于该问题为NP难，精确算法随终端数量增长而急剧变慢，现有实用求解器不得不牺牲精度以应对大规模问题。本文提出MazeNet，一种基于深度学习的方法，从数据中学习求解OARSMT。MazeNet将OARSMT重构为迷宫求解任务，采用循环卷积神经网络（RCNN）进行求解。其核心优势在于可扩展性：仅需在少量终端的迷宫上训练RCNN模块；更大规模问题可通过复制预训练模块构建更大网络。在广泛实验中，MazeNet实现了100%的OARSMT求解准确率，相比经典精确算法显著降低运行时间，并能处理超过当前最优近似算法的终端数量。
原文摘要 · Abstract (English)
The Obstacle Avoiding Rectilinear Steiner Minimum Tree (OARSMT) problem, which seeks the shortest interconnection of a given number of terminals in a rectilinear plane while avoiding obstacles, is a critical task in integrated circuit design, network optimization, and robot path planning. Since OARSMT is NP-hard, exact algorithms scale poorly with the number of terminals, leading practical solvers to sacrifice accuracy for large problems. We propose MazeNet, a deep learning-based method that learns to solve the OARSMT from data. MazeNet reframes OARSMT as a maze-solving task that can be addressed with a recurrent convolutional neural network (RCNN). A key hallmark of MazeNet is its scalability: we only need to train the RCNN blocks on mazes with a small number of terminals; larger mazes can be solved by replicating the same pre-trained blocks to create a larger network. Across a wide range of experiments, MazeNet achieves perfect OARSMT-solving accuracy, significantly reduces runtime compared to classical exact algorithms, and can handle more terminals than state-of-the-art approximate algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。