Постановка задачи размещения. Критерии оптимизации

Задача размещения – задача оптимального расположения элементов. Требуется создать благоприятные условия для последующего выполнения трассировки.
Основная сложность - проблема формулировки выбора адекватного критерия выбора

Критерии:
1. Минимальная суммарная длина соединительных проводников.
2. Минимум числа проводников, длина которых превышает заданный предел.
3. Минимум суммарной длины проводников, соединяющих две наиболее удаленные точки цепи.
4. Минимальная суммарная длина проводников, соединяющих источник сигнала с его наиболее удаленной нагрузкой.
5. Размещение рядом элементов, имеющих наибольшее количество общих цепей.
6. Минимальное число пересечений проводников.
7. Максимальное число проводников с простейшей конфигурацией.
8. Минимум числа перегибов проводников.

9. Минимум суммарных зон реализации цепи.

Что дает минимальная суммарная длина соединительных проводников:
1. Улучшение электрических характеристик соединений
2. Создаются благоприятные условия для реализации соединений (меньше длина => меньше расход => меньше стоимость)
3. Создаются благоприятные условия для трассировки
4. Критерий удобен с математической точки зрения разработки алгоритма. Облегчает учет особенностей схемы путем присваивания весовых коэффициентов отдельным проводникам

Метрики:
1. Евклидова: sqrt((x_i - x_j)² + (y_i - y_j)²)
2. Прямоугольная: |x_i - x_j| + |y_i - y_j|
3. Если все плохо: (x_i - x_j)^s + (y_i - y_j)^s (s = 2, 3, 4 - выбирается экспериментально. Используется при необходимости минимизации длинных проводников)

Классы алгоритмов размещения:
1. Алгоритмы решения математических задач, которые являются задачами размещения
2. Конструктивные алгоритмы начального размещения
3. Комбинационные алгоритмы улучшения начального размещения
4. Непрерывно-дискретные алгоритмы размещения

10. Алгоритмы размещения, основанные на силовых функциях.

Эти алгоритмы относятся к классу непрерывно-дискретных алгоритмов размещения.
Идея: механическая интерпретация. Элементы представляются материальными точками, к которым прилагаются силы притяжения и отталкивания. После этого ищется равновесие сил, которое определяет размещение элементов на монтажной плоскости.

Этапы:
1. Элементы произвольно располагаются на монтажной плоскости.
2. Вводится система сил:
а) Силы притяжения (критерий минимальности длины)
б) Силы отталкивания (предотвращают слияние элементов)
в) Силы отталкивания от краев поля
г) Силы сопротивления среды (препятствуют колебательному характеру перемещения элементов)
3. Для данной системы сил составляется система однородных дифференциальных уравнений II порядка, затем приводится к СОДУ I порядка, решается (например, методом Эйлера). Получаем некоторое равновесное положение.
4. Элементы перемещаются в целочисленные координаты (ближайшие)

Недостатки:
1. Сложность решения ОДУ (как алгоритмическая, так и вычислительная)
2. Отсутствие в этом методе учета габаритов элементов
3. Экспериментальный характер подбора коэффициентов для действующих сил
4. Сильная зависимость от первоначального (случайного) размещение элементов

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