Статья в сборнике "Математические вопросы кибернетики" №18, Москва, 2013
Авторы:Колпаков Р.М., Посыпкин М.А.
Верхняя оценка числа ветвлений для задачи о сумме подмножеств
Аннотация:
В работе получена верхняя оценка сложности решения задачи о сумме подмножеств методом ветвей и границ с ветвлением по переменной с максимальным весом. Эта оценка зависит только от исходных данных задачи, тем самым позволяя определять максимальное необходимое для решения задачи число операций до начала решения задачи на основании ее исходных данных.
Ключевые слова:
задачи о ранце, метод ветвей и границ, вычислительная сложность