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

Аннотация

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

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

2019-69-2
2019-69-1
2018-68-4
2018-S1

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