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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению

01.03.02 Прикладная математика и информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

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

Сидорова Татьяна

Нижний Новгород, 2019



СОДЕРЖАНИЕ

• Введение
• Глава 1
• Укладка деревьев минимальной длины
• Алгоритм укладки дерева минимальной длины
• Укладка деревьев минимальной ширины
• Алгоритм укладки дерева минимальной ширины
• Глава 2
• Заключение
• Список использованной литературы
• Приложение 1

Приложение 2



ВВЕДЕНИЕ

Решение широкого круга задач связано с размещением объектов различной природы в элементах определенных структур. Необходимость таких действий возникает, например, при проектировании расположения технологического оборудования предприятия, размещении радиоэлектронной аппаратуры на щитах и ??т. д. [7].Как правило, размещаемые объекты имеют определенный набор взаимосвязей, которые часто можно определить, используя граф. В этом случае задача состоит в том, чтобы найти такую ??нумерацию вершин графа, которая принесла бы наибольшее значение некоторому функционалу, определенному на множестве нумераций. В общем случае для задачи нумерации графов не существует эффективного алгоритма решения. В этой ситуации представляется уместным изучить частные случаи проблем нумерации для ограниченных классов графов (корневых деревьев), для которых существуют алгоритмы, работающие за линейное время [8].Задача нумерации деревьев является одной из возможных моделей для некоторых прикладных задач. Например, задача оптимизации вычисления функции, которая задается в виде корневого дерева. Укладка дерева минимальной длины соответствует такой организации расчетов, которая обеспечивает вычисление функции с минимальным общим временем хранения всех данных, а укладка дерева минимальной ширины соответствует организации расчетов, которая обеспечивает вычисление функции с использованием минимального количества ячеек памяти.Таким образом, возможность нахождения оптимальной укладки корневого дерева за линейное время делает задачу нумерации деревьев одной из самых интересных областей математики.

Объектом исследования в данной работе являются ориентированные корневые деревья. Предметом исследования является построение оптимальной нумерации ориентированных корневых деревьев.

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

Для достижения поставленной цели, были сформулированы следующие задачи:

1) Изучение теоретической базы: определение укладки ориентированного дерева, способов нахождения длины и ширины укладки дерева.

2) Изучение алгоритмов оптимальной по длине и ширине укладки ориентированных деревьев

3) Реализация алгоритма укладки дерева минимальной длины

4) Реализация алгоритма укладки дерева минимальной ширины

5) Тестирование программы, выполняющей оптимальную по длине и ширине укладку для различных деревьев.

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

Во второй главе приводится описание программы и результатов построения нумерации для различных деревьев.

ГЛАВА 1

Введем несколько ключевых определений.

Определение 1: Допустимая нумерация ориентированного графа[7] - это нумерациявершин данного графа, которая удовлетворяет следующему свойству:

,

где - номер вершины в нумерации .

Определение 2: Укладка дерева - это допустимая нумерация вершин ориентированного дерева [1].

Граф - это пара , состоящая из множества - множества вершин и множества - множества ребер, причем каждому ребру сопоставлена неупорядоченная пара вершин, то есть [4].

Ориентированный граф (или просто орграф) - это пара , состоящая из множества - множества вершин и множества - множества упорядоченных пар различных вершин, называемых дугами [5].

Укладка дерева характеризуется двумя параметрами: длина и ширина укладки.

Длина укладкидерева определяется следующим соотношением:

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

Допустим задано ориентированное корневое дерево [6] (Рис.1), для которого существуют две укладкии (Рис.2, Рис.3).

Рис.1

Рис.2

Рис.3

Найдем длину укладки дерева . Согласно формуле получаем следующее:

Найдем теперь длину укладки :

Таким образом, оптимальной по длине укладкой дерева , является укладка , так как имеет меньшую длину, по сравнению с укладкой .

Теперь определим для дерева , укладки , в которой номер вершины совпадает с ее именем, и вершины множество дуг :

