Страница публикации

Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач

Авторы: Семенов А.А., Заикин О.С.

Журнал: Тр. Междунар. науч. конф. (ПАВТ’08, Санкт-Петербург, 28 января-1 февраля 2008 г.)

Том:

Номер:

Год: 2008

Отчётный год: 2008

Издательство: Издат. центр ЮУрГУ

Местоположение издательства: Челябинск

URL:

Аннотация: Для некоторых типов NP - трудных комбинаторных задач исследуется подход к их решению посредством неполных алгоритмов, то есть алгоритмов, конечность работы которых в общем случае не гарантируется. Речь идет об алгоритмах «программирования в ограничениях», использующих в своей работе идею пополнения базы ограничений с отбрасыванием нерелевантных ограничений. Сравниваются два подхода к решению ряда комбинаторных задач посредством неполных алгоритмов: исходная задача решается на последовательном компьютере; используется крупноблочное распараллеливание исходной задачи с последующим решением получаемых задач неполными алгоритмами на кластере. Показано, что второй подход приводит в ряде случаев к сверхлинейному ускорению по времени в сравнении с первым.

Индексируется WOS: 0

Индексируется Scopus: 0

Индексируется РИНЦ: 1

Публикация в печати: 0

Добавил в систему: