A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: BASIC PATH SEARCH ALGORITHM <s> This paper describes a method of generating a path between two points of a cellular array, with some cells being specified as obstacles. The method combines two techniques: A line search is first directed toward the target. This is a fast and extremely effective method on boards with plenty of space. When the line search hits an obstacle, an expansion technique typical for the Lee-type algorithms is then used to “bubble” around the obstacle. The line search can then continue toward the target again. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: BASIC PATH SEARCH ALGORITHM <s> Net by net routing is still a very important technique used to make connections in VLSI circuits. The maze routing algorithms used for this purpose correspond to shortest path searches derived from basic BFS or from A*, with many dedicated improvements. This paper proposes the use of a new path search algorithm, LCS*, for routing individual connections in VLSI circuits. LCS* is a generic and simultaneous bidirectional heuristic algorithm which is faster than A* in most graph domains, such as VLSI routing grids. This is achieved by using dynamic estimation with the separation of computed values for open and closed nodes. Results show that the running time is reduced and little storage space is needed. <s> BIB002
Like global routing, detailed routing also uses the path search algorithm to find the wire routes such as Lee's algorithm, A*, Soukup's algorithm BIB001 , LCS* BIB002 , etc.