5.4. Градиентные методы в теории графов

Иногда метод градиента позволяет получить вполне определенное решение «в лоб». Рассмотрим пример такой задачи из

области теории графов. В ней моделируются некоторые конкретные ситуации: проектирование телекоммуникационных или вычислительных сетей, обработка анкет, автоматическая классификация. Задача формулируется следующим образом:

Задан связный граф со стоимостями дуг Требуется построить частичное дерево , имеющее минимальную общую стоимость.

Дерево — это связный ациклическийэграф , по формуле Эйлера он содержит ребер.

Если использовать метод градиента, по которому нужно рассматривать дуги графа в порядке возрастания стоимостей, то получается первый алгоритм рещения этой задачи, предложенный Крускалем в 1956 г:

Алгоритм построения минимального дерева

(см. скан)

Замечание. Данный алгоритм содержит этапов.

5 4.1. Доказательство алгоритма Крускаля

Обозначим стоимость дерева (X, V), полученную в результате последней итерации описанного выше алгоритма, через Докажем, что не существует дерева, имеющего стоимость меньше . В самом деле, пусть среди множества деревьев имеется дерево (X, V, стоимость которого является наименьшей. Деревья (X, V и (X, V) имеют по ребер каждое. Пусть ребро первое из числа ребер, входящих в V и не входящих в V (если такого ребра не существует, то результат доказан). Добавление у, в V должно привести к образованию цикла. На этом цикле непременно существует ребро которое не входит в V? Но тогда граф также является деревом, поскольку содержит ) ребер и не имеет циклов При этом добавление в граф не приводит к образованию цикла, поскольку этот граф является поддеревом дерева V, а это означает, что стоимость стоимость (Здесь мы без потери общности предполагаем, что все стоимости различны.)

Из этого мы, наконец, получаем, что стоимость дерева равная стоимость меньше, чем предположительно оптимальная стоимость что противоречит исходному предположению.

Тип алгоритма, выбирающий объекты в том порядке, в котором они задаются оценочной функцией, получил название

«жадного». Он приводит к успеху во всех тех случаях, когда задача может быть сведена к определению пересечения двух семейств, принадлежащих к не зависящим друг от друга частям одного и того же множества, называемым матроидами (Gondran и Minoux, 1979).

Рис. 5.6. Граф системы линий электропередач.

Пример. Во французской системе высоковольтных линий электропередач обнаружить дерево, имеющее минимальную сумму расстояний, если все исходные данные представлены в графе, изображенном на рис. 5.6.

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

Распространение данного алгоритма на случай обобщенных поисковых задач приводит нас в область искусственного интеллекта, к методам, получившим название «эвристического поиска».