Информационные технологии проектирования электронных средств

- 35 - являются закрепленные вершины. В этом случае формирование первого куска начинается с той вершины х ν , которая за ним закреплена. При этом в процессе формирования каждого куска необходимо постоянно следить за тем, чтобы в него не оказалась включенной какая-либо из вершин, закрепленная за другими кусками . Алгоритм становится немного сложнее. Итерационные алгоритмы компоновки В итерационных алгоритмах первоначально произвольным образом про- изводят разбиение графа схемы на куски, а затем начинают переставлять пару вершин или группу вершин, следя за числом внешних связей. Для матрицы смежности это будет означать разбиение ее на клетки, сто- ящие на диагонали, с перестановкой элементов из одной клетки в другую таким образом, чтобы сумма элементов, находящихся вне диагональных клеток, все время снижалась. Такая матрица называется блочно-диагональной. В качестве первона- чального разбиения графа на куски для итерационного алгоритма можно взять результат последовательного алгоритма. Это означает, что итерационный алго- ритм можно применять для улучшения начального алгоритма компоновки. Наиболее связанные между собой элементы будут группироваться в клетках, стоящих на диагонали матрицы смежности, а вне диагональных клеток будут концентрироваться все больше нулевых элементов. С точки зрения простоты нахождения перестановок и удобства програм- мирования большое распространение имеет метод последовательного дихото- мического разрезания графа на два куска. Если нам нужно разбить граф на L кусков, то мы последовательно разрезаем граф на два куска, причем число вер- шин, вошедших в первый кусок, должно равняться заданному числу n 1 . Разбив матрицу на два куска, выделяя n 1 вершин, вычисляем значение критерия каче- ства F 0. Переставляем вершины или пару вершин и вновь подсчитываем значе- ние критерия. Если F 0 > F 1 , то это удачная перестановка. Если же F 0 < F 1 , то это неудачный вариант перестановки и эту пару возвращаем на свое место. Процесс