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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Построение минимального частичного дерева для полного
ориентированного графа
К. Г. Дмитриев, И. В. Солодовников «Информационные технологии в автоматизированных системах», МГИЭМ 8−910−425−04−06 (моб.), e-mail: dmitriev_kir@mail. ru
В статье рассматривается проблема нахождения минимального частичного дерева с отмеченной вершиной (корнем) для полного ориентированного графа, в котором известны все его вершины, ветви и их стоимости. В начале статьи дано общее описание проблемы. Далее описан алгоритм нахождения минимального частичного дерева, приводится возможность оптимизации алгоритма и вычислено время работы общего алгоритма.
Введение
В задачах маршрутизации в сетях, прокладке маршрутов для автомобилей, расчете цветов для графиков, производстве печатных плат возникает проблема создания определенной системы, состоящей из заданных узлов и ребер и имеющей некоторый узел в качестве центра. При чем построенная система должна обеспечивать наименьшие затраты при выполнении своих функциональных задач.
Рассмотрим такой пример. Предположим, что некоторой межнациональной компании в одном из своих многочисленных офисов требуется разместить центр управления сбытом. В функции этого центра входит рассылка сообщений своим агентам на местах (в остальных офисах). Один из возможных способов передачи сообщения мог бы сводиться просто к тому, что руководитель центра отправляет сообщение каждому агенту по телефону. Однако такой способ окажется слишком дорогостоящим. Дело в том, что центр может находиться в Москве, а агенты в Лондоне и Париже. При этом для руководителя было бы разумнее с точки зрения затрат не звонить каждому из агентов, а позвонить одному из них, например в Лондон, с тем чтобы лондонский агент затем позвонил в Париж.
По-видимому, наилучшим решением в подобных ситуациях было бы указание каждому агенту определенного абонента, которому он должен передать сообщение,
после того как сам его получил, т. е. создание определенной системы передачи сообщений.
Каким условиям должна удовлетворять система? Во-первых, любое лицо, входящее в систему, должно получать передаваемое сообщение ровно один раз (дублирование бессмысленно). Во-вторых, система должна обеспечивать наименьшие затраты при выполнении своих функций.
Построим граф, каждая вершина которого соответствует лицу, входящему в систему передачи сообщений, а каждая дуга представляет собой возможность передачи сообщения от одного лица другому. Каждой дуге поставлено в соответствие некоторое число (стоимость дуги), которое отражает стоимость звонка. Однако, в условиях задачи стоимость звонка, например, из Москвы в Лондон не равна стоимости звонка из Лондона в Москву. Поэтому в данном случае обязательно должна учитываться ориентация ребер, т. е. граф является ориентированным.
Также подобная задача может возникать в следующих областях:
• прокладка маршрутов для автомобилей-
• расчет цветов для графиков-
• маршрутизация в сетях. Например, задача о соединении некоторого количества городов в единую телефонную сеть с минимальной суммарной стоимостью соединений и единым центром-
• производство печатных плат. По аналогии с сетью: мы хотим соединить п узлов проводами с минимальной суммарной стоимостью так, что один из узлов будет являться центральным, и др.
Постановка задачи
В общем случае задачу можно сформулировать так. Пусть дан полный ориентированный граф (орграф) 0(У, Е), где V — множество вершин или узлов, Е -множество упорядоченных пар различных вершин, называемых дугами или ориентированными рёбрами. Полным ориентированным графом называется орграф, каждая пара вершин которого соединена ориентированным ребром. Пусть для каждого ребра (и, V), в котором вершина и является началом, а V — концом дуги, однозначно определено некоторое вещественное число w (u, v) — его стоимость. При чем w (u, v) Ф w (v, u). Такая ситуация может возникнуть от наличия препятствий на
пути или неравенстве стоимости пути в прямом и обратном направлении. Тогда возникает задача о нахождении минимального частичного дерева Т исходного графа О, содержащего все вершины графа. Частичным деревом в орграфе называется ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Весом (стоимостью) частичного дерева будем считать сумму весов всех его ребер. Таким образом, стоимость минимального частичного дерева меньше, либо равна стоимости любого из частичных деревьев для данного графа.
Алгоритм
Решение задачи может быть найдено следующим образом: на каждом следующем шаге алгоритма выбрать одну из вершин как корневую, построить частичное дерево, имеющее в качестве корня выбранную вершину и подсчитать суммарную стоимость всех ребер, образующих найденное частичное дерево. От выбора одной из вершин графа в качестве корневой зависит направление движения в графе и порядок обхода вершин. После перебора всех вершин и нахождения для них частичных деревьев, мы можем выбрать дерево, имеющее минимальную суммарную стоимость среди всех найденных частичных деревьев. Теперь встает проблема построения частичного дерева для отдельной вершины. Эта задача полностью решается с помощью алгоритма Крускаля [2], который использует жадную стратегию и позволяет за конечное количество шагов найти минимальное остовное дерево, то есть остов, у которого суммарный вес его ребер минимален.
Таким образом, исходная задача сводиться к поиску частичных деревьев для каждой вершины исходного графа и выбору минимального частичного дерева из найденных решений. То есть, мы должны применить п раз (п — количество вершин в графе) алгоритм Крускаля.
Приведем обобщенный алгоритм решения исходной задачи в псевдокоде.
Входными данными для алгоритма будет:
Исходный граф О = (У, Е), где V — множество вершин и Е — множество ребер графа-
Матрица M[NxN] - матрица стоимостей всех ребер графа G, N -количество вершин исходного графа. АЛГ main НАЧ
minStoimost := 32 767 iMin := 0 i := 1
Упорядочить ребра графа G в порядке не убывания их весов цикл пока i & lt-= N stoimost := Kruskal (i) если minStoimost & gt- stoimost то minStoimost:= stoimost iMin := i
кц
КОН АЛГ main
Этот обобщенный алгоритм иллюстрирует все вышесказанное. Мы проходим по массиву всех вершин, с помощью алгоритма Крускаля (функция Krusk (v) в нашем алгоритме) ищем частичное дерево для вершины v (считая ее корневой), возвращаем ее суммарную стоимость и сравниваем эту величину с переменной minStoimost, хранящей минимальную стоимость частичного дерева на данный момент. Если условие выполняется, сохраняем номер вершины, для которой нашли частичное дерево с меньшей суммарной стоимостью, в переменную iMin, а его стоимость — в переменную minStoimost. Также стоит отметить, что упорядочение ребер исходного графа происходит только один раз не в алгоритме Крускаля, а в общем алгоритме. Далее опишем алгоритм Крускаля в псевдокоде: АЛГ Kruskal НАЧ
T := пустое дерево, содержащее все n вершин графа i := 0
цикл пока число ребер в Т& lt- N-1 или ребра в G закончились если ребро допустимо для добавления то добавить его в T
кц
КОН АЛГ Кгшка!
Так как в исходной задаче рассматривается орграф, то алгоритм Крускаля должен учитывать ориентацию ребер и строить минимальный остов исходя из определения ориентированного дерева. При выполнении алгоритма может возникнуть такая ситуация, когда очередное кратчайшее ребро будет соединять две вершины одного и того же поддерева или в вершину будет входить более одного ребра или, если вершина выбрана в качестве корня, в нее входит хотя бы одно ребро. Добавлять это ребро к Т нельзя, поскольку полученный граф по определению не будет являться ориентированным деревом. Поэтом, прежде чем добавлять ребро к графу Т, надо проверить, является ли оно допустимым в указанном выше смысле. Такую проверку можно выполнить эффективно путем осуществления одного сравнения с использованием процедуры расстановки пометок [1]. Опишем эту процедуру.
Процедура пометки вершин
Первый шаг процедуры состоит в приписывании номеров ребрам графа О после процедуры сортировки (ребра нумеруются от 1 до Ы). Для организации проверки на возможность образования цикла (при добавлении нового ребра на очередном шаге алгоритма Крускаля) каждую вершину ху помечают парой (гу, ру). Первая пометка гу указывает «корень» поддерева, содержащего вершину ху. Первоначально Гу = ху для всех вершин ху. На некотором шаге да поддерева Т1 и Т2 сращиваются посредством добавления ребра а1 = (ха, хр) с вершиной ха из Т1 и вершиной хр из Т2. Если на этом шаге г1 — «корневая» пометка вершин в Т1, а г2 — «корневая» пометка вершин в Т2 и г1 & lt- г2 (например), то все вершины в Т2 должны «сменить» свои корневые пометки на г1 и два поддерева Т1 и Т2 «сольются» в единственное новое дерево Т1.
Вторая пометка ру, приписанная вершине ху, указывает вершину, предшествующую вершине ху, т. е. если (хк, ху) — дуга рассматриваемого поддерева, то Ру = хк. Для корневой вершины дерева такая пометка полагается равной нулю.
Опишем возможные операции и действия с пометками во время работы алгоритма:
А. Замена корня дерева
Если корнем дерева T является вершина г и нужно в качестве корня выбрать новую вершину xs, то такую «замену» г на xs, можно осуществить простым обращением ориентации дуг, принадлежащих цепи, идущей от г к xs, не меняя при этом ориентацию других дуг. Соответствующие изменения пометок будут таковы.
Изменение пометок «предшествования»
Пусть Xj = xs и 2 = Pj.
Положить XI = 2, а 2 = рг.
Шаг обновления: р1 = х^
Если Xi = г, то перейти к шагу 5, в противном случае положить xj¦ = хг и перейти к шагу 2.
Положить р- = 0, стоп.
Изменение корневых пометок
У всех вершин, имеющих корневую пометку г, заменить ее на пометку х-.
Б. Сращивание двух поддеревьев
Если осуществлено сращивание двух поддеревьев Т1 и Т2 (путем добавления ребра (ха, хД как было описано ранее), то в пометки необходимо внести следующие изменения:
Т Г и и _
У вершин с корневой пометкой г2 заменить эту пометку на г1.
Заменить в дереве Т2 корень г2 на хр (так, как было описано выше в пункте А), после чего изменить пометку «предшествования» у вершины хр с рр = 0 на рр = ха.
Таким образом, если рассматривается на очередном шаге алгоритма Крускаля ребро ак = (хг, Xj) и г = ¦ то это означает, что вершины хг и xj¦ принадлежат одному и тому же поддереву и добавление ребра ак приведет к появлению цикла. Следовательно, ребро ак в данном случае следует отбросить. Если гг Ф ¦ то ребро ак можно добавить к ребрам построенных поддеревьев. После этого следует срастить два поддерева, у которого вершины имеют корневые пометки г и ¦ применяя для этого метод, описанный выше в пункте Б.
Оптимизация алгоритма
Имеется возможность оптимизации алгоритма Крускаля [1]. Больше всего времени необходимо для выполнения процедуры сортировки ребер по не убыванию их весов. Для графа с т ребрами нужно выполнить т о2 т операций, чтобы
составить полный список ребер в порядке возрастания их весов. Однако полный список, вообще говоря, не требуется, так как весьма правдоподобно, что n-1 допустимых ребер, образующим МОД, будут найдены после просмотра только «верхней» части списка, содержащей r & lt- m ребер. Отсюда немедленно следует, что используемая процедура сортировки должна быть процедурой многократного обращения, дающее корректное расположение первых p ребер в конце p-го цикла обращения. С помощью такой процедуры кратчайшее ребро находиться посредством одного обращения к процедуре сортировки, затем осуществляется проверка ребра и ее добавление- далее происходит возвращение к предыдущим шагам и т. д. Процесс продолжается до тех пор, пока после некоторого чиста r таких проб не будут отобраны n-1 ребер, дающие МОД графа.
В конце такого процесса будут эффективно рассортированы только r ребер и при этом будут выполнены r log 2m операций. Остальные m-r ребер не потребуются.
Сложность алгоритма
В заключение раздела оценим сложность алгоритма. С памятью все очевидно: необходимо хранить расстояния между всеми парами вершин, т. е. потребуется C * n2 памяти, где C — некоторая константа. Таким образом, сложность алгоритма по памяти составляет O (n). Подсчитаем время работы алгоритма. Инициализация занимает время O (V), упорядочение ребер — O (E lg E). Далее производиться поиск частичных деревьев для каждой вершины, т. е. O (n * E) операций, в совокупности занимающих время O (nEa (E, V)), где, а — функция, обратная к функции Аккермана. Поскольку a (E, V) = o (lg E), то общее время работы нашего алгоритма составляет O (n E lg E). Очевидно, что при больших порядках числа вершин n время работы алгоритма будет сильно увеличиваться. Но оптимизации алгоритма можно добиться путем оптимизации процедуры сортировки.
Список литературы
1. Кристофидес Н. Теория графов. Алгоритмический подход.
2. Кормен Т., Лейзерсон Ч. Алгоритмы: построение и анализ.

ПоказатьСвернуть
Заполнить форму текущей работой