Тогда ширина укладки дерева определяется следующим равенством:



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

Найдем ширину укладки дерева (Рис.2).

Пусть , тогда из следует, что .Количество дуг равно 0. Пусть теперь , тогда , количество дуг равно 1.

количество дуг - 2.

количество дуг - 1.

количество дуг - 2.

Таким образом, согласно , ширина укладки равна 2.

Найдем теперь ширину укладки дерева (Рис.3).

Аналогично нахождению ширины укладки :

, количество дуг - 0.

, количество дуг - 1.

количество дуг - 2.

количество дуг - 3.

количество дуг - 2.

Исходя из , ширина укладки равна 3.

Таким образом, оптимальной по ширине укладкой дерева , является укладка , так как имеет меньшую ширину, по сравнению с укладкой .

Теорема 1.

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

Доказательство:

Пусть есть некоторая укладка корневого ориентированного дерева . Пусть в данной укладке -корень поддерева с минимальным номером.

Покажем, что в оптимальной (до длине и ширине) укладке, вершины поддерева с корнем в вершине , имеют последовательную нумерацию.

Предположим, что вершины поддерева не имеют последовательную нумерацию (Рис.6).

Рис.6 Фрагмент укладки дерева

Теперь перенумеруем вершины поддеревьев с корнями в вершинах и (Рис.7).

Рис.7 Фрагмент укладки дерева

В итоге получаем новую укладку , в которой вершины поддерева с корнем в вершине имеют последовательную нумерацию.

Покажем теперь, что длина и ширина поддеревьев с корнями в вершинах и в укладке , по сравнению с укладкой , не увеличится. Пронумеруем вершины в укладках и как показано на Рис.8,9.

Рис.8 Фрагмент укладки

Рис.9 Фрагмент укладки

Длина укладки поддерева с корнем в вершине в укладке :

Длина укладки поддерева с корнем в вершине в укладке :

Длина укладки поддерева с корнем в вершине в укладке :

Длина укладки поддерева с корнем в вершине в укладке :

Ширина укладки поддерева с корнем в вершине в укладке :

, количество дуг - 0.

, количество дуг - 1.

количество дуг - 2.

количество дуг - 3.

Ширина укладки поддерева с корнем в вершине в укладке равна 3.

Ширина укладки поддерева с корнем в вершине в укладке :

количество дуг - 0.

количество дуг - 1.

Ширина укладки поддерева с корнем в вершине в укладке равна 1.

Ширина укладки поддерева с корнем в вершине в укладке :

, количество дуг - 0.

, количество дуг - 1.

количество дуг - 2.

количество дуг - 3.

Ширина укладки поддерева с корнем в вершине в укладке равна 3.

Ширина укладки поддерева с корнем в вершине в укладке :

количество дуг - 0.

количество дуг - 1.

Ширина укладки поддерева с корнем в вершине в укладке равна 1.

Таким образом, после проведенных вычислений, можно видеть, что длина укладки поддеревьев с корнями в вершинах и для укладкиуменьшилась, по сравнению с укладкой , а ширина осталась прежней.

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

Укладка дерева минимальной длины

При нахождении укладки корневого ориентированного дерева минимальной длины, из теоремы 1 следует, что есть возможность сузить область допустимых решений задачи укладки дерева минимальной длины на класс укладок, где каждое из поддеревьев укладывается последовательно. Другие укладки не рассматриваются.

Пусть у корневой вершины дерева есть потомки , которые являются корнями поддеревьев соответственно (Рис.10).

Рис.10

Чтобы найти минимальную по длине укладку дерева нужно определить такой порядок укладки поддеревьев этого дерева, при котором длина укладки всего дерева будет минимальной. Для этого достаточно чтобы

Покажем, что данное неравенство верно. Рассмотрим две укладки дерева (Рис.2,3). В укладке первым укладывается поддерево с наименьшим количеством вершин, в то время как в укладке - с наибольшим. Как было показано ранее, длина укладки меньше длины укладки . Таким образом, неравенство справедливо.

