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

Российские ученые получили точную верхнюю оценку сложности решения задачи о сумме подмножеств методом ветвей и границ. Результаты работы были опубликованы в журнале The American Institute of Physics (AIP) Conference Proceedings.

Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов.

«Мы исследовали сложность решения задачи о сумме подмножеств методом ветвей и границ. Рассмотрена естественная модификация стандартного метода ветвей и границ, и найдено точное значение сложности решения задачи о сумме подмножеств с этой модификацией в наихудшем случае», — говорит профессор кафедры дискретной математики механико-математического факультета МГУ имени М.В. Ломоносова, доктор физико-математических наук Роман Колпаков.

Для решения поставленной задачи использовались комбинаторные результаты, касающиеся структуры единичного n-мерного куба.

«В дальнейшем предполагаются исследования проблемы оптимального выбора переменной ветвления для рассмотренной модификации метода ветвей и границ», — комментирует Роман Колпаков.

Исследования выполнены совместно с учеными из Вычислительного центра имени А.А. Дородницына Российской академии наук и Национального исследовательского университета «Московский институт электронной техники» (МИЭТ).

Пресс-релизы о научных исследованиях, информацию о последних вышедших научных статьях и анонсы конференций, а также данные о выигранных грантах и премиях присылайте на адрес science@indicator.ru.