01
А
Астрономия
02
Б
Биология
03
Г
Гуманитарные науки
04
М
Математика и CS
05
Мд
Медицина
06
Нз
Науки о Земле
07
С
Сельское хозяйство
08
Т
Технические науки
09
Ф
Физика
10
Х
Химия и науки о материалах
Математика и Computer Science
7 декабря 2016

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

imagebroker/Stocktake/www.globallookpress.com

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

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

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

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

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

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

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

Комментарии

Все комментарии
Обсуждаемое