close

Вход

Забыли?

вход по аккаунту

?

kursach nadin 2(1)

код для вставкиСкачать
Содержание
1. Введение............................................................................................3
2. Постановка задачи..........................................................5
3. Прямой алгоритм...........................................................13
4. Список литературы........................................................17
5. Приложение №1. Структурное проектирование.....................17
6. Приложение №2. Текст программы....................................17
7. Приложение №3............................................................17
Задача о проведении дорог
1. Введение
Очень много задач решаются методами теории графов. Приведем несколько примеров.
1. Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.
2. Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением.
3. Сеть компьютеров, соединенных проводными линиями связи.
4. Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников.
5. Генеалогические деревья, указывающие родственные отношения между людьми.
6. и т.д.
Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Основной объект теории графов-граф и его обобщения.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
В курсовой работе будет рассматриваться задача о проведении дорог. Нам нужно сделать, что бы дороги, которую мы хотим проложить через города или улицы, по километражу были максимально короткими. В результате будет потрачено меньше времени и средств на строительство дорог. Это го результата можно добиться при помощи разных алгоритмов и методов, н-р:
1. Алгоритм Дейкстры;
2. Алгоритм Флойда-Уоршелла;
3. Алгоритм Форда-Беллмана;
4. Расстановка меток;
5. Коммуникационная сеть минимальной длины (дерево кратчайших расстояний), и т.д.
В данной курсовой работе мы будем рассматривать последний метод, т.е. коммуникационная сеть минимальной длины (дерево кратчайших расстояний).
Коммуникационная сеть минимальной длины (или дерево кратчайших расстояний) - это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети, то есть возможность попасть из любого узла в любой другой узел.
Целью работы является изучение метода решения поставленной задачи и написание программы, которая реализует данный метод и позволяет находить кратчайший путь между городами или улицами .
2. Постановка задачи
Рассмотрим задачу о проведении дорог, как задачу на графах.
Теория графов - раздел дискретной математики, изучающий свойства графов. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, перекрёстки, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Представление участка в виде графа (рисунок).
Граф - базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины). Граф является ориентированным, если для каждого ребра задано направление, в котором возможно движение по этому ребру. Если движение возможно в обоих направлениях, то граф называется неориентированным.
Граф называется взвешенным, если каждому ребру поставлено в соответствие некоторое число (вес).
Граф называется связным, если из любой его вершины существует путь (не обязательно состоящий из одного ребра) в любую другую.
На рисунке изображен неориентированный, несвязный, невзвешенный граф.
Часть графа, которая является связной, называется компонентой связности. В графе, изображенном на рисунке две компоненты связности.
Степенью вершины (в неориентированном графе) называется количество выходящих из нее ребер.
Полустепенью вершины (в ориентированном графе) называется количество выходящих из нее ребер (полустепень исхода) или количество входящих ребер (полустепень захода).
Истоком (в ориентированном графе) называется вершина, в которую не входит ни одно ребро.
Стоком (в ориентированном графе) называется вершина, из которой не выходит ни одного ребра.
Петлей называется ребро, соединяющее вершину с самой собой.
Простым путем в графе называется путь, в котором ни одно ребро не встречается дважды.
Циклом называется путь, не проходящий дважды через одну и ту же вершину.
Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные. Конечная последовательность необязательно различных рёбер E1,E2,...En называется маршрутом длины n, если существует последовательность V1, V2, ... Vn необязательно различных вершин, таких, что Ei = (Vi-1,V i ).
Если совпадают, то маршрут замкнутый.
Маршрут, в котором все рёбра попарно различны, называется цепью.
Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.
Маршрут, в котором все вершины попарно различны, называется
простой цепью.
Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.
Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины. Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется компонентой связности . Несвязный граф имеет, по крайней мере, две компоненты связности.
Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.
Маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами, называется обходом графа.
Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj.
Свойства связных графов. 1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.
2. Связный граф , имеющий К вершин , содержит по крайней мере К-1 ребро. 3. В связном графе любые две простые цепи максимальной длины имеет по крайней мере одну общую вершину.
4. В графе с N вершинами и К компонентами связности число рёбер не превышает 1/2(N-K)(N-K+1).
5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).
Вершина, Узел - базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G). Перекрёсток - вершина.
Ребро графа - базовое понятие. Ребро соединяет две вершины графа. Дорога - ребро.
Дуга- это ориентированное ребро.
Взвешенный граф - граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Вес ребра - значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес - вещественное число, в таком случае его можно интерпретировать как "длину" ребра. Длина дороги - вес ребра.
Деревом называется граф, не содержащий циклов.
Дерево - одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Определения:
* Корневой узел - самый верхний узел дерева (узел 2 на примере).
* Корень - одна из вершин, по желанию наблюдателя.
* лист, листовой или терминальный узел - узел, не имеющий дочерних элементов (узлы 2, 4, 5, 11).
* Внутренний узел - любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (2, 7, 5, 6, 9).
Дерево считается ориентированным, если в корень не заходит ни одно ребро.
Эквивалентные определения дерева. 1. Связный граф называется деревом, если он не имеет циклов. 2. Содержит N-1 ребро и не имеет циклов.
3. Связный и содержит N-1 ребро.
4. Связный и удаление одного любого ребра делает его несвязным.
5. Любая пара вершин соединяется единственной цепью.
6. Не имеет циклов и добавление одного ребра между любыми двумя
вершинами приводит к появлению одного и только одного цикла.
Упорядочивание деревьев Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами илиупорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска - одно из разновидностей упорядоченного дерева.
Представление деревьев Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы В теории графов дерево - связанный ациклический граф. Корневое дерево - это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения "родитель-потомок". Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.
Методы обхода Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем - правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Общие операции * вставка нового элемента в определённую позицию;
* вставка поддерева;
* добавление ветви дерева (называется прививкой);
* нахождение корневого элемента для любого узла;
* нахождение наименьшего общего предка двух вершин;
* перебор всех элементов дерева;
* перебор элементов ветви дерева;
* поиск изоморфного поддерева;
* поиск элемента;
* удаление ветви дерева (называется обрезкой);
* удаление поддерева;
* удаление элемента.
Каждый узел дерева должен иметь в точности один родительский узел (разумеется, за исключением корневого узла - для него родителя не существует). В сети же любой узел (иногда называемый вершиной) может быть соединен связями (которые иначе называются дугами или ребрами) с произвольным количеством других узлов. В зависимости от поставленной задачи связи могут быть ориентированными, иначе говоря, направленными (указывающими одно направление), либо неориентированными, или ненаправленными (можно переходить по данной связи в обоих направлениях), а понятий родительского узла и корня не существует.
Во многих представлениях связь также характеризуется некоторой величиной − весом (иногда называемой cost − цена, distance − расстояние или length − длина), которую можно понимать как стоимость перехода по данной дуге.
3. Простой алгоритм
Рассмотрим пример о построении дорог: В городе возможно строительство новых дорог. Инженеры определили идеальные места расположения этих дорог. Эти места представлены узлами сети , приведенном ниже рисунке. Дуги сети отражают возможные альтернативы дорог. Инженеры хотят минимизировать общую протяженность дорог, которые требуется проложить в городе, и при этом обеспечить доступ ко всем узлам. Какова минимальная протяженность дорог?
Определение такой системы связи минимальной длины представляет собой пример дерева кратчайших расстояний. Сеть применительно к этой задаче с различными возможными альтернативными связи и расстояния показаны на рисунке 1.
Метод, который может быть использован для решения задачи нахождения дерева кратчайших расстояний, очень прост.
Шаг1. начните произвольно с любого узла и соедините его с ближайшим узлом. Эти два узла теперь рассматриваются как связанные узлы, а остальные - как несвязанные узлы.
Шаг 2. определение несвязанный узел, который наиболее близок к одному из связанных узлов. Если два или более узлов можно рассматривать как ближайшие, то выберите любой из них. Добавьте этот новый узел к связанным узлам. Повторяйте этот шаг до тех пор, пока все узлы не станут связанными.
Этот сетевой алгоритм легко реализуется, если выбирать связи непосредственно на графе сети.
Обращаясь к сети связи для регионального вычислительного центра и начиная с узла 1, мы находим, что ближайшим является узел 2 с расстояния 20. используя жирные линии для пометки дуги, обеспечивающая соединение узлов 1 и 2, мы приходим к следующему результату, характеризующему шаг 1 (рис. 2).
На втором шаге метода находим, что несвзанный узел, ближайший к одному из связанных узлов, есть узел 4 с расстоянием 30 км от узла 1. добавляя узел 4 к множеству связанных узлов, мы получаем следующий результат (рис. 3).
Повторение шага, заключается в добавлении ближайшего несвязанного узла к связанному сегменту сети, дает нам решение задачи о дереве кратчайших расстояний, показана на рисунке 4. Повторяйте шаги метода и посмотрите, получите ли вы решение. Минимальная длина дерева представлена суммой расстояний на дугах, образующих дерево. В данном случае сумма расстояний в сети регионального вычислительного центра составляет 110 км. Заметим, что хотя дуги сети вычислительного центра измерялись в км, другие сетевые модели могут характеризоваться совсем другими показателями - затратами, временем и т.д. В таких случаях алгоритм дерева кратчайших расстояний будет приводить к оптимальному решению (минимальные затраты, минимальное время и т.д.) приминительно к рассматриваемому критерию.
2
Документ
Категория
Без категории
Просмотров
129
Размер файла
688 Кб
Теги
kursach, nadin
1/--страниц
Пожаловаться на содержимое документа