Разработка функциональной цифровой ячейки (стр. 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│