Свириденко А. В.

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

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

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

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