Лабораторная работа №4

Эвристические алгоритмы размещения

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

Итак, наша задача построить размещение элементов на печатной плате. и здесь у нас есть два варианта для разных групп. В обоих вариантах предварительно строится G(V,E,P) - взвешенный граф схемы. Здесь V - множество вершин, соответствующее множеству элементов принципиальной схемы. E - множество ребер графа. Считается, что две вершины соединены ребром если существует цепь, соединяющая выводы этих элементов. P - весовая функция, ставящая в соответствие каждому ребру графа некоторое натуральное число - количество цепей соединяющих элементы соответствующие концам ребра.

Далее граф модель G(V,E,P) используется по-разному в зависимости от варианта, но в обоих случаях мы решаем задачу размещения путем перехода от топологической модели (граф) к геометрической - изображение графа на плоскости.

Вариант 0

Используется множество фиксированных позиций в узлах прямоугольной сетки m x n с шагом x и y соответственно. В начальный момент вершины графа располагаются в узлах сетки случайным образом. Далее на каждом следующем шаге выбирается некоторая случайная вершины и перемещается (также случайным образом) в какую-либо соседнюю позицию. Если в этой позиции уже расположен какой-либо другой элемент (вершина графа), то они меняются местами. Если суммарная "длина" ребер с учетом веса окажется меньше, то новая позиция становится текущим вариантом размещения. Если общая длина ребер увеличилась, то вариант просто отвергается. Далее процесс случайного выбора вершины и позиции для ее перемещения снова повторяется. Процесс заканчивается либо через заранее заданное время, либо по событию (например, нажатие кнопки). Тот вариант, который остался в памяти на момент прерывания алгоритма считается результатом.

Вариант 1

Этот вариант соответствует физической модели равновесия сил притяжения и отталкивания. Начальное размещения получается заданием случайных координат для размещения элементов (вершин графа). Все связанные элементы притягиваются друг к другу с силой пропорциональной весу ребра и расстоянию между размещенными на плоскости вершинами. В тоже время все вершины отталкиваются друг от друга с силой обратно пропорциональной квадрату расстояния между ними. Коэффициент отталкивания следует подобрать экспериментально. Далее процесс разбивается на множество повторяющихся шагов. На каждом шаге для каждой вершины вычисляется сумма сил (равнодействующая) и все вершины смещаются в полученном направлении на некоторый шаг (не обязательно зависящий от величины силы). Процесс заканчивается либо через заранее заданное время, либо по событию (например, нажатие кнопки). Тот вариант координат вершин, который остался в памяти на момент прерывания алгоритма считается результатом.

Ваша задача состоит в написании программы, которая получая на входе данный из лабораторных работ 1 и 2 строила (и изображала) некоторое размещение элементов с использованием соответствующего алгоритма.

Анимированные демонстрации поощряются. Пример реализации анимации можно найти здесь.