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