Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán định tuyến kênh bằng phương pháp làm nguội mô phỏng
Tóm tắt
Trong bài báo này, một thuật toán cho Vấn đề Định tuyến Kênh (CRP) trên Mô hình Manhattan được đề xuất. Thuật toán sử dụng một phương pháp tìm kiếm trong không gian giải pháp, được biết đến là Làm nguội mô phỏng. Độ rộng kênh được giảm bằng cách phá vỡ các đoạn dài của đồ thị ràng buộc theo chiều dọc, liên quan đến vấn đề này. Chiến lược 'dogleg' được áp dụng tương tự như trong thuật toán định tuyến kênh được đề xuất trong tài liệu [1]. Kết quả thu được từ các phép mô phỏng rộng rãi là đầy hứa hẹn so với các kết quả của các phương pháp heuristics khác cho cùng một vấn đề.
Từ khóa
#Vấn đề định tuyến kênh #mô hình Manhattan #làm nguội mô phỏng #chiến lược dogleg #thuật toán heuristics.Tài liệu tham khảo
E. Lodi, F. P. Preparata,A heuristic for channel routing, Proc. of Found. of Data Organaz. and Alg. Paris (1989), 155–169.
S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi,Optimization by Simulated Annealing, Science Vol. 220 (1983), 671–680.
D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon,Optimization by Simulated Annealing: an experimental evaluation (part I).
G. H. Sasaki, B. Hajek,The time complexity of Maximum Matching by Simulated Annealing, JACM Vol. 35 (1988), 387–403.
H. W. Leong, D. F. Wong, C. L. Liu,A Simulated-Annealing channel router, IEEE Trans. on CAD (1985) 226–228.
F. Darema, S. Kirkpatrick, V. A. Norton,Parallel algorithms for chip placement by Simulated Annealing, IBM J. Res. Develop. Vol. 31 N. 3 (1987).
T. C. Hu, E. S. Kuh,Theory and Concepts of Circuit Layout: An Overview, in VLSI circuit layout: Theory and Design IEEE Press N.Y. 1985.
T. Leighton,A Survey of Problems and Results for Channel Routing, AWOC 86, Loutraky, 1986.
T. Yoshimura, E. S. Kuh,Efficient Algorithms for Channel Routing, IEEE Trans. on CAD of Integrated Circuits and Systems CAD-1, (1982), 25–35.
T. Szymanski,Dogleg Channel Routing is NP-Complete, IEEE Trans. on CAD, CAD-4 (1985), 31–40.
B. S. Baker, S. N. Bhatt, T. Leighton,An Approximation Algorithm for Manhattan Routing, in F. P. Preparata, Ed., Advances in Computing Research, Vol. 2, JAI Press (1984), 205–229.
J. M. Greene, K. J. Supowit,Simulated Annealing without rejecting moves, IEEE Trans. on Computer-Aided Design 5 (1986), 221–228.