Итерационные алгоритмы улучшения начального значения. Алгоритм парных перестановок. Алгоритм Штейнберга, страница 2

По мере распространения волны, ячейки i-го фронта помечаются.

2) От ячеек k-го фронта переходим по определенным правилам к k-1 и т.д. до P₀. Пройденные ячейки – искомый путь. Пусть критерий – min СДС, тогда пометка: Pi=i, ищем ячейку с P_i-1: P_i=i=P_i-1+1

Достоинства: всегда строит путь, если он есть, и этот путь минимальной длины

Недостатки: в процессе распространения волны каждая ячейка может быть свободна/запрещена/помечена. При max L небоходимо хранить (L+2) значений, т.е. N=log₂(L+2) бит информации. Например, для платы 100х100 мм² и размере дискрета 0,5 (0,2+0,1) ДРП=  200х200 = 40000 ячеек; L=400; N=log₂402 = 9, Т.е. каждый дискрет занимает 9 бит. Следовательно потребуется большой объем памяти для хранения ДРП..

Модификация. Кодирование по mod3

Хранится не само число (вес ячейки), а число mod3.

Ячейка: свободна/запрещена/помечена     - 0/1/2, т.о. для каждой ячейки храним три бита. И это число не зависит от размера платы.

Метод путевых координат

Путевой координатой ячейки С_i будем называть ячейку предыдущего фронта, от кот. Ячейка C_i получает свой вес:

До трассировки задается правило приоритета: ®¯¬ N= log₂ = 6

Для того, чтобы идти в правильную сторону, у любой ячейки должны быть разные соседи. Для этого последовательность 001100110011

N=log₂4 = 2 бита

На самом деле ячейки сложнее – есть еще признак цепи: если принадлежит цепи, то ячейки помечаются тем же фронтом

Второй недостаток – трудоемкость алгоритмов.

Методы:

1. Выбор источника волны

Время работы пропорционально заштрихованной области.

За источник волны выбирается ячейка, находящаяся ближе к краю коммутационного поля

2. Метод встречной волны

Время Т ~ ПR²

Если гнать волну из двух источников попеременно до встречи:

3. Обрамление

Волна распространяется не по всему полю, в рамке, ограниченной D

Если достичь из А в В не удается, то D увеличивается (до 3х раз – потом открывается все поле)

Главные недостаток – последовательный характер алгоритма. Учет длины пути, числа переходов со слоя на слой необходим:

A_i- весовой коэффициент, учитывающий важность i-го параметра, f_i – коэффициент, учитывающий значение i-го параметра.

Пример: Пусть учитываются 2 параметра: СДС и количество переходов:

а1 = 1; f1 = 1

а2 = 3; f2 = 1, если есть переход, 0, если нету

DР = 1+3f2

Обратно: пока можем идти по уменьшению значения – идем.

Для пути: l=11, количество переходов n=3

Для пути (кратчайшего): l=7; n=5.

Лучевые алгоритмы

Цель – сокращение времени работы

Алгоритм Абрайтиса        

Основной луч

Вспомогательный луч старается обойти препятствие. Если лучи не встретятся (40% трасс), то пользуются волновым алгоритмом.

Малоповоротный алгоритм

Если лучи от А и В пересеклись, то результат готов.

Тогда ячейки луча становятся источниками лучей.

Скорость на два порядка выше, чем у волнового.

Канальный алгоритм

g_Г – емкость горизонтального канала; g_В – вертикального (максимальная)

1.  Распределение соединений по каналам

2.  Распределение соединения по магистралям

Распределение по каналам определяется из соотношения

g

^* - текущ. значение, там где это отношение меньше, там и пускаем соединение.

2)

Графом интервалов называется граф, вершинами которого являются интервалы Mi, а ребро соединяет вершины, если интервалы имеют одинаковые координаты.

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

M1,M5,M2,M4,M6,M3

Просматривая последовательность слева направо, помещаем интервалы на как можно более верхнюю магистраль так, чтобы они были несмежны в графе:

Для верт. Строится еще и граф ограничений:

Дойчем был предложен алгоритм:

Если возможно, то трасса проводится слева как можно выше. Когда все проведено, там, где не мешают друг другу, спрямляют.

Достоинства: Скорость на 1-2 порядка выше, чем у волнового.

Не нужно хранить все ДРП

Проводники проводятся с учетом следующих на обоих этапах

Недостатки: Используется только для регулярных структур

Кратчайшие пути

Пусть задан граф G(X,U), ребрам которого предписаны веса C = ||C_ij||

Задача о кратчайшем пути состоит в нахождении пути с минимальным суммарным весом от начальной вершины SÎX до конечной tÎX или до всех остальных, если такие пути существуют.

Алгоритм Дейкстра

Для случая C_ij³0. Основан на приписывании вершинам временных пометок – верхняя граница длины пути от S к этой вершине. Эти пометки постоянно уменьшаются, и на каждом шаге ровно одна вершина получает постоянную (+) пометку – минимальная длина пути от S к этой вершине.

l(x_i) – пометка вершины x_i

1. l(s)=0⁺

l(x_i) = ¥; x_j ¹S, x_j Î X

p – вершина, последняя получившая постоянную пометку p=S.

2. Для всех вершин x_j Î Г_р смежных с последней вершиной р и имеющих временные пометки уточняется временная пометка:

L(x_j) = min [ l(x_j), l(p)+C(p_xj) ]

3. Из всех вершин, имеющих временную пометку, выбирается вершина с