Аспирант и соискатель, № 5, 2011 Автоматизация и управление технологическими процессами и производствами Аунг Со Лвин, аспирант Национального исследовательского университета «МИЭТ» ВЕНГЕРСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ НАВИГАЦИИ И УПРАВЛЕНИЯ ДВИЖЕНИЕМ Венгерский алгоритм – алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). <...> Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари). <...> Задача – получить наилучшее распределение некоторого числа работ между таким же числом исполнителей. <...> При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. <...> Наиболее эффективным методом ее решения является венгерский метод. <...> Задача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т. д. <...> Необходимо распределить задания между машинами так, чтобы суммарное время выполнения было минимальным. <...> Будем решать задачу с помощью венгерского алгоритма. <...> Получение 0 в каждой строке и столбце матрицы. <...> Найдем минимальный элемент (MIN) в каждой строке и вычтем его из всех элементов строки. <...> Простой граф: два множества вершин (X и Y) и отображение G. <...> Число дуг равно числу нулей Процедура 3. <...> Если не все вершины Х отобразились в Y, перейдем к процедуре 4. <...> Вспомним задачу нахождения максимального потока в транспортной сети! <...> Из «худой» вершины идем вперед по «худым» дугам, назад по «жирным» и помечаем вершины индексом α. <...> Число вершин в минимальной опоре равно числу дуг в максимальном паросочетании !!! <...> В опору войдут вершины Х, не помеченные α, и вершины Y, помеченные α. <...> Вычеркнем из матрицы строки и столбцы опоры. <...> В оставшейся подматрице <...>