Страница публикации
Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач
Авторы: Семенов А.А., Заикин О.С.
Журнал: Вычисл. методы и программирование
Том: 9
Номер: 1
Год: 2008
Отчётный год: 2008
Издательство:
Местоположение издательства:
URL:
Аннотация: Для некоторых типов NP-трудных комбинаторных задач исследуются технологии поиска их решений посредством неполных алгоритмов, т.е. алгоритмов, конечность работы которых в общем случае не гарантируется. Речь идет об алгоритмах "программирования в ограничениях", использующих в своей работе идею пополнения базы ограничений с отбрасыванием нерелевантных ограничений. Сравниваются два подхода к решению ряда комбинаторных задач посредством неполных алгоритмов. Основой первого подхода является крупноблочное распараллеливание исходной задачи с последующим решением получаемых задач неполным алгоритмом на кластере. Во втором подходе исходная задача решается на одном процессора кластера (фактически на ПК) тем же самым алгоритмом. Показано, что в ряде случаев коэффициент ускорения, которое достигается в первом подходе, может существенно превосходить число процессоров кластера.
Индексируется WOS: 0
Индексируется Scopus: 0
Индексируется РИНЦ: 1
Публикация в печати: 0
Добавил в систему: