6.2.3.6. Адаптивная агрегация графа с переменными свойствами в детерминированной среде

Рассмотрим случай, когда параметры (6.2.4) агрегируемого графа Г изменяются во времени или под действием среды:

причем эти зависимости детерминированны и среда изменяется достаточно медленно, т. е. производная мала по модулю.

Тогда оптимальная агрегация (разрезание) U (6.2.16) также изменяется и возникает задача ее отслеживания, т. е. адаптации к изменяющимся параметрам графа. Это обычная задача адаптации к новым условиям, причем ограничения могут нарушаться. Алгоритм адаптивной агрегации должен иметь возможность как устранять возникающие нарушения ограничений так и минимизировать критерий.

Воспользуемся описанным выше алгоритмом устранения нарушения ограничений (см. п. 6.2.3.3) и алгоритмом поиска оптимального разрезания (см. п. 6.2.3.4). Связь этих алгоритмов показана на рис. 6.2.3 и 6.2.4 пунктирными стрелками. В алгоритме устранения нарушения ограничений (см. рис. 6.2.3) таких стрелок две: Стрелка а обозначает переход при устранении ограничений, а стрелка б — при невозможности это сделать. В последнем случае для решения задачи необходимо расширение ресурсов С (6.2.13).

Блок-схема адаптации, объединяющая оба рассмотренных выше алгоритма, приведена на рис. 6.2.8. Здесь стрелки соответствуют пунктирным стрелкам на рис. 6.2.3.

Рис. 6.2.8. Блок-схема адаптивной агрегации изменяющегося графа.

Как видно, алгоритм адаптации работает следующим образом. После устранения нарушения ограничений (или проверки их выполнения) производится локальная оптимизация агрегации графа, за которой снова следует проверка выполнения ограничений, и т. д. Эффективность работы такого алгоритма гарантируется медленностью изменения параметров (6.2.77) графа. Поэтому оптимальную агрегацию удается отследить описанным образом.

Однако часто среда X изменяется стохастически в соответствии со своими неизвестными, но определенными статистическими свойствами, которые удобно описывать плотностью распределения состояний среды. Рассмотрим этот случай.