Research Article
Algorithm design and simulation of Rectilinear Steiner Tree problems based on concrete class Line
@INPROCEEDINGS{10.4108/eai.6-6-2021.2307527, author={Man Feng and Mingyang Li and Pengyuan Chen and Zhenping Lan and Ping Li}, title={Algorithm design and simulation of Rectilinear Steiner Tree problems based on concrete class Line}, proceedings={Proceedings of the 8th EAI International Conference on Green Energy and Networking, GreeNets 2021, June 6-7, 2021, Dalian, People’s Republic of China}, publisher={EAI}, proceedings_a={GREENETS}, year={2021}, month={8}, keywords={minimum rectilinear steiner tree dynamic programming vlsi algorithm optimization}, doi={10.4108/eai.6-6-2021.2307527} }
- Man Feng
Mingyang Li
Pengyuan Chen
Zhenping Lan
Ping Li
Year: 2021
Algorithm design and simulation of Rectilinear Steiner Tree problems based on concrete class Line
GREENETS
EAI
DOI: 10.4108/eai.6-6-2021.2307527
Abstract
This graduation thesis mainly focuses on the specific RST, namely the Minimum Rectilinear Steiner tree, to study and improve the algorithm, and finally simulation and output results. Steiner tree problem belongs to combinatorial optimization discipline and is NP-hard problem. Over the past three centuries, many mathematicians have extended and extended this problem, making the steiner tree tree problem further developed. This paper mainly deals with a sub-problem of steiner tree, the Minimum Rectilinear Steiner tree problem. In this paper, based on dynamic programming, a classical technique to solve the steiner tree problem, two algorithms, L-MRST and Z-MRST, are proposed to construct the Minimum Rectilinear Steiner tree on a plane. Both algorithms use point data discretization for pre-tree preparation. However, in the same solution mode, the algorithm l-mrst directly iterates on the current subtree to build the final tree. The algorithm zmrst preprocesses the feasible z-layout standby of all points and enumerates all possible layouts when traversing the nodes. This algorithm increases the algorithm complexity, but the results are obviously optimized. Experimental results also bear this out. For the Minimum Rectilinear Steiner tree problem, the two algorithms in this paper have their own advantages and disadvantages, which can help VLSI problem to some extent, and can effectively optimize the large-scale wire network routing problem.