Малоповоротный алгоритм
+++Скорость на 1 -2 порядка выше чем у волнового. Не нужно хранить все ДРП. Проводники проводятся с учетом следующих на обоих этапов.
---- Используется только для регулярных структур.
Если лучи от А к В пересеклись, то результат готов.. Тогда ячейки луча становятся источником лучей.
Канальный алгоритм.
Распределение соединений по каналам из соображений где соотношение (бла бла) меньше там и пускаем соединение. Распределение соединений по магистралям.
Кратчайшие пути
Пусть задан граф G(x,v) ребрам которого предписаны веса c=||cij||. Задача о кратчайшем пути состоит в нахождении пути с миним суммарным весом от начальной вершины до конечной или до всех остальных если такие пути существуют.
Алгоритм Дейкстра
Для случая cij>=0. Основан на приписывании вершинам временных пометок – верхняя граница длины пути от S к этой вершине. Эти пометки постоянно уменьшаются, и на каждом шаге ровно одна вершина получает постоянную (+) пометку – мин длина пути от S к этой вершине.
Аналогичные задачи: Самый надежный путь, самый длинный путь, путь с наибольшей пропускной способностью.
Теорема
Пропускня способность пути с наибольшей пропускной способностью равна min[maxqij] любой s-t разрез К графа. Для неографа разработан алгоритм Франка-Фрима.
Алгоритмы трассировки
Алгоритм Винтера
Недостатки волновых алгоритмов – последовательный характер, возможно замуровывание выводов. Винтер предложил алгоритм с многократным повторением шага построения всех трасс. На каждом шаге сохраняется только часть трасс.
SPECCTRA – автотрассировщик PC. В нем используется б…ный алгоритм. На первом шаге проводятся все соединения без ограничений. На каждом последующем шаге трассировщик пытается меньшить количество конфликтов, используя 2 метода: вставка и расталкивание, развертывание и проталкивание.
Ни один алгоритм не может обеспечить 100% разводки поэтому топологию необходимо дорабатывать. Требование: простая конфигурация трасс.
Кроме того, существует множество ограничений: длина 2-х параллельных проводников, длина 3-х || проводников и т.д. Ограничения могут быть противоречивыми.
Последовательные алгоритмы компоновки
Компоновка- разбиение исх схемы на подсхемы. Сводится к разбиению графа g(x,v) на части.
1. Для всех вершин х определяется степень р(хi) и выбирается вершина с мин степенью. Если таких вершин несколько, то выбираем вершину с наибольшим количеством кратных ребер.
2. В первый кусок включается вершина хi и вершины смежные с ней.
3. В первом куске окозалось /х1/=n1 вершин
/х1/>n1 для всех xj принадлежащих x1 выбирается вершина минимально связанная с вершинами первого куска, она удаляется из первого куска.
Для /х1/<n1 для xj не принадлежащей x1 выбирается вершина максимально связанная с вершинами х1. ..бла бла бла
. Алгоритм обратного размещения
Оцениваются все элементы и все позиции.
Все элементы упорядочиваются по неубванию
Все элементы размещаются на соответствующие позиции.
Алгоритмы раскраски графов
Раскраской графов называется разбиение множества вершин графов на подмножества, таким образом чтобы в каждом из подмножеств вершины были несмежны.
Алгоритм Вейсмана
Построить все максимально устойчивые множества
Выбор минимального их количества для покрытия всех вершин (метод Петрика)
Рассчитываем ri – количество ненулевых связей.
1. Выбираем макс ri.
2. Удаляем вершины xi и инцидентные ей ребра (удаляем из матрицы соотв строку и столбец)
3. Если матрица еще есть, то переходим к п 1
4. минимизация
5. Для каждого К строится ПСИ в которое входят вершины не вошедшие в К.
6. Для каждой xi строится ti=VПСИ,
7. П’=t1t2… - минимизация
8. Делаем из этого ДНФ
9. Выбираем терм, содержащий минимальное количество сомножителей (это хроматической число графа) Каждое ПСИ вошедшее в этот терм – вершины которые могут быть окрашены в один цвет
Приближенный алгоритм раскраски
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.