Исходя из полученного, можно сформулировать Теорему 2.

Теорема 2.

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

Алгоритм укладки дерева минимальной длины

Данный алгоритм основан на поиске в глубину.

1) Вначале нужно присвоить каждой вершине дерева метку , которая равна количеству вершин в поддереве, корнем которого она является. Чтобы присвоить метки используется поиск в глубину, который начинается из корня дерева. Во время поиска в глубину, при удалении вершины из стека, приписываем ей метку согласно следующим условиям:

· Если вершина - лист (то есть не имеет потомков), тогда

= 1;

· Если вершина - внутренняя, тогда

.

2) Для оптимальной нумерации вершин дерева , используется поиск в глубину с приоритетами, который так же начинается из корня дерева.

Во время поиска в глубину, путь из вершины идет в такую вершину , которая имеет наибольшую метку , так как ранее было доказано, что для оптимальной по длине укладки дерева нужно вначале выполнить укладку поддерева, которое имеет большее количество вершин.

При удалении вершины из стека, присваиваем ей номер = , где первоначально равно 1, и увеличиваем счетчик

на 1.

Трудоемкость алгоритма, как и трудоемкость поиска в глубину составляет

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

1) Выбираем вершину из тех, которые еще не были посещены, помечаем ее как посещенную и кладем ее в стек. Обозначим ее за .

2) Выбираем смежную с вершину из тех, что еще не были посещены, помечаем ее как пройденную, кладем в стек и запускаем алгоритм для вершин, смежных с . Как только все вершины данной ветки становятся посещенными, извлекаем вершины из стека и запускаем алгоритм для последней вершины в стеке.

3) Повторяем шаги 1) и 2) пока все вершины не будут пройденными.

Покажем, что сложность поиска в глубину

Суммарное время работы перебора всех вершин равно , то есть

, а общее время оставшейся работы равно . Таким образом общее время работы алгоритма равно . Так как для деревьев , то время работы поиска в глубину равно [2].

Попытаемся применить описанный выше алгоритм укладки дерева минимальной длины для выполнения оптимальной укладки дерева (Рис.11).



Рис. 11 Корневое дерево

1) Присвоим каждой вершине дерева метку .Кладем в стек корневую вершину дерева: Кладем в стек вершину - потомка корневой вершины : .Так как у вершины нет потомков, извлекаем ее из стека и присваиваем ей метку равную 1. Теперь в стеке снова находится только корневая вершина. Кладем в стек следующую вершину. Таким образом стек: Так как у есть потомки, продолжаем наполнять стек: У нет потомков, поэтому извлекаем данную вершину из стека и присваиваем ей метку равную 1. Теперь в стеке снова две вершины. Кладем в стек другого потока :

У два потомка, кладем в стек первого из них: У нет потомков, поэтому извлекаем эту вершину из стека, присваиваем ей метку 1 и кладем в стек другого потомка: , у которого так же нет потомков. Извлекаем из стека и присваиваем метку равную 1. Так как у нет больше потомков, то извлекаем эту вершину из стека и, согласно, второму пункту первого этапа алгоритма, присваиваем ей метку равную 3.

Аналогичным образом расставляем метки для других вершин дерева (Рис.12).

2) Выполним оптимальную нумерацию вершин дерева . Запускаем поиск с приоритетами из корневой вершины.Кладем в стек вершину Выбираем среди потомков этой вершины ту, которая имеет максимальную метку, присвоенную на предыдущем этапе. Такая вершина - (метка равна 8). Кладем в стек: У три потомка: . Среди них, имеет большую метка (равна 5), поэтому кладем в стек вершину : У два потомка, наибольшую метку имеет вершина , кладем ее в стек: И, наконец, у , так же два потомка, которые, однако, имеет одинаковые метки (равные 1), поэтому выбираем любого их них чтобы добавить в стек: Так как у нет потомков, извлекаем данную вершину из стека и присваиваем ей номер «1», увеличиваем счетчик на 1. Кладем в стек другого потомка вершины - . Так как у данной вершины нет потомком, мы сразу же извлекаем ее из стека и присваиваем ей номер «2», увеличиваем счетчик на 1.

