6.2.3. Адаптивная агрегация графа методами случайного поиска

6.2.3.1. Методы агрегации (разрезания) графа

Существует целый ряд методов агрегации (разрезания) графа; их подробный обзор приводится в работе [111]. Эти методы подразделяются на детерминированные и стохастические (типа случайного поиска).

Детерминированные методы используют для разрезания графа известный метод ветвей и границ [27, 66, 201], а также различного рода эвристики, которые позволяют эффективно решать поставленную задачу [1, 2, 38, 106, 129, 147, 224]. Однако такие методы не позволяют решать глобальные задачи большой размерности, т. е. определяют лишь одно локальное решение. Именно это обстоятельство заставляет искать стохастические подходы к решению задачи о разрезании графа большой размерности.

Стохастический подход к разрезанию графа связан с намеренным введением элемента случайности в процесс разрезания. Это может быть сделано по-разному. Простейшей схемой является рандомизация перебора [37, 53, 97].

Рассмотрим стохастические методы, решающие задачу разрезания графа методом случайного поиска, т. е. путем введения случайного шага в процесс разрезания с последующей оценкой его эффективности.