Распределенные вычислительные системы
Оптимизационные задачи и распределенная среда
Р.М.Колпаков, М. А. Посыпкин "Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце"
Прикладные задачи распределенных вычислений
Р.М.Колпаков, М. А. Посыпкин "Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце"

Аннотация

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

Скачать статью в формате pdf

2020-70-2
2020-70-1
2019-69-4
2019-69-3

© ФИЦ ИУ РАН 2008-2018. Создание сайта "РосИнтернет технологии".