Локальные элиминационные алгоритмы решения разреженных дискретных задач

Рассмотрен класс локальных алгоритмов элиминации, позволяющих на основе вычисления локальной информации получать глобальную информацию о решении всей задачи. Описана общая структура локальных алгоритмов элиминации, использующих окрестности элементов, структурный граф, описывающий структуру задачи, а также алгоритм элиминации. Представителями этого класса алгоритмов являются локальные алгоритмы декомпозиции задач дискретной оптимизации, алгоритмы несериального динамического программирования (НСДП), алгоритмы сегментной элиминации, методы древовидной декомпозиции. Показана возможность реализации локальных алгоритмов элиминации для решения оптимизационных задач. Библ. 34. Фиг. 5. Табл. 9.