Рис.12 Метки вершин дерева

Рис.13 Пример работы программы. Выполнение первого этапа алгоритма.

У нет больше потомков, извлекаем ее из стека, присваиваем ей номер «3», увеличиваем счетчик на 1. и переходим к другому потомку вершины . У вершины нет потомков и ее номер будет «4». Таким образом присваиваем каждой вершине дерева номер. В итоге

Рис.14 Оптимальная (по длине) укладка дерева

Рис.15 Пример работы программы.

Выполнение второго этапа алгоритма будет выполнена оптимальная по длине укладка корневого ориентированного дерева (Рис.14). Длина данной укладки равна 28 и соответствует суммарному времени хранения в памяти всех данных, необходимых для вычисления главной функции .

Укладка дерева минимальной ширины

При нахождении укладки корневого ориентированного дерева минимальной ширины, из теоремы 1 следует, что есть возможность сузить область допустимых решений задачи укладки дерева минимальной ширины на класс укладок, где каждое из поддеревьев укладывается последовательно. Другие укладки не рассматриваются.

Пусть у корневой вершины дерева есть потомки , которые являются корнями поддеревьев соответственно (Рис.16).

Рис. 16

При укладке поддеревьев вершины в порядке , длина укладки дерева равна

где - ширина оптимальной укладки поддерева , ().

Чтобы найти минимальную по ширине укладку дерева нужно определить такой порядок укладки поддеревьев этого дерева, при котором ширина укладки всего дерева будет минимальной. Для этого, достаточно чтобы

Покажем, что данное неравенство верно. Рассмотрим две укладки дерева (Рис.4,5). В укладке первым укладывается поддерево с наименьшей шириной, в то время как в укладке - с наибольше. Как было показано ранее, ширина укладки меньше ширины укладки . Таким образом, неравенство справедливо.

Теорема 3.

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

Алгоритм укладки дерева минимальной ширины

1) Вначале нужно присвоить каждой вершине дерева метку , которая равна ширине укладки поддерева . Чтобы присвоить метки используется поиск в глубину, который начинается из корня дерева. Во время поиска в глубину, при удалении вершины из стека, приписываем ей метку согласно следующим условиям:

· Если вершина - лист (то есть не имеет потомков), тогда

= 0;

· Если вершина - внутренняя, а , () ее поддеревья, для которых

то

Метка корня, при этом, соответствует минимальной ширине укладки дерева .

2) Для оптимальной нумерации вершин дерева , используется поиск в глубину с приоритетами, который так же начинается из корня дерева.

Во время поиска в глубину, путь из вершины идет в такую вершину , которая имеет наибольшую метку , так как ранее было доказано, что для оптимальной по ширине укладки дерева нужно вначале выполнить укладку поддерева, которое имеет большее количество вершин.

При удалее вершины из стека, присваиваем ей номер = , где первоначально равно 1, и увеличиваем счетчик

на 1.

Трудоемкость алгоритма, как и трудоемкость поиска в глубину составляет

Попытаемся применить описанный выше алгоритм для выполнения оптимальной укладки дерева (Рис.17).

1) Присвоим каждой вершине дерева метку .

Кладем в стек корневую вершинудерева :

Кладем в стек вершину -потомка корневой вершины : .

