Математики исследовали сложность решения задачи о сумме подмножеств методом ветвей и границ

Российские ученые получили точную верхнюю оценку сложности решения задачи о сумме подмножеств методом ветвей и границ. Результаты работы были опубликованы в журнале The American Institute of Physics (AIP) Conference Proceedings. Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. «Мы исследовали сложность решения задачи о сумме подмножеств методом ветвей и границ. Рассмотрена естественная модификация стандартного метода ветвей и границ, и найдено точное значение сложности решения задачи о сумме подмножеств с этой модификацией в наихудшем случае», — говорит профессор кафедры дискретной математики механико-математического факультета МГУ имени М.В.Ломоносова, доктор физико-математических наук Роман Колпаков. Для решения поставленной задачи использовались комбинаторные результаты, касающиеся структуры единичного n-мерного куба. «В дальнейшем предполагаются исследования проблемы оптимального выбора переменной ветвления для рассмотренной модификации метода ветвей и границ», — комментирует Роман Колпаков. Исследования выполнены совместно с учеными из Вычислительного центра имени А.А. Дородницына Российской академии наук и Национального исследовательского университета «Московский институт электронной техники» (МИЭТ).