Название работы	Кол-во страниц	Размер
Рецензия на книгу: Мартин Хайдеггер. Бытие и Время (M. Heidegger.	1	289.15kb.
Шифрование методом скремблеров	1	51.68kb.
Изучить блочные алгоритмы шифрования: алгоритм перестановки, алгоритм...	1	82.65kb.
Пример: Алгоритм метода пжи (полные жардановые исключения)	1	19.18kb.
Шаг Подготовка научной работы Шаг Подача заявки на участие	1	37.18kb.
Лекция n 25. Способы составления характеристического уравнения.	1	68.94kb.
Задание на курсовую работу группы: дисциплина: «Информатика»	1	15.15kb.
1Сортировка подсчетом. Общая схема метода 1 1Сортировка извлечением...	1	318.17kb.
Программа для молодежи и школьников «шаг в будущее» «шаг в будущее...	1	156.49kb.
Он шёл тяжело опираясь на меч, левой рукой, а правой зажемал рваную...	1	43.99kb.
Прототип Алгоритм парсера	1	60.16kb.
Задача о назначении Постановки задач	1	63.41kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Алгоритм венгерского метода
Шаг 1. Проводим предварительные преобразования матрицы C (получаем эквивалентную матрицу).
Формулы предварительных преобразований:
1) Преобразование в столбцах:

2) Преобразование в строках:

Шаг 2. Рассматривая столбцы матрицы сверху вниз поочередно, помечают звездочками нули таким образом, чтобы они не лежали в одной строке или одном столбце (отмечается первый попавшийся [но в соответствии с алгоритмом] в столбце ноль). Если количество поставленных звездочек равно m, то оптимальное решение найдено, и процесс решения закончен.
Шаг 3.

а) столбцы, в которых есть нули со звездочками, помечают сверху знаком «+», и далее эти столбцы считают занятыми;

б) просматривая строки матрицы слева направо, ищут незанятые нули. Незанятый ноль помечается знаком штрих, строку, в которой он находится, справа помечают знаком «+», и далее эту строку считают занятой. Если в строке нуля со штрихом есть ноль со звездочкой, то снимают знак занятости «+» со столбца, где находится ноль со звездочкой. Если в строке 0’ нет нуля со звездочкой, переходят к шагу 5. Если в процессе поиска незанятых нулей оказалось, что незанятых нулей больше нет, а решение при этом не менялось, то переходят к шагу 4.
Шаг 4. Выбирается минимальный незанятый элемент (h). Число (h) вычитается из всех незанятых строк, и прибавляется ко всем занятым столбцам. Таким образом, получаем следующую эквивалентную матрицу. В новой матрице все пометки сохраняются. После этого повторяют выполнение шага 3 в части «б».
Шаг 5. Производим построение цепочки из нулей. Начиная от последнего отмеченного 0’, двигаясь по столбцу к 0*, далее по строке к 0’, и так далее, пока это возможно. Внутри цепочки знаки * снимаются, а вместо штрихов ставятся звездочки. После этого все знаки, кроме *, снимаются (штрихи, плюсы), и возвращаются к шагу 2.