|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ
Р. М. Колпаковab, М. А. Посыпкинb a МГУ им. М.В.Ломоносова
b Вычислительный центр им. А. А. Дородницына ФИЦ ИУ РАН
Аннотация:
Рассматривается легко реализуемая на практике стратегия распараллеливания при решении задачи о сумме подмножеств методом ветвей и границ, называемая рекурсивной стратегией распараллеливания. Сравниваются два различных варианта этой стратегии: фронтальный и сбалансированный. На примере частного случая задачи о сумме подмножеств показано, что сбалансированный вариант является более эффективным, чем фронтальный вариант. Более того, показано, что для рассматриваемого частного случая задачи о сумме подмножеств сбалансированный вариант является оптимальным по времени.
Ключевые слова:
метод ветвей и границ, параллельная вычислительная сложность, задача о сумме подмножеств.
Статья поступила: 25.06.2019 Переработанный вариант поступил: 06.09.2019
Образец цитирования:
Р. М. Колпаков, М. А. Посыпкин, “Об эффективной стратегии распараллеливания при решении задач о сумме подмножеств методом ветвей и границ”, Дискрет. матем., 31:4 (2019), 20–37; Discrete Math. Appl., 30:5 (2020), 313–325
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1526https://doi.org/10.4213/dm1526 https://www.mathnet.ru/rus/dm/v31/i4/p20
|
Статистика просмотров: |
Страница аннотации: | 374 | PDF полного текста: | 60 | Список литературы: | 46 | Первая страница: | 19 |
|