Щербина О. А.

Алгоритм выделения блочно-древовидной структуры в разреженных задачах дискретной оптимизации

Журнал: 
Страница: 
44
В статье предложен алгоритм выделения блочно-древовидной структуры для разреженных матриц. Реализован в виде программы на C++ и протестирован алгоритм Финкельштейна для выделения квазиблочных структур в разрежённых матрицах. Произведен сравнительный эксперимент для модифицированной и исходной версий алгоритма, показавший существенное уменьшение количества построенных блоков и размеров сепараторов для модифицированного алгоритма Финкельштейна.

Алгоритмы упорядочения переменных в локальном элиминационном алгоритме

Журнал: 
Страница: 
81
 В работе рассмотрены пять алгоритмов упорядочивания переменных для решения разреженньїх задач дискретной оптимизации с помощью алгоритма несериального динамического программирования. В результате проведенного вычислительного экс-перимента, во-первнх, было отмечено, что для решения разреженных задач дискрет­ной оптимизации, упорядочивание переменных оказывает значительное влияние на время решения задачи. Помимо этого, было показано, что различные звристики упо­рядочивания наиболее зффективны для различных классов задач.

Локальные элиминационные алгоритмы для задач удовлетворения ограничений

Авторы: 
Журнал: 
Страница: 
24
Рассмотрены локальные элиминационные алгоритмы для решения некоторых задач искусственного интеллекта, таких как задача удовлетворения ограничениям, задачи SAT, задачи раскраски графа.

Локальные элиминационные алгоритмы обработки запросов в базах данных

Авторы: 
Журнал: 
Страница: 
53
Рассмотрено использование локальных элиминационных алгоритмов (ЛЭА) для обработки запросов в реляционных базах данных. Обсуждаются особенности реализации локального алгоритма, использующего лишь прямую часть.

Метаэвристические алгоритмы для задач комбинаторной оптимизации

Авторы: 
Журнал: 
Страница: 
56
В настоящей работе сделан краткий обзор основных метаэвристических алгоритмов для задач комбинаторной оптимизации. Метаэвристики — это общие эвристики, позволяющие находить близкие к оптимальным решения различных задач оптимизации за приемлемое время. Метаэвристики пытаются объединить основные эвристические методы в рамках алгоритмических схем более высокого уровня, направленных на эффективное изучение пространства поиска. Метаэвристики включают две категории: метаэвристики локального поиска и эволюционные алгоритмы.

О распараллеливании локального элиминационного алгоритма

Журнал: 
Страница: 
56
Целью настоящей работы служит определение стратегий распараллеливания локального элиминационного алгоритма для разреженных задач дискретной оптимизации на основе использования современных вычислительных архитектур. Независимые подзадачи, соответствующие разным блокам, и подзадачи, соответствующие независимым ветвям обобщенного элиминационного дерева, могут решаться параллельно при помощи таких вычислительных архитектур, как многоядерные процессоры, графические процессоры (GPU) и GRID.  Для параллельной реализации локального элиминационного алгоритма

Средняя оценка эффективности локального алгоритма на классе всех блочно-древовидных структур с дополнительными ограничениями

Авторы: 
Журнал: 
Страница: 
80
В работе найдена асимптотика среднего значения вычислительной сложности локального алгоритма для решения блочно-древовидных задач дискретной оптимизации с дополнительными ограничениями многократного выбора одновариантного типа в более общем случае.

Элиминационные алгоритмы декомпозиции задач дискретной оптимизации

Авторы: 
Журнал: 
Страница: 
28
Рассмотрен класс элиминационных алгоритмов декомпозиции задач дискретной оптимизации, включающий локальные алгоритмы декомпозиции, алгоритмы несериального динамического программирования, алгоритмы сгментной элиминации, методы древовидной декомпозиции. Сделан обзор и описаны основные черты элиминационных алгоритмов декомпозиции, представляющих собой есьма перспективный подход к решению задач дискретной оптимизации большой размрности.