Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранцестатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 23 сентября 2021 г.
Аннотация:Работа посвящена одной из возможных реализаций метода ветвей и границ на многопроцес#
сорных системах с распределенной памятью – фронтальному алгоритму. Исследование слож#
ности фронтального алгоритма проводится для семейства задач о булевом ранце содним огра#
ничением в предположении, что число процессоров неограничено. Получены формулы,
определяющие порядок роста сложности фронтального алгоритма с ростом размерности за#
дач из рассматриваемого семейства. Исследовано асимптотическое поведение ускорения и
эффективность использования ресурсов с увеличением числа переменных задачи.