Target-driven Maze Routing Algorithm And Optimization

Automatic routing is a basic of computer design automatization, and it's also an important subject of computer aided design. With the development of computer industry, the integrate level of some apparatus is becoming higher, so routing is more complicated than before and manual routing can not fit in with the development of computer aided design now. Under this situation, automatic routing comes.Having been developed for several years, there are many routing algorithms at present. However, almost all routing questions are proved to be NP difficult questions and there are no perfect routing algorithms. In additional, different applications need different routing algorithms. Because of the reasons above, target-driven maze routing algorithm and optimization was brought forward, which is fast, easy to realize and easy to succeed in routing. First, the solution of maze question was applied to routing algorithm. Then in the process of routing, target driven,dynamic pace methods etc are used to accelerate the speed of routing. Lastly, the curves and crunodes of the line are optimized after the routing is finished.With the comparability of routing question and maze question, using the solution of maze question to solve routing question can make the routing algorithm easy to realize and to succeed in routing. In the process of routing, with the differentia between routing question and maze question, target driven,dynamic pace methods etc was used to accelerate the speed of routing and the problem that traditional maze routing algorithms are slow will be solved. After the route is found, the line is repeatedly stretched then compressed. This method decreases the number of curves and crunodes of the line greatly and solves the problem that traditional maze routing algorithms make too many curves and crunodes and improves the efficiency of calculate and storage.This algorithm has been realized on virtual experiment system of circuit. The practical running and theoretics analyse proves that this algorithm is effective in improving the speed of routing and optimizing the rout of routing.