|
Автоматика и телемеханика, 2017, выпуск 3, страницы 96–110
(Mi at14415)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Системный анализ и исследование операций
Сложность решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевом
Р. М. Колпаковab, М. А. Посыпкинb, Си Ту Тант Синc a Московский государственный университет им. М. В. Ломоносова
b Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН, Москва
c Московский институт электронной техники
Аннотация:
Получена точная верхняя оценка сложности решения задачи о сумме подмножеств вариантом метода ветвей и границ специального вида. Cложность определяется как число рассматриваемых в процессе решения задачи подзадач. При этом применяется сокращение перебора за счет использования отношения доминирования. Построен пример задачи о сумме подмножеств, на котором полученная оценка достигается. Полученная оценка асимптотически в 2 раза меньше точной верхней оценки сложности решения этой задачи стандартным вариантом метода ветвей и границ.
Ключевые слова:
задача о ранце, метод ветвей и границ, вычислительная сложность, отношение доминирования.
Образец цитирования:
Р. М. Колпаков, М. А. Посыпкин, Си Ту Тант Син, “Сложность решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевом”, Автомат. и телемех., 2017, № 3, 96–110; Autom. Remote Control, 78:3 (2017), 463–474
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at14415 https://www.mathnet.ru/rus/at/y2017/i3/p96
|
Статистика просмотров: |
Страница аннотации: | 249 | PDF полного текста: | 120 | Список литературы: | 42 | Первая страница: | 16 |
|