Трассировка в коммутационном блоке на основе генетических процедур

Ввиду грандиозной сложности трассировка СБИС разбивается на два этапа: глобальная и детальная. При глобальной трассировке решается две задачи: разбиение коммутационного поля на области и распределение соединений по областям. Детальная трассировка заключается в проектировании топологии соединений внутри областей. Традиционно коммутационное поле разбивается на два типа областей: канал и коммутационный блок (switch box).
В классической постановке коммутационный блок - это прямоугольная область на всех четырех сторонах которой размещены в фиксированных позициях терминалы (выводы). Терминалы помечены цифрами - номерами подключенных к ним цепей. Задача состоит в том чтобы сделать терминалы каждой цепи электрически связными так, чтобы цепи и переходные отверстия, реализующие связи, вписывались в область трассировки и удовлетворяли конструктивным ограничениям.
Обычно проблема решается с дополнительно наложенными ограничениями, одним из которых является число слоев. В работе рассматривается двухслойная трассировка.
Задача трассировки в ограниченной прямоугольной области является NP-полной. Поэтому несмотря на обилие разработок, проблема построения эффективного трассировщика является актуальной.