default ЭЛЕМЕНТЫ ТЕОРИИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ВЕНГЕРСКОГО АЛГОРИТМА

Ст. преподаватель Симоненко Андрей Валерьевич,

студент Хоменко Татьяна Владимировна

Национальный технический университет Украины «Киевский политехнический институт»

Киев, Украина

В работе рассматривается принцип повышения эффективности Венгерского алгоритма поиска максимального паросочетания для двудольного графа. Показано, что Венгерский алгоритм можно использовать для проектирования пространственных планировщиков задач в распределенных неоднородных вычислительных системах и глобальных GRID систем. Представлены теоремы, позволяющие для разреженных двудольных графов, отображающих претендование заявок на ресурсы, уменьшить временную сложность алгоритмов распределения заданий на ресурсы для неоднородных систем. Показано, что использование такого подхода уменьшает временную сложность Венгерского алгоритма с O(n3) до O(n1,5logn). Ввиду того, что предложенный алгоритм является адаптивным, а поиск максимального паросочетания выполнялся в разреженной матрице с коэффициентом заполнения меньше 30%, то статистическая временная сложность его меньше O(n1,5logn) и близка к линейной.