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

Аннотация

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

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

2024-74-3
2024-74-2
2024-74-1
2023-73-4

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