Введение 3
1. Практическая и математическая постановка задачи 4
2. Анализ алгоритмов и методов решения задачи 6
3. Описание разрабатываемого алгоритма 13
4. Развернутая блок-схема алгоритма 15
5. Руководство пользователя 19
6. Решение контрольного примера 25
7. Перечень идентификаторов, используемых при решении программы 26
Список литературы 29
Приложение 30
В данном курсовом проекте рассматривается однолучевой алгоритм трассировки. Лучевой алгоритм находит, в частности, применение в САПР печатных плат и интегральных схем для оценки качества размещения.
Задача трассировки — одна из наиболее трудоёмких в общей проблеме автоматизации проектирования РЭА. Это связано с несколькими факторами, в частности с многообразием способов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачи применяются специфические критерии оптимизации и ограничения. С математической точки зрения трассировка — наисложнейшая задача выбора из огромного числа вариантов оптимального решения.
Среди задач непрерывной конечномерной оптимизации самым важным с практической точки зрения и, одновременно, самым сложным является класс задач глобальной оптимизации. Методы решения задачи глобальной оптимизации делятся на детерминированные стохастические и эвристические методы.
Эвристические методы являются относительно новым и быстро развивающимся классом методов глобальной оптимизации. Среди этих методов выделяются эволюционные и поведенческие (имитационные) методы [1].
В данном курсовом проекте рассматривается однолучевой алгоритм трассировки. Лучевой алгоритм находит, в частности, применение в САПР печатных плат и интегральных схем для оценки качества размещения[2].
Целью курсового проекта является разработка программы однолучевого алгоритма трассировки на языке С++.
В данном курсовом проекте было произведено изучение однолучевого алгоритма трассировки, а также реализованы блок-схема и программа алгоритма однолучевой трассировки.
Результатом работы программы будет вывод на экран луча между точками А и В.
Достоинством данного алгоритма является сокращение числа просматриваемых алгоритмом ячеек, а следовательно, и времени на анализ и кодировку их состояния.
Недостатком является заложенный в их основу приоритетный (постоянный) порядок построения трассы и обхода препятствий влечет за собой неоптимальность получаемого результата.
Поэтому этот алгоритм применяют в тех случаях, когда основным является скорость решения задачи, а к качеству трассировки жестких требований не предъявляется.