Так как у вершины есть потомок - вершина , добавляем ее в стек: .У вершины два потомка - вершины . Добавляем одну из этих вершин в стек: .Так как у нет потомков, то извлекаем эту вершину из стека и присваиваем ей метку равную 0. Кладем теперь в стек другого потомка - вершину : . Так как у есть два потомка - вершины , кладем в стек одного из них: .Так у нет потомков, извлекаем ее из стека и присваиваем ей метку равную 0. У другого потомка - так же нет потомков, поэтому метка этой вершины равна 0. Извлекаем из стека вершину и присваиваем ей метку равную . Таким образом, метка вершины равна 2.

Извлекаем из стека следующую вершину - и присваиваем ей метку равную . Метка вершины - 2. Извлекаем из стека вершину . Метка этой вершины равна .



Рис. 17 Корневое дерево

Таким образом, в стеке снова находится только корневая вершина: Аналогичным образом расставляем метки для других вершин дерева (Рис.18).

2) Выполним оптимальную нумерацию вершин дерева . Запускаем поиск с приоритетами из корневой вершины.

Кладем в стек вершину Выбираем среди потомков этой вершины ту, которая имеет максимальную метку, присвоенную на предыдущем этапе. Такая вершина - . Кладем ее в стек и среди потомков вершины выбираем ту, которая имеет максимальную метку.



Рис.18Метки вершин дерева

Рис.19 Пример работы программы. Выполнение первого этапа алгоритма.

Так как все потомки данной вершины имеют одинаковые метки, выбираем любого из них и кладем в стек: . Так как у вершины нет потомков, извлекаем ее из стека и присваиваем ей номер «1», увеличиваем счетчик на 1. Кладем в стек другого потомка вершины - вершину . Так как у вершины нет потомков, извлекаем ее из стека и присваиваем ей номер «2», увеличиваем счетчик на 1. Кладем в стек другого потомка вершины - вершину . Так как у вершины нет потомков, извлекаем ее из стека и присваиваем ей номер «3», увеличиваем счетчик на 1. Так как у вершины нет больше потомков, извлекаем ее из стека и присваиваем ей номер «4». Таким образом, в стеке снова находится только корневая вершина:

• Аналогичным образом нумеруем остальные вершины дерева и в итоге получаем оптимальную по ширине укладку данного дерева (Рис.20).Ширина полученной укладки равна 3 и соответствует минимальному количеству ячеек памяти, требующемуся для вычисления главной функции . длина ширина укладка дерево

Рис.20Оптимальная (по ширине) укладка дерева



Рис.21Пример работы программы. Выполнение второго этапа алгоритма.

Стоит отметить, что для приведенного на Рис.17 корневого дерева, оптимальная по ширине и оптимальны по длине укладки не совпадают. Ниже представлена оптимальная по длине укладка дерева (Рис.22).

Рис.22Оптимальная (по длине) укладка дерева

Рис.23Пример работы программы. Оптимальная (по длине) нумерация дерева



ГЛАВА 2

Для реализации описанных выше алгоритмов оптимальной по ширине и длине укладки корневых ориентированных деревьев использовалась среда MicrosoftVisualStudio, язык программирования: C++.

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

Корневое дерево в программе задается классом который имеет несколько полей и методов.

1) Поле имеет тип и предназначено для хранения имени вершины

2) Поле имеет тип и предназначено для хранения количества потомков одной вершины

3) Поляиимеют тип и предназначены для хранения меток, присваиваемых вершинам на первым этапе алгоритмов, описанных ранее. Поле хранит метку, присваиваемую вершине на первом этапе алгоритма для оптимальной по длине укладки дерева, поле хранит метку, присваиваемую вершине на первом этапе алгоритма для оптимальной по ширине укладки дерева.

4) Поле имеет тип ихранит номер, присваиваемый вершине на втором этапе обоих алгоритмов.

5) Поле - вектор типа , который хранит потомков вершины.

6) Метод «Birth» добавляет потомка вершины в вектор потомков и увеличивает счетчик потомков «num» на 1.

7) Метод осуществляет поиск вершины, сравнивая имя вершины, переданное в функцию, с именами потомков вершины, лежащих в векторе

