Учебная САПР электронных средств. Асланянц В.Р. - 56 стр.

       3. Аналоговое рабочее поле – для алгоритма гибкой трассировки и
т.д.
      Формализованная формулировка задачи
      (применительно к волновому алгоритму)
      Найти путь кратчайшей длины между 2-мя вершинами в регулярном
графе степени 4 с ребрами единичной длины.
      Тип оптимизационной задачи
      Это задача динамического программирования (применительно к вол-
новому алгоритму).
      Алгоритмы трассировки
      1. Волновой алгоритм и его модификации.
      2. Алгоритмы трассировки на канальных моделях монтажного про-
странства.
      3. Алгоритмы трассировки по магистралям.
      4. Топологические алгоритмы трассировки (алгоритмы, основанные
на теории планарных графов и алгоритмы гибкой трассировки (на аналого-
вом рабочем поле)).

                     6.2. Описание программы TRACE-3

     В лабораторной работе исследуется волновой алгоритм трассировки.
Схема программы трассировки TRACE-3 представлена на рис. 15, подпро-
граммы WAVE - на рис. 16.
     Входные данные
     Входными данными являются 5 файлов исходного описания проекта,
обработанные программой PLACE-3 и шестой файл BDP.SO (список со-
единений), созданный программой TLO-3.
     Выходные данные
     Выходным является файл BDP.LIN, содержащий описание дискрет-
ного рабочего поля: это массив DP(DX, DY), изображения слоев печатной
платы, сформированные на основе массива DP(DX, DY), а также файл
BDP.REP, содержащий список не проведенных соединений.
     Промежуточные данные
     D - номер очередного слоя платы;
     Q - номер очередного соединения;
     A - номер очередного фронта волны;




                                                                    56