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

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

Тип публикации: Материал конференции

Тип материала: Текст

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

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

Язык публикации: russian

Номера страниц: 232–244

Количество страниц: 13

Год публикации: 2008

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

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

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

Адрес издателя: Челябинск

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

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

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

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

Индексируется УБС: Нет

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

Индексируется ВАК: Нет

Индексируется CORE: Нет