8) Метод «Add» создает нового потомка вершины и добавляет его в массив потомков, так же как «Birth» увеличивает счетчик потомков на 1. На вход функции подается имя будущего потомка, которое потом записывается в поле потомка.

9) Метод «Labels_Length» выполняет первый этап алгоритма оптимальной по длине укладки корневого ориентированного дерева.В начале значение метки . Затем метод осуществляет рекурсивный поиск в глубину, который начинается из корневой вершины дерева и присваивает вершинам метки.Если количество потомков равно 0, то есть вектор пустой, то метод присваивает вершине метку равную 1, еслиу вершины есть хоть один потомок, тогда метка - это сумма всех меток потомков вершины + 1. То есть количество вершин в поддереве, корнем которой данная вершины является. Примеры работы данного метода можно видеть на Рис. 24-35.

Рис.24

Рис.25 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной длины

Рис. 26



Рис.27 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной ширины

Рис. 28

Рис.29 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной длины

Рис.30



Рис.31 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной ширины

Рис.32



Рис.33 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной длины

Рис.34



Рис.35 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной ширины

10) Метод выполняет первый этап алгоритма оптимальной по ширине укладки корневого ориентированного дерева. В начале значение метки . Так как метка вершины - это максимум из меток ее потомков и количества потомков, пусть максимальное значение изначально равно количеству потомков вершины . Метод осуществляет рекурсивный поиск в глубину, который начинается из корневой вершины дерева и присваивает вершинам метки. Если метка потомка вершины больше, чем количество потомков, то присваиваем вершине метку ее потомка. Если количество потомков вершины равно 0, то метод присваивает вершине метку равную 0. Примеры работы данного метода можно видеть на Рис. 36-43.



Рис.36

Рис.37 Пример работы программы. Выполнение второго этапа алгоритма

Для данного дерева оптимальная по длине и по ширине укладки совпадают.



Рис.38

Рис.39 Пример работы программы. Выполнение второго этапа алгоритма укладки дерева минимальной длины



Рис.40

Рис.41 Пример работы программы. Выполнение второго этапа алгоритма укладки дерева минимальной ширины



Рис. 42

Рис.43 Пример работы программы. Выполнение второго этапа алгоритма

Для данного дерева укладки минимальной ширины и длины совпадают.

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

Функция генерирует имя для вершины. На вход подается - число букв в имени вершины. Затем генерируется случайное число, берется остаток от деления сгенерированного числа на длину строки - алфавита и затем в записывается буква, которая находится в алфавита на полученном месте.

Функция «» выполняетгенерацию корневых деревьев. На вход подается количество вершин и указатель на корневую вершину. Функция рекурсивно генерирует количество потомков каждой вершины и каждой из них, присваивается имя, сгенерированное с помощью функции, описанной ранее.

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

Функцияпредназначена для выполнения второго этапа обоих алгоритмов. Метод осуществляет рекурсивный поиск в глубину с приоритетами. На вход подается корневая вершина и переменная типа , в зависимости от значения которой, будет выполняться второй этап либо первого, либо второго алгоритма. Для того чтобы осуществить поиск в глубину с приоритетами, отсортируем потомков конкретной вершины по меткам, присвоенным на первом этапе алгоритмов. Алгоритм, применяемый для сортировки - сортировка подсчетом, которая работает за линейное время [3, c.225]. Кроме того, сортируются не все вершины графа, а только потомки конкретной вершины. После того, как потомки отсортированы, запускается поиск в глубину, который расставляет вершинам номера. Подробнее примеры работы программы можно увидеть в Приложении 1. Кроме того, из таблицы можно видеть, что алгоритмы действительно работают за линейное время:



Количество вершин	Алгоритм укладки мин. Длины (сек.)	Алгоритм укладки мин. Ширины (сек.)
500	0,06	0,0000005
1000	0,1	0,0000011
5000	0,52	0,0000053
10000	1,2	0,000012
50000	5,5	0,000058
100000	11,36	0,00027



