Трассировка межсоединений печатных плат с использованием роевого алгоритма

Задача трассировки — одна из наиболее трудоемких в общей проблеме автоматизации проектирования РЭА. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачи применяются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка — наисложнейшая задача выбора из огромного числа вариантов оптимального решения.

ВВЕДЕНИЕ………………………………………………………………………..5
Глава 1. ПОСТАНОВКА ЗАДАЧИ……………………………………..……7
1.1 Содержательная постановка задачи трассировки печатных плат…..7
1.2 Математическая постановка задачи трассировки печатных плат…..8
Глава 2. КРИТЕРИИ И ОГРАНИЧЕНИЯ ЗАДАЧИ…………………………..10
Глава 3. МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ……………………12
3.1 Определение порядка соединения выводов внутри цепи…………..12
3.2 Распределение соединений по слоям печатной платы……………..14
3.3 Нахождение последовательности проведения соединений в каждом слое………………………………………………………………………...15
3.4 Алгоритмы решения задачи трассировки…………………………...16
3.4.1 Волновой алгоритм Ли………………………………………17
3.4.2 Лучевой алгоритм ……………………………………………19
Глава 4. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ТРАССИРОВКИ……………………………………………………....…………21
4.1. Обоснование выбора алгоритмов решения задачи …………..……21
4.2 Бионические предпосылки алгоритма пчелиных колоний……...…21
4.3 Трассировка как задача глобальной условной оптимизации………23
Глава 5. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННОГО АЛГОРИТМА ТРАССИРОВКИ…………………………………………..……26
5.1 Выбор среды разработки и реализации программы………………. 26
5.2 Создание улья пчел и описание его характеристик …..……………26
5.3 Моделирования поведения улья …………………….………………27
5.4 Описание логики поведения активных пчел………….…………… 28
5.5 Имитация танца пчелы в улье………………………………….…… 31
5.6 Описание логики поведения пчел – скаутов………………….…… 31
Глава 6. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РАЗРАБОТАННОГО АЛГОРИТМА……………………………………………………………………37
ЗАКЛЮЧЕНИЕ…………………………………………………………………..