Смекни!
smekni.com

Разработка функциональной цифровой ячейки (стр. 5 из 8)

Рис.15. Структурная схема “венгерского алгоритма".

1 блок - начальное преобразование матрицы эффективности

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

2 блок - в полученной матрице эффективности помечаются нули, образующие правильное решение, таким образом, чтобы в каждой строке и столбце было не более одного помеченного нуля.

3 блок - проверка: получен ли полный правильный выбор нулей. Выбор нулей называется полным, если помечено

нулей, где
- размерность матрицы. Если получен полный правильный выбор, то - к выходу, если "нет", то к блоку 4.

4 блок - помечаем "+" столбцы, в которых есть нули со "

". Таким образом помечаем все ребра, инцидентные вершинам. Каждый "+" соответствует вершине.

5 блок - проверка: есть ли в матрице незанятые нули. Нуль называется незанятым, если его строка и его столбец не помечены "+".

6 блок - помечаем незанятый нуль "/".

7 блок - проверка: есть ли в строке нуля, помеченного "/" в блоке 6 нуль со "

", если "да", то переход в блок 8.

8 блок - если в строке есть нуль со "

", то снимаем "+" со столбца, в котором он находился, а строку помечаем "+".

9 блок - если нуля со "

" в строке нет, то это означает, что можно увеличить количество нулей со "
" на 1. Строится расширяющая цепочка, начиная с последнего помеченного нуля (блок 6): переходим по столбцу к нулю со "
", по строке к нулю со "/", по столбцу к нулю со "
", пока цепочка не прервется. Возможно, что цепочка прервется сразу.

10 блок - в результате процедуры в блоке 9 образовалась цепочка, состоящая из нулей со "/" и нулей со "

", но нулей с "/" на 1 больше. Если теперь в цепочке снять с нулей "
", а "/" заменить на "
", то нулей со "
" станет на 1 больше. Снимаем все метки, кроме "
" и переходим к блоку 2.

11 блок - выполняется эквивалентное преобразование матрицы с целью увеличения количества нулей. Если в блоке 5 свободных нулей не найдено, то надо их добавить - для этого из всех незанятых нулей матрицы, то есть лежащих на пересечениях строк и столбцов, не помеченных "+" находится

. Вычитаем
из элементов всех строк, не помеченными "+" и прибавляем ко всем элементам строк столбцов, помеченных "+" [3].

Последовательность действия при решении задачи назначения:

Для решения задачи назначения воспользуемся программой VENGR. Исходными данными для программы являются таблицы координат инвариантных выводов и контактов подключаемых цепей. Таблицы составляются для всех групп инвариантных выводов, включая выводы логических вентилей и выводы контактов разъёма. Для каждой группы программа автоматически составляет матрицу эффективности назначения, а затем в диалоговом режиме выполняется её пошаговые преобразования с целью оптимизации назначения цепей.

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

Таблица 4

"Венгерский алгоритм". Результаты работы программы. Исходные данные: Координаты выводов разъема и контактов цепей

┌───────────┬────────────────────────────────────────────────────────────┐

│ Разъем │ контакты цепей │

├───────────┼┬───────────┬───────────┬───────────┬───────────┬───────────┤

│ X Y ││ X Y │ X Y │ X Y │ X Y │ X Y │

├───────────┼┼───────────┼───────────┼───────────┼───────────┼───────────┤

│ 8.5 33.3││103.5 11.0│ 93.5 18.5│ 91.0 18.5│ 68.6 11.0│---.- ---.-│

│ 8.5 37.0││ 96.0 11.0│ 33.5 71.0│ 96.0 71.0│ 93.5 71.0│---.- ---.-│

│ 8.5 40.7││ 31.0 78.5│ 38.5 71.0│ 41.0 71.0│ 43.5 71.0│ 43.5 11.0│

│ 8.5 44.5││ 31.0 18.5│ 33.5 18.5│ 41.0 18.5│ 36.0 11.0│ 38.5 11.0│

│ 8.5 48.2││ 61.0 18.5│ 71.0 18.5│ 71.0 11.0│ 63.5 71.0│---.- ---.-│

│ 8.5 52.0││ 71.0 71.0│ 63.5 78.5│ 61.0 78.5│ 96.0 78.5│---.- ---.-│

│ 8.5 55.7││ 91.0 78.5│101.0 78.5│101.0 71.0│ 98.5 71.0│---.- ---.-│

│ 3.5 55.7││ 63.5 18.5│ 66.0 18.5│ 98.5 18.5│ 96.0 18.5│---.- ---.-│

│ 3.5 52.0││ 91.0 11.0│ 93.5 11.0│101.0 18.5│---.- ---.-│---.- ---.-│

│ 3.5 48.2││ 58.5 78.5│ 41.0 78.5│ 63.6 11.0│---.- ---.-│---.- ---.-│

│ 3.5 44.5││ 36.0 18.5│ 68.5 78.5│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 40.7││ 61.0 71.0│ 66.0 71.0│ 68.5 71.0│---.- ---.-│---.- ---.-│

│ 3.5 37.0││ 28.5 78.5│ 36.0 71.0│---.- ---.-│---.- ---.-│---.- ---.-│

│ 3.5 33.3││ 33.5 11.0│ 61.1 11.0│---.- ---.-│---.- ---.-│---.- ---.-│

└───────────┴┴───────────┴───────────┴───────────┴───────────┴───────────┘


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

2) Программа составляет по исходной матрице, представленной таблицей 4, матрицу назначений (матрицу эффективности, матрицу стоимости), представленную на таблице 5.

3) Затем программа составляет так называемую эквивалентную матрицу, которая получается в результате выполнения венгерского алгоритма линейного назначения (алгоритм Магу), описанного выше. Эта матрица представлена таблицей 6.

4) В результате выполнения блока 11 алгоритма мы получаем неправильное полное решение (таблица 7), переходим от него к эквивалентной матрице и т.д. по описанному выше алгоритму. Алгоритм продолжается до тех пор, пока не будет получен правильный выбор нулей. После этого программа составляет полное правильное решение и на экран выводится результат задачи назначения.


Таблица 5

┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐

│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │

├───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤

│ │ │ │ │ │ │ │ │ │ │ │ │ │ ├────┐

│ 82.4 │ 62.7 │ 57.3 │ 37.3 │ 67.3 │ 97.7 │ 127.7 │ 69.8 │ 104.8 │ 77.4 │ 42.3 │ 90.2 │ 65.2 │ 47.3 │ 1│

│ 86.1 │ 59.0 │ 61.0 │ 41.0 │ 71.0 │ 94.0 │ 124.0 │ 73.5 │ 108.5 │ 74.0 │ 46.0 │ 86.5 │ 61.5 │ 51.0 │ 2│

│ 89.8 │ 55.3 │ 60.3 │ 44.7 │ 74.7 │ 90.3 │ 120.3 │ 77.2 │ 112.2 │ 70.3 │ 49.7 │ 82.8 │ 57.8 │ 54.7 │ 3│