ЗАКЛЮЧЕНИЕ

Предметом исследования является оптимальная нумерация ориентированных корневых деревьев. Допустимая нумерация ориентированного графа - это нумерациявершин данного графа , которая удовлетворяет следующему свойству:

,

где - номер вершины в нумерации .

Укладка дерева - это допустимая нумерация вершин ориентированного дерева .

Длину укладки дерева можно найти по следующей формуле:

Ширину укладки дерева можно найти по следующей формуле:

.

Кроме того, в ходе работы были сформулированы алгоритмы для выполнения оптимальной по длине и ширине укладки ориентированного дерева, которые основаны на поиске в глубину.

Приведенные алгоритмы были успешно реализованы, что подтверждается результатами, описанными во второй главе. Для написания реализации алгоритмов использовалась средаMicrosoftVisualStudio, язык С++. Таким образом, цель работы достигнута.



СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1) Котов, В.М. Укладка деревьев / В.М. Котов, Е.П Соболевская - Минск: Ежеквартальный научно-методический журнал «Информатизация образования», 2012. - 10 c.

2) Калинин, П.Поиск в глубину / П. Калинин, 2008. - 24 c.

3) Кормен, Т. Алгоритмы. Построение и анализ. Второе издание / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - М.: Издательский дом «Вильямс», 2005. - 1296 с. - ISBN 5-8459-0857-4

4) Bondy, J.A. Graph Theory / J.A. Bondy, U.S.R. Murty - New York: Springer, 2008. - 655 с. -ISBN 978-1-84628-970-5

5) Gross, L. J. Handbook of graph theory / L. J. Gross, J. Yellen - Boca Raton: CRC Press LLC, 2004. - 1155 с. - ISBN 1-58488-090-2

6) Bang-Jensen, J. Digraphs / J.Bang-Jensen, G. Gutin - New York: Springer Science + Business Media, 2009. - 812 с. - ISBN 978-1-84800-997-4

7) Донец, Г. А.Об одной задаче нумерации вершин деревьев / Г. А. Донец, 2010. - 8c.

8) Шелухин, Д. С.Минимальные нумерации корневых ориентированных деревьев с выделенной вершиной / Д. С. Шелухин, 2012. - 8c.



Приложение 1

Рис.44

Рис.45 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной длины

Рис. 46



Рис.47 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной ширины

Рис. 48

Рис.49 Пример работы программы. Выполнение второго этапа алгоритма укладки дерева минимальной длины

Рис.50

Рис.51 Пример работы программы. Выполнение второго этапа алгоритма укладки дерева минимальной ширины

Рис.52

Рис.53 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной длины

Рис.55 Пример работы программы. Выполнение первого этапа алгоритма укладки дерева минимальной ширины



Рис.56

Рис.57 Пример работы программы. Выполнение второго этапа алгоритмов укладки дерева минимальной длины и ширины

Для данного примера укладка минимальной ширины и длины совпадают.

Приложение 2

Листинг кода

#include<iostream>

#include<string>

#include<algorithm>

#include<vector>

#include<stdlib.h>

#include<time.h>

#include<Windows.h>

usingnamespace std;

int c = 0;

int pos = 0;

char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

classPerson

