Heuristic routing algorithms for the switch box routing problems

Switch box routing problems, for PC boards and VLSI, can be considered as generalized planning problems. A subgoal is to find a connection for each net. The search and backtrack techniques must be used to solve the problem. One difficulty of this particular routing problem is the interdependency among the connections. To cope with this problem, the graceful retreat and least impact policies are used to select subgoals and paths of connections. These policies are based on heuristic algorithms. A routing system has been developed which adopts these algorithms. Test results show that the system can effectively find a solution even on the cases which are considered very difficult to route