close

Вход

Забыли?

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

?

kursach nadin 2(2)

код для вставкиСкачать
Содержание:
1. Введение............................................................................................3
2. Постановка задачи..........................................................5
3. Прямой алгоритм...........................................................11
4. Список литературы........................................................20
5. Приложение №1. Структурное проектирование.....................20
6. Приложение №2. Текст программы....................................20
7. Приложение №3............................................................20
Введение
Прежде всего, несколько слов о том, как возникает понятие графа из естественных условий задач. Приведем несколько примеров.
Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.
Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением.
Сеть компьютеров, соединенных проводными линиями связи.
Набор слов, каждое из которых начинается на определенную букву и заканчивается на эту же или другую букву.
Множество костей домино. Каждая кость имеет 2 числа: левую и правую половину кости.
Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников.
Генеалогические деревья, указывающие родственные отношения между людьми.
И, наконец, собственно графы, указывающие отношения между какими либо абстрактными понятиями, например, числами.
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.
2. Постановка задачи
Для решения задачи можно представить участок ТС как граф, узлами которого являются перекрёстки, а дугами - улицы.
Представление участка в виде графа (рисунок).
Теория графов - раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E - подмножество V×V. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, перекрёстки, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов .
Основные термины теории графов
Граф - базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины). Участок ГТС будет представлен в виде графа.
Вершина, Узел - базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G). Перекрёсток - вершина.
Ребро графа - базовое понятие. Ребро соединяет две вершины графа. Дорога - ребро.
Дуга- это ориентированное ребро.
Взвешенный граф - граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Вес ребра - значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес - вещественное число, в таком случае его можно интерпретировать как "длину" ребра. Длина дороги - вес ребра.
Задача.
Коммуникационная сеть минимальной длины, или дерево кратчайших расстояний, - это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети.
Рассмотрим задачу: В городе возможно строительство новых дорог. Инженеры определили идеальные места расположения этих дорог. Эти места представлены узлами сети , приведенном ниже рисунке. Дуги сети отражают возможные альтернативы дорог. Инженеры хотят минимизировать общую протяженность дорог, которые требуется проложить в городе, и при этом обеспечить доступ ко всем узлам. Какова минимальная протяженность дорог?
Определение такой системы связи минимальной длины представляет собой пример дерева кратчайших расстояний. Сеть применительно к этой задаче с различными возможными альтернативными связи и расстояния показаны на рисунке 1.
Метод, который может быть использован для решения задачи нахождения дерева кратчайших расстояний, очень прост.
Шаг1. начните произвольно с любого узла и соедините его с ближайшим узлом. Эти два узла теперь рассматриваются как связанные узлы, а остальные - как несвязанные узлы.
Шаг 2. определение несвязанный узел, который наиболее близок к одному из связанных узлов. Если два или более узлов можно рассматривать как ближайшие, то выберите любой из них. Добавьте этот новый узел к связанным узлам. Повторяйте этот шаг до тех пор, пока все узлы не станут связанными.
Этот сетевой алгоритм легко реализуется, если выбирать связи непосредственно на графе сети.
Обращаясь к сети связи для регионального вычислительного центра и начиная с узла 1, мы находим, что ближайшим является узел 2 с расстояния 20. используя жирные линии для пометки дуги, обеспечивающая соединение узлов 1 и 2, мы приходим к следующему результату, характеризующему шаг 1 (рис. 2).
На втором шаге метода находим, что несвзанный узел, ближайший к одному из связанных узлов, есть узел 4 с расстоянием 30 км от узла 1. добавляя узел 4 к множеству связанных узлов, мы получаем следующий результат (рис. 3).
Повторение шага, заключается в добавлении ближайшего несвязанного узла к связанному сегменту сети, дает нам решение задачи о дереве кратчайших расстояний, показана на рисунке 4. Повторяйте шаги метода и посмотрите, получите ли вы решение. Минимальная длина дерева представлена суммой расстояний на дугах, образующих дерево. В данном случае сумма расстояний в сети регионального вычислительного центра составляет 110 км. Заметим, что хотя дуги сети вычислительного центра измерялись в км, другие сетевые модели могут характеризоваться совсем другими показателями - затратами, временем и т.д. В таких случаях алгоритм дерева кратчайших расстояний будет приводить к оптимальному решению (минимальные затраты, минимальное время и т.д.) приминительно к рассматриваемому критерию.
3. Простой алгоритм
Коммуникационная сеть минимальной длины (или дерево кратчайших расстояний) - это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети, то есть возможность попасть из любого узла в любой другой узел.
Алгоритм построения:
1. Начать с любого узла и соединить его с ближайшим узлом. Считаем, что это связанные узлы, а все другие - несвязанные.
2. Определить несвязанный узел, ближайший к одному из связанных узлов. Если таких "ближайших" узлов несколько, то выбрать любой. Добавить этот узел к связанным узлам. И так далее до тех пор, пока есть несвязанные узлы.
Дерево - одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
Определения:
* Корневой узел - самый верхний узел дерева (узел 2 на примере).
* Корень - одна из вершин, по желанию наблюдателя.
* лист, листовой или терминальный узел - узел, не имеющий дочерних элементов (узлы 2, 4, 5, 11).
* Внутренний узел - любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом (2, 7, 5, 6, 9).
Дерево считается ориентированным, если в корень не заходит ни одно ребро.
* Полный сцепленный ключ - идентификатор записи, который образуется путём конкатенации всех ключей экземпляров родительских записей (групп).
Узлы Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (илиузлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла - это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
Корневые узлы Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с "листов" и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). (Согласно формальному определению, каждый подобный путь должен быть уникальным). В диаграммах он обычно изображается на самой вершине. В некоторых деревьях, например, кучах, корневой узел обладает особыми свойствами. Каждый узел дерева можно рассматривать как корневой узел поддерева, "растущего" из этого узла.
Поддеревья Поддерево - часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином "соответствующее подмножество").
Упорядочивание деревьев Существует два основных типа деревьев. В рекурсивном дереве или неупорядоченном дереве имеет значение лишь структура самого дерева без учёта порядка потомков для каждого узла. Дерево, в котором задан порядок (например, каждому ребру, ведущему к потомку, присвоены различные натуральные числа) называется деревом с именованными рёбрами илиупорядоченным деревом со структурой данных, заданной перед именованием и называемой структурой данных упорядоченного дерева.
Упорядоченные деревья являются наиболее распространёнными среди древовидных структур. Двоичное дерево поиска - одно из разновидностей упорядоченного дерева.
Представление деревьев Существует множество различных способов представления деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве (например, двоичная куча).
Деревья как графы В теории графов дерево - связанный ациклический граф. Корневое дерево - это граф с вершиной, выделенной в качестве корневой. В этом случае любые две вершины, связанные ребром, наследуют отношения "родитель-потомок". Ациклический граф со множеством связанных компонентов или набор корневых деревьев иногда называется лесом.
Методы обхода Пошаговый перебор элементов дерева по связям между узлами-предками и узлами-потомками называется обходом дерева. Зачастую, операция может быть выполнена переходом указателя по отдельным узлам. Обход, при котором каждый узел-предок просматривается прежде его потомков называется предупорядоченным обходом или обходом в прямом порядке (pre-order walk), а когда просматриваются сначала потомки, а потом предки, то обход называется поступорядоченным обходом или обходом в обратном порядке (post-order walk). Существует также симметричный обход, при котором посещается сначала левое поддерево, затем узел, затем - правое поддерево, и обход в ширину, при котором узлы посещаются уровень за уровнем (N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Общие операции * вставка нового элемента в определённую позицию;
* вставка поддерева;
* добавление ветви дерева (называется прививкой);
* нахождение корневого элемента для любого узла;
* нахождение наименьшего общего предка двух вершин;
* перебор всех элементов дерева;
* перебор элементов ветви дерева;
* поиск изоморфного поддерева;
* поиск элемента;
* удаление ветви дерева (называется обрезкой);
* удаление поддерева;
* удаление элемента.
Каждый узел дерева должен иметь в точности один родительский узел (разумеется, за исключением корневого узла - для него родителя не существует). В сети же любой узел (иногда называемый вершиной) может быть соединен связями (которые иначе называются дугами или ребрами) с произвольным количеством других узлов. В зависимости от поставленной задачи связи могут быть ориентированными, иначе говоря, направленными (указывающими одно направление), либо неориентированными, или ненаправленными (можно переходить по данной связи в обоих направлениях), а понятий родительского узла и корня не существует.
Во многих представлениях связь также характеризуется некоторой величиной − весом (иногда называемой cost − цена, distance − расстояние или length − длина), которую можно понимать как стоимость перехода по данной дуге.
Например, применительно к сети улиц вес связи может быть временем, которое требуется для проезда по ней. В электрической сети весом связи может быть величина потерь напряжения или мощности при прохождении тока через данную линию. В сети магистральных дорог (highway) весом связи можно считать затраты на строительство соответствующего участка магистрали (которые могут достигать более двух миллионов долларов на милю для дорожной полосы). На рисунке 1 показана небольшая направленная сеть. Числа на связях − это веса связей. Буквами обозначены узлы.
Рисунок 1. Пример направленной сети. Числами обозначены веса дуг.
В виде сетей могут быть представлены многие объекты реального мира, такие как городские улицы, водопровод, ливневые стоки и коллекторы, электросети, компьютерные сети, железнодорожные пути, авиалинии и т.д. В подобных сетях поиск кратчайшего пути приводит к наилучшему маршруту поездки от одного пункта к другому, к маршруту в компьютерной сети с наименьшим использованием ресурсов промежуточных компьютеров или, например, к авиа-перелету с минимальным числом посадок и т.п.
Есть и несколько других более "тонких" применений методов вычисления кратчайших путей. В роли кратчайших путей могут выступать наилучшие последовательности элементарных поворотов кубика Рубика. Другая задача - определение наименьшего числа преобразований, требуемых для конвертирования одной части текста в другую (что можно трактовать как меру подобия фрагментов текста). Вычисления кратчайших маршрутов требуются также для решения задачи коммивояжера (поиск оптимальной последовательности посещения нескольких пунктов с возвращением в начальную точку).
Задача нахождения кратчайшего пути от одного узла сети к другому предполагает нечто большее, чем поиск какого-нибудь одного маршрута. Разглядывая карту улиц, иногда мы способны интуитивно найти маршрут, близкий к оптимальному, вовсе не обращая внимания на тупики, глухие переулки, улицы, расположенные где-то сбоку и тому подобное, которые наверняка не будут задействованы в искомом маршруте.
К сожалению, в алгоритмах поиска кратчайшего пути не может проявляться такого рода интуиция. Тому есть две веские причины:
Во-первых, для некоторых сетей бывает слишком сложно точно установить, какие из связей (дуг) действительно "бесполезны". Например, в сети улиц время прохождения дуги соотносится с ее длиной, а в другой сети дуга может иметь иной практический смысл. Вторая − и, возможно, более важная причина: эти алгоритмы недостаточно интеллектуальны. Даже если добавить в них код, чтобы попытаться определить те части сети, которые заведомо не будут принадлежать окончательно найденному решению, это настолько усложнило бы алгоритм, что могло бы существенно снизить общую производительность. Алгоритмы содержат короткие циклы, которые исполняются по многу раз с большой скоростью. Добавление специальных тестов, помогающих найти кратчайший путь, повышает интеллектуальность алгоритма, но обычно замедляет его выполнение. В общем случае не стоит излишне загромождать циклы.
Поскольку такие алгоритмы не могут, проявляя интуицию, отбрасывать явно неправильные маршруты, для них действительно проще вычислять кратчайший маршрут от данного узла к любому другому узлу в сети, нежели сразу находить кратчайший путь между двумя узлами.
Посмотрим на рисунок 2, где показана та же ориентированная сеть, что и на рисунке 1. Здесь все кратчайшие пути от узла A сети к любому другому узлу и отмечены красным цветом. В частности, кратчайшим путем от узла A к узлу G оказался A-C-E-F-G.
Рисунок 2. Множество путей: Алгоритмы находят кратчайшие пути от одного узла ко всем остальным.
Дуги, задействованные в этих кратчайших путях, образуют дерево, которое называют деревом кратчайших путей с корнем в узле A.
После того, как найдено дерево кратчайших путей, найти кратчайший маршрут к конкретному узлу несложно. Достаточно начать движение с узла назначения и двигаться по ветвям дерева обратно, следуя к родителю каждого узла, пока не будет достигнут корневой узел.
К примеру, для того чтобы найти путь из узла A в узел D, необходимо начать с узла D, затем перейти к его родительскому узлу E, после чего перейти к родителю узла E, потом к C, и, наконец, к родителю узла C, который и есть узел A. Проход завершен, поскольку мы достигли корня дерева кратчайших путей. Прочитав последовательность узлов, которые мы посетили, в обратном порядке, получим искомый путь.
2
Документ
Категория
Рефераты
Просмотров
106
Размер файла
788 Кб
Теги
kursach, nadin
1/--страниц
Пожаловаться на содержимое документа