Heuristic Routing Algorithms for the Switch Box Routing Problems
Ming-fmg Wq · 1991
Switch box routing problem can be considered as a generalized planning problem. 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 inter dependency 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 the heuristic algorithms. A routing system has been developed which adopts these algorithms. The test result shows that the system can effectively find a solution even on the cases which are considered very difficult to route.