|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Сложность решения задачи о сумме подмножеств методом ветвей и границ с доминированием и мощностным отсевомстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
- Авторы: Посыпкин М.А., Колпаков Р.М., Тант Син Си Ту
- Журнал: Автоматика и телемеханика
- Номер: 3
- Год издания: 2017
- Первая страница: 96
- Последняя страница: 110
- DOI: http://mi.mathnet.ru/at14415
- Аннотация: Получена точная верхняя оценка сложности решения задачи о сумме подмножеств вариантом метода ветвей и границ специального вида. Cложность определяется как число рассматриваемых в процессе решения задачи подзадач. При этом применяется сокращение перебора за счет использования отношения доминирования. Построен пример задачи о сумме подмножеств, на котором полученная оценка достигается. Полученная оценка асимптотически в 2 раза меньше точной верхней оценки сложности решения этой задачи стандартным вариантом метода ветвей и границ.
- Добавил в систему: Колпаков Роман Максимович