{

public:

string name;

vector<Person*> next;

vector<Person*> sort;

vector<int> help;

int num, mark, pos, mark_width, length;

Person()

{

num = 0;

mark = 0;

mark_width = 0;

length = 0;

next.clear();

sort.clear();

}

Person* Search(stringName)

{

for (int i = 0; i < num; i++)

{

if (next[i]->name ==Name)

{

return next[i];

}

}

return 0;

}

void Add(stringName)

{

Person *child;

child = newPerson;

next.push_back(child);

child->name =Name;

num++;

}

void Birth(Person *child)

{

next.push_back(child);

num++;

}

int Labels_Length()

{

mark = 1;

c++;

for (int i = 0; i < num; i++)

{

mark+=next[i]->Labels_Length();

}

for (int i = 0; i < c; i++)

{

cout <<"\t";

}

cout << name <<" "<< mark << endl;

c--;

return mark;

}

int C_Length()

{

for (int i = 0; i < num; i++)

{

length += next[i]->C_Length();

}

return length;

}

int Labels_Width()

{

c++;

int max = num;

for (int i = 0; i < num; i++)

{

next[i]->Labels_Width();

if (next[i]->mark_width > max)

{

max = next[i]->mark_width;

}

}

mark_width = max;

for (int i = 0; i < c; i++)

{

cout <<"\t";

}

cout << name <<" "<< mark_width << endl;

c--;

return mark_width;

}

};

int Num(Person *parent, boola=1)

{

c++;

if (a == 1)

{

for (int i = 0; i <parent->mark; i++)

{

parent->help.push_back(0);

parent->sort.push_back(0);

}

for (int i = 0; i <parent->num; i++)

{

parent->help[parent->next[i]->mark]++;

}

for (int i = 1; i <parent->mark-1; i++)

{

parent->help[i] = parent->help[i] + parent->help[i - 1];

}

for (int i = parent->num - 1; i >= 0; i--)

{

parent->help[parent->next[i]->mark]--;

parent->sort.at(parent->help[parent->next[i]->mark]) = parent->next[i];

}

}

else

{

for (int i = 0; i <parent->mark_width+1; i++)

{

parent->help.push_back(0);

parent->sort.push_back(0);

}

for (int i = 0; i <parent->num; i++)

{

parent->help[parent->next[i]->mark_width]++;

}

for (int i = 1; i <parent->mark_width+1; i++)

{

parent->help[i] = parent->help[i] + parent->help[i - 1];

}

for (int i = parent->num - 1; i >= 0; i--)

{

parent->help[parent->next[i]->mark_width]--;

parent->sort.at(parent->help[parent->next[i]->mark_width]) = parent->next[i];

}

}

for (int i = parent->num - 1; i >= 0; i--)

{

Num(parent->sort[i],a);

}

for (int i = 0; i < c; i++)

{

cout <<"\t";

}

pos++;

parent->pos = pos;

cout <<parent->name <<" "<< pos << endl;

c--;

return pos;

}

int Length(Person *parent)

{

parent->length = 0;

for (int i = 0; i <parent->num; i++)

{

Length(parent->next[i]);

parent->length += parent->pos - parent->next[i]->pos;

}

returnparent->length;

}

string GenName(intn)

{

string name;

int len = strlen(alphabet);

for (int j = 0; j <n; j++)

{

name.push_back(alphabet[rand() % len]);

}

return name;

}

void Gen(intnum, Person* parent)

{

if (num==0)

{

return;

}

Person* p1;

int n, N, n1;

n = rand() % num + 1;

if (n > 4)

{

n = 4;

}

N = num - n;

for (int i = 0; i < n; i++)

{

parent->Add(GenName(1));

if (i == n - 1)

{

n1 = N;

}

else

{

n1 = rand() % (N + 1);

}

p1=parent->next.back();

N = N - n1;

Gen(n1, p1);

}

}

void main()

{

srand((unsigned)time(NULL));

Person p1;

p1.name ="A";

Gen(19, &p1);

//Пример задания графа вручную

p1.name ="a";

p1.Add("c");

p1.Add("b");

Person *hp;

hp = p1.Search("c");

hp->Add("d");

hp->Add("e");

p1.Labels_Length();

cout << endl;

cout << endl;

cout << endl;

Num(&p1);

cout << endl;

Length(&p1);

cout << endl;

cout <<"Length= "<<p1.C_Length() << endl;

p1.Labels_Width();

cout << endl;

cout << endl;

cout << endl;

Num(&p1,0);

cout << endl;

system("pause");

}

Размещено на Allbest.ru

...