 |
 |
 |
|
|||||||||
|
 | |||||||||||
|
 |
||||||||
|
МЕНЮ
|
БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Эйлеровы циклы. Задача "Китайского почтальона"Эйлеровы циклы. Задача "Китайского почтальона"2 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОСТОЧНО - СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра систем информатики Курсовая работа (Д.669.2.1.12.13.006.09.ПЗ) по дисциплине «Дискретная математика в программировании» Тема: «Эйлеровы циклы. Задача «Китайского почтальона» Выполнил: студентка гр. 669 Хохлова А.М. Руководитель: Доцент кафедры Си Данилова С.Д Улан-Удэ,2010 ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра систем информатики ЗАДАНИЕ на курсовую работу
Оглавление Глава 1: теоретическая часть Аннотация 1.1 Задача Эйлера 1.2 Цикломатическое число и фундаментальные циклы 1.3 Разрезы 1.4 Матрицы циклов и разрезов 1.5 Эйлеровы циклы и задача китайского почтальона 1.5.1 Основные понятия и определения 1.5.2 Критерий существования эйлерова цикла 1.5.3 Алгоритмы построения эйлерова цикла 1.6 Алгоритм для задачи китайского почтальона 1.6.2 Алгоритм Дейкстры 1.6.3 Венгерский алгоритм 2.Проектный раздел 2.1 Словесная постановка задачи 2.2 Формальная постановка задачи 2.3 Алгоритм решения задачи в графическом виде 3. Программный раздел 4. Экспериментальный раздел Заключение Приложения 1 Список использованной литературы Аннотация Целью моей курсовой работы является описание методов нахождения и построения эйлеровых циклов в графах. Разобраться с такими понятиями как, цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Так же было необходимо решить задачу « задачу китайского почтальона». Для достижения поставленной цели в работе рассмотрены теоретические вопросы в данной предметной области, предложен способ решения «задачи китайского почтальона». И разработано программное обеспечение, реализующее предложенный способ. Предмет исследований: Задача «Китайского почтальона» Цель работы: Изучение таких понятий как: Цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Эйлеровы циклы и задача китайского почтальона. Задачи: 1)Узнать, что такое Цикломатическое число и фундаментальные циклы. Разрезы. Матрицы циклов и разрезов. Эйлеровы циклы и задача китайского почтальона. 2)изучить алгоритм решения «задачи китайского почтальона» 3)Разработать программу решающую данную задачу на языке программирования. Си Методы исследования: Теоретические методы:теоретический анализ (выделение и рассмотрение отдельных сторон, признаков, особенностей, свойств явлений), индуктивные и дедуктивные методы обобщения полученных данных, математические методы, статические методы и практические. 1. Теоритический раздел 1.1 Задача ЭйлераС именем Эйлера, связана задача о трех домиках и трех колодцах. Задача: Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики (рис.1).Рис. 1. К задаче о домиках и колодцах.Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых. Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство где - общее число вершин, - общее число ребер, - число многоугольников (граней). Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).
Рис. 2. Действительно, после проведения такой диагонали в новом разбиении будет вершин, ребер и количество многоугольников увеличится на единицу. Следовательно, имеем Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) (рис. 2, б). Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая: · для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC; для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN. В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из вершин, ребер и многоугольника: Таким образом, удаление одного треугольника не меняет равенства (*). Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения , , и, следовательно, Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*). Соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится. Решениезадачи о трех домиках и трех колодцах.. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются. Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид , причем и Следовательно Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше , что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу. 1.2 Цикломатическое число и фундаментальные циклы.Мультиграф -- граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг -- , называют-графом.Рассмотрим неориентированный мультиграф (s-граф) , n -- вершин, -- ребёр, -- связных компонент. -- цикломатическое число (число ребер в остовах всех p связных компонент графа). -- коцикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. -- наибольшее число независимых круговых токов в электрической цепи. -- наибольшее число независимых разностей потенциалов в электрической цепи. Рассмотрим, например, электрическую цепь, показанную на рисунке 3а. Неориентированный граф G этой цепи состоит из единственной связной компоненты и изображен на рис. 3б ,где остов Т показан жирной линией .Добавление любого ребра из , не принадлежащего, к ребрам дерева приводит к образованию точно одного (простого) цикла, состоящего из ребер остова , лежащих на (единственной) цепи из в, и только что добавленного ребра. Например, добавляя ребро, получаем цикл .Так как в графе имеется ребер, из которых лежат в , то число всех циклов, построенных таким способом, равно , что совпадает с цикломатическим числом графа . В примере на рисунке 3 число таких циклов равно , они изображены на рисунке 3б пунктирными линиями и обозначены через Все эти циклы, очевидно, независимы между собой, так как каждый из них имеет по крайней мере одно ребро, не принадлежащее никакому другому циклу. В общем случае циклов, получаемых добавлением какого-либо ребра из , не лежащего в , к ребрам , называются фундаментальными циклами. Если семейство этих циклов обозначить черезв нашем примерето любой другой цикл в графе, не принадлежащий к , может быть выражен в виде линейной комбинации циклов из , если принять следующее соглашение :Пусть каждый фундаментальный цикл представлен -мерным вектором, в котором j-я компонента равна 1 или 0 в зависимости от того, принадлежит лиj-е ребро данному циклу. Тогда, используя как символ сложения по модулю 2, любой цикл можно представить как сумму по модулю 2 фундаментальных циклов. Так, цикл на рисунке 3б может быть представлен в виде Отметим, что обращение вышеприведенного утверждения неверно, а именно некоторая сумма по модулю 2 фундаментальных циклов не обязательно дает единственный цикл, но может представлять два и более циклов. Например, сумма соответствует двум циклам () и Таким образом, для порождения всех циклов графа не надо брать все комбинаций фундаментальных циклов и складывать их но модулю 2: некоторые из этих сумм на самом деле не будут циклами.Более того, если данная сумма, не порождает цикла, то нельзя отбросить другие суммы, ее содержащие, так как, складывая по модулю 2 сумму с другой суммой (которая сама может не порождать цикла), мы можем получить цикл. Рисунок 3аРисунок 3б1.3 РазрезыПонятие разреза очень тесно связано с понятием цикла и определяется так. Определение. Если вершины неориентированного графа разбиты на два множества и (где , и является дополнением Хо относительно X), то множество ребер графа одни концевые вершины которых лежат в а другие в называется разрезом графа G.Множество ребер разрева может быть представлено множеством вершин пары . Таким образом, остовный подграф ,полученный ив удалением ребер, принадлежащих разрезу, является несвязным графом, состоящим но крайней мере из двух компонент. фундаментальные разрезы относительно остова определяются как разрезов, каждый из которых содержит одно, и только одно ребро, принадлежащее дереву Т. Теорема Если -- остов неориентированного врафа , то фундаментальный разрез, определяемый ребром из Т, образован и теми ребрами из не принадлежащими которые после добавления к дают фундаментальные циклы, содержащие 1.4 Матрицы циклов и разрезовПусть -- остов неориентированного графа. Матрицей фундаментальных циклов графа называется матрица состоящая из строк и столбцов, в которой равно 1, если ребро принадлежит циклу и равно 0 в противном случае. Если ребра, не принадлежащие дереву Т, пронумеровать последовательно от 1 до а ребра дерева T пронумеровать от до , то матрица циклов будет иметь вид ,где - единичная матрица. Это объясняется тем, что каждый цикл содержит одно, и только одно ребро, не принадлежащее остову Т, и циклы всегда можно пронумеровать по числу принадлежащих им внеостовных ребер, вследствие чего все единицы в первой подматрице матрицы лежат на диагонали. Матрица фундаментальных разрезов определяется аналогично -- как матрица строками и столбцами, где есть 1, если ребро - принадлежит разрезу и 0 в противном случае. При той же самой нумерации ребер, что и выше, матрица К имеет вид так как теперь каждый фундаментальный разрез содержит одно, и только одно ребро из ребер дерева Т.1.5 Эйлеровы циклы и задача китайского почтальона1.5.1 Основные понятия и определенияДадим теперь строгое определение эйлерову циклу и эйлерову графу. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.Ясно, что эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз). Очевидно также, что эйлеровым может быть только связный граф. Выберем в качестве вершин графа берега реки, а в качестве ребер - мосты, их соединяющие. После этого задача становится очевидной: требование неосуществимо - чтобы его выполнить, число дуг, приходящих к каждой вершине, должно быть четным. В самом деле, поскольку по одному мосту нельзя проходить дважды, каждому входу на берег должен соответствовать выход.1.5.2 Критерий существования эйлерова циклаЧто необходимо, чтобы в графе существовал эйлеров цикл? Во-первых, граф должен быть связанным: для любых двух вершин должен существовать путь, их соединяющий. Во-вторых, для неориентированных графов число ребер в каждой вершине должно быть четным. На самом деле этого оказывается достаточно.Теорема 1. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.Доказательство. Необходимость. Любой эйлеров цикл должен прийти в вершину по одному ребру и покинуть ее по другому, так как любое ребро должно использоваться ровно один раз. Поэтому, если G содержит эйлеров цикл, то степени вершин должны быть четными. Достаточность. Пусть G -- связный неориентированный граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины x0 и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину x0 и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф -- только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем xi, являющуюся конечной вершиной какого-либо до сих пор не использованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (0 является четным числом), инцидентных каждой вершине.Начиная теперь с xi, получаем цикл Ф', начинающийся и оканчивающийся в xi. Если все оставшиеся ранее ребра использованы для цикла Ф', то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x0 до xi, затем циклом Ф' и, наконец, частью цикла Ф от вершины xi до x0. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф' дает новый цикл Ф. Мы снова можем найти вершину xj, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф', начинавшегося в xj, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.Хотя доказательство проведено для неориентированных графов, оно сразу переносится на ориентированные, только требование четности заменяется теперь на такое: число входящих в каждую вершину ребер должно быть равно числу выходящих.Следствие #1.Для связного эйлерова графа G множество ребер можно разбить на простые циклы.Следствие #2.Для того чтобы связный граф G покрывался единственной эйлеровой цепью, необходимо и достаточно, чтобы он содержал ровно 2 вершины с нечетной степенью. Тогда цепь начинается в одной из этих вершин и заканчивается в другой.1.5.3 Алгоритмы построения эйлерова циклаВыше был установлен эффективный способ проверки наличия эйлерова цикла в графе. А именно, для этого необходимо и достаточно убедиться, что степени всех вершин четные, что нетрудно сделать при любом представлении графа. Осталось заметить, что предложенный в доказательстве алгоритм линеен, т.е. число действий прямо пропорционально числу ребер.Алгоритм построения эйлерова цикла в эйлеровом графе.Вход:эйлеров граф G(V,E), заданный матрицей смежности. Для простоты укажем, что Г[v]-- множество вершин, смежных с вершиной v.Выход:последовательность вершин эйлерова цикла.S:=Ш {стек для хранения вершин}selectvV {произвольная вершина}v>S {положить v в стек S}whileS?Ш dov<S; v>S {v -- верхний элемент стека}ifГ[v]=Ш then v<S; yieldvelseselectuГ[v] {взять первую вершину из списка смежности}u>S {положить u в стек} Г[v]:=Г[v]\{u}; Г[u]:=Г[u]\{v} {удалить ребро (v,u)}end ifend whileОбоснованиеалгоритма.Принцип действия этого алгоритма заключается в следующем. Начиная с произвольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина v имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке S. Заметим, что при этом степени всех вершин остались четными. Далее вершина v выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека.Мне бы хотелось привести здесь еще один алгоритм построения эйлерова цикла в эйлеровом графе -- это Алгоритм Флёри, он позволяет пронумеровать ребра исходного графа так, чтобы номер ребра указывал каким по счету это ребро войдет эйлеров цикл.Алгоритм Флёри:1. Начиная с любой вершины v присваиваем ребру vu номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u.2. Пусть w - вершина, в которую мы пришли в результате выполнения 1 шага алгоритма и k - номер, присвоенный очередному ребру на этом шаге. Выбираем произвольное ребро инцидентное вершине w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присваиваем ребру номер k+1 и вычеркиваем его. Процесс длится до тех пор, пока все ребра не вычеркнут. Примечание: Мостом называется ребро, удаление которого лишает данный граф связности, т.е. увеличивает число компонент связности. Пример:Приведем теперь строгое обоснование корректности алгоритма Флёри построения эйлерового цикла в данном эйлеровом графе.Теорема 2. Пусть G(V,E) -- эйлеров граф. Тогда следующая процедура всегда возможна и приводит к построению эйлерова цикла графа G(V,E).Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая при этом следующие правила:1)Стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);2)На каждом шаге идем по мосту только в том случае, когда нет других возможностей.Доказательство.Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v ? u. Удалив ребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G1 имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G1, либо происходит удаление вершины u и оставшийся граф G2 связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся не пройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).1.6 Алгоритм для задачи китайского почтальонаВ случае, когда веса всех ребер равны единице, задачу китайского почтальона рассмотрели Беллман и Кук с использованием динамического программирования. Более общую задачу. когда веса ребер произвольны, сформулировали и решили как задачу о паросочетании (с частной задачей о кратчайшей цепи) Эдмондс, Эдмондс и Джонсон , Басакер и Саати и Кристофидес.Рассмотрим неориентированный граф Среди вершин из некоторые вершины (скажем из множества ) будут иметь четные степени, а остальные (из множества )-нечетные степени. Далее сумма степеней всех вершин равна удвоенному числу ребер в (так как каждое ребро добавляет по единице к степеням двух его концевых вершин) и поэтому равна четному числу . Следовательно,и так как сумма четна, то сумма также четна, но все в последней сумме нечетны, значит число | вершин нечетной степени четно.Пусть -- множество таких цепей (скажем ) в между концевыми вершинами и ) что никакие две цепи не имеют одинаковых конечных вершин, т. е. цепи соединяют различные пары вершин из и покрывают все вершины множества .Число цепей в в равно , а как было показано выше, ,всегда четно, следовательно, это число всегда целое, если, конечно, оно определено. Предположим теперь, что все ребра, образующие цепь , добавлены к в качестве искусственной параллельной цепи, причем эти ребра остаются в графе . Это означает, прежде всего, что все ребра из , образующие цепь ,теперь удвоены. Так поступаем с каждой цепью и полученный -граф обозначим через Так как некоторые ребра из могут входить более чем в одну цепь ·, то некоторые ребра из могут быть (после того как добавлены все «новые» цепи) утроены, учетверены и т. д. Теперь мы можем рассмотреть следующую теорему.Теорема. Для любого цикла, проходящего по , можно выбрать множество , для которого граф имеет эйлеров цикл, соответствующий первоначально взятому циклу в графе . Это соответствие таково, что если цикл проходит по ребру из раз, то в существует ребер (одно реальное и искусственных) между , каждое из которых проходится ровно один раз эйлеровым циклом из. Справедливо и обратное утверждение. Алгоритм решения задачи китайского почтальона немедленно следует из данной теоремы, так как все, что для этого необходимо, состоит в нахождении множества цепей (цепного паросочетания для множества вершин нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего веса, проходящий по , будет иметь вес, равный сумме весов всех ребер из плюс сумма весов ребер в цепях из . Это то же самое, что и сумма весов всех ребер - реальных и искусственных - графа (М*). Описание алгоритма.Шаг 1. Пусть -матрица весов ребер графа . Используя алгоритм кратчайшей цепи, образуем -матрицу, где - вес цепи наименьшего веса, идущей из некоторой вершины в другую вершину Шаг 2. Найдем то цепное паросочетание для множества которое дает наименьший вес (в соответствии с матрицей весов ). Шаг 3. Если вершина сочетается с другой вершиной, то определим цепь наименьшего веса (из), соответствующую весу , делая шаг 1. Добавим искусственные ребра в соответствующие ребрам из и проделаем это для всех других цепей из множества в результате чего получится -граф (М*).. Сумма весов всех ребер графа (М*). ,найденная с использованием матрицы (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по . При этом число прохождений цикла по ребру равно общему числу параллельных ребер между в (М*).Следует заметить, что поскольку на шаге 2 используется минимальное паросочетание, никакие две кратчайшие цепи и при таком паросочетании (скажем, идущие из и из в не могут иметь общего ребра.Рисунок 6. Цепи и ,имеющие общее ребро Если бы они имели общее ребро (), как показано на рисунке. 6 то сочетание вершин (использующее подцепи от ) и сочетание пары вершин (использующее подцепи от ) давало бы общее паросочетание веса, меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф (М*).не должен содержать более двух параллельных ребер между любыми двумя вершинами, т. е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.Коротко данный алгоритм можно записать:1. В исходном графе Г' находятся все вершины нечетной степени, если таковыхнетто пункт 6. 2. Для каждой такой вершины находятся кратчайшие пути до всех остальных, эти пути запоминаются. 3. На этих вершинах строится двудольный граф Г' с весами, равными кратчайшему расстоянию 4.Ищем максимальное паросочетание минимального веса. 5. По паросочетанию добавляем в исходный граф дополнительные ребра. Т.е. если у нас в паросочетании Г' есть ребро (A,B), то в Г добавляется цепь кратчайшего пути между вершинами А и В. Получаем эйлеров граф.6.Находимэйлерову цепь. Для реализации данного алгоритма нам необходимо реализовать три алгоритма: · Алгоритм Дейкстры( пункт 2) · Венгерский алгоритм (пункт 4) · Алгоритм Флёри (пункт 6) 1.6.2 Алгоритм ДейкстрыАлгоритм Демйкстры (Dijkstra's algorithm) -- алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.Обозначения V -- множество вершин графа E -- множество ребер графа w[ij] -- вес (длина) ребра ij a -- вершина, расстояния от которой ищутся U -- множество посещенных вершин d[u] -- по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u p[u] -- по окончании работы алгоритма содержит кратчайший путь из a в u Псевдокод Присвоим Для всех отличных от a присвоим Пока Пусть -- вершина с минимальным Для всех таких, что если то изменим изменим Описание В простейшей реализации для хранения чисел можно использовать массив чисел, а для хранения принадлежности элемента множеству -- массив булевых переменных. В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (большим максимального возможного пути вграфе). Массив флагов заполняется нулями. Затем запускается основной цикл. На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф не связан. 1.6.3 Венгерский алгоритмВенгерский алгоритм -- алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари). Джеймс Манкрес в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна -- Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была O(n4), однако Эдмондс и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O(n3). Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни. Так как алгоритм сложен для понимания. В данной работе он будет рассмотрен на примере, через матричную инетерпритацию. Матричная интерпретация Для n работников и работ, дана матрица, задающая стоимость выполнения каждой работы каждым работником. Найти минимальную стоимость выполнения работ, такую что каждый работник выполняет ровно одну работу, а каждую работу выполняет ровно один работник. В дальнейшем мы под назначением понимаем соответствие между работниками и работами, имеющее нулевую стоимость, после того как мы произвели трансформации, влияющие лишь на общую стоимость работ. Прежде всего запишем задачу в матричной форме: где a, b, c, d -- работники, которые должны выполнить работы 1, 2, 3, 4. Коэффициенты a1, a2, a3, a4 обозначают стоимость выполнения работником «a» работ 1, 2, 3, 4 соответственно. Аналогичный смысл имеют остальные символы. Матрица квадратная, поэтому каждый работник может выполнить только одну работу. Шаг 1 Уменьшаем элементы построчно. Находим наименьший из элементов первой строки (а1, а2, а3, а4), и вычитаем его из всех элементов первой строки. При этом хотя бы один из элементов первой строки обнулится. То же самое выполняем и для всех остальных строк. Теперь в каждой строке матрицы есть хотя бы один ноль. Иногда нулей уже достаточно, чтобы найти назначение. Пример показан в таблице. Красные нули обозначают назначенные работы.
При большом количестве нулей для поиска назначения (нулевой стоимости) можно использовать алгоритм нахождения максимального паросочетания двудольных графов, например алгоритм Хопкрофта-Карпа. Кроме того, если хотя бы в одном столбце нет нулевых элементов, то назначение невозможно. Шаг 2 Часто на первом шаге нет назначения, как, например, в следующем случае:
Задача 1 может быть эффективно (за нулевую стоимость) выполнена как работником a, так и работником c, зато задача 3 не может быть эффективно выполнена никем. В таких случаях мы повторяем шаг 1 для столбцов и вновь проверяем, возможно ли назначение. Шаг 3 Во многих случаях мы достигнем желаемого результата уже после шага 2. Но иногда это не так, например:
Если работник d выполняет работу 2, некому выполнять работу 3, и наоборот. В таких случаях мы выполняем процедуру, описанную ниже. Сначала, используя любой алгоритм поиска максимального паросочетания в двудольном графе, назначаем как можно больше работ тем работникам, которые могут их выполнить за нулевую стоимость. Пример показан в таблице, назначенные работы выделены красным.
Отметим все строки без назначений (строка 1). Отметим все столбцы с нулями в этих строках (столбец 1). Отметим все строки с нулями в этих столбцах (строка 3). Продолжаем, пока новые строки и столбцы не перестали отмечаться.
Теперь проводим линии через все отмеченные столбцы и неотмеченные строки.
Все эти действия преследовали лишь одну цель: провести наименьшее количество линий (вертикалей и горизонталей), чтобы покрыть все красные нули. Можно было воспользоваться любым другим методом вместо описанного. Шаг 4 Из непокрытых линиями элементов матрицы (в данном случае это a2', a3', a4', c2', c3', c4') найти наименьший. Вычесть его из всех не отмеченных строк и прибавить ко всем пересечениям отмеченных строк и столбцов. Так, например, если наименьший элемент из перечисленных равен а2', мы получим
Повторять процедуру (шаги 1-4) до тех пор, пока назначение не станет возможным. 2. Проектный раздел 2.1 Словесная постановка задачи:Реализовать известный алгоритм для задачи китайского почтальона.2.2 Формальная постановка задачи:Входные данные:n-количество вершин графа C[50][50]-символьная матрица смежности Выходные данные:Путь обхода графа. Суммарный вес пройденных дуг Метод решения :Программа состоит из 2 основных подпрограмм 1)Программа реализующая алгоритм Дейкстры( описанный в разделе 1) 2)Алгоритм Флёри (раздел 1) содержащий в себе часть венгерского алгоритма. 2.3 Алгоритм решения задачи в графическом видеKomponenta() Poisk()Main() Deikstra() Eiler() 3. Программный разделvoid main(int argc, char* argv[])Главная функция программы. В ней происходит ввод данных с клавиатуры:n-числа вершин C[i][j]-расстояние между конкретными вершинами i и jВ результате чего формируется матрица смежности wordC[n][n].В этой функции происходит вызов функции deikstra() и eiler();В функцию deikstra() передаются номера вершин с нечетной степенью в всевозможных попарных сочетаниях .void deikstra()Функция нахождения кратчайшего расстояния между переданными точками.Функция ничего не возврящает, но при каждом вызове выводит на экран путь между заданными вершинами и длину этого пути.Для работы данной функции необходимо подключить функции int min(int n) и word minim(word x, word y)· int min(int n)- возвращает номер ближайшей не пройденной вершины · wordminim(wordx, wordy)-возвращает самое короткое из 2 переданных слов void eiler() Функция нахождения эйлерова цикла в заданом графе. В случае если данный цикл не может быть найден ,цикл ищеться с добавлением необходимых ребер, после чего необходимое ребро заменяеться самой короткой цепью из возвращаемых функцией Deikstra(). Так же в этой функции просчитывется суммарный вес обхода. Для работы данной функции необходимо подключение 3 функций: · void poisk(int i)- динамическая функция непосредственного поиска пути. В ней же происходит обнуления рабочей матрицы смежности A[50][50] · void komponenta(int i)- проверяет наличие пустых ячеек в регистре флагов. В данной программе не обязательна и не используется · void no()-функция выводящая сообщение о невозможности нахождения эйлерова цикла в данном графе( если граф не связан) 4.Эксперементальный раздел Данная программа работает только с графами количество вершин меньше 50. (Это число было задано при разработке , и по этому в случае необходимости может варьироваться )Но так как программа основана не на динамическом распределении памяти а н хранении элементов (матрицы смежности) в виде массива, но верхний порог значений всегда будет иметь место. Так же данная программа не работает с отрицательными значениями в матрице смежности. Это связанно с основой поставленной задачи. Данная задача может иметь множество разных решений, так как единственный метод получения достоверного ответа сводиться к полному перебору вариантов. Данный метод в этой работе не рассматривается. Пример работы программы в нормальных условиях не описанных выше: При введённых значения (которые указаны на рисунке выше) сформировалась матрица смежности. Как видно, единственные вершины с нечетными степенями -это вершины х1 (3 ребра),и x4(3 ребра). Они были самый короткий путь между ними х1-х4 ,вес этого пути равен 3. После был составлен путь по граням: всего девять переходов. Дважды встречается переход по грани (4-1), так как степени этих вершин нечетные. Минимальный путь обхода складывается из: 1+2+3+5+6+4+1+2=24- длина эйлерова цикла( его можно просчитать сложив все числа над главной диагональю) 24+3=27(3-путь (4-1),который повторяется) Заключение Были выполнены все поставленные задачи. Было разобрано понятие эйлеровых задач, и именно задачи «китайского почтальона», решение которой базируется на понятии эйлерова цикла. Был изучен известный алгоритм решения данной задачи, и на основе этого была создана программная реализация. Приложения 1 Исходныйкод: //С-матрица смежности,с расстониями //xn-начальная точка //xk-конечнаяточка #include"locale.h" #include"stdafx.h" #include<iostream> #include<string.h> #include<stdio.h> #include<stdlib.h> #include<conio.h> #include"locale.h" #define word unsignedint usingnamespace std; void deikstra(); void no(); void komponenta(int i); void eiler(); void poisk(int i); int a[50][50]; int i, j, p, xn, xk,z,k=1,Mas[100][100],ch=0; int vert[10000];//степеньвершин int way [10000];//Эйлеровцикл int flag[10000];//компоненты связности int x,y,w; int n,m;// m - число дуг, n - число вершин int count;// число компонент связности word c[50][50], l[50]; char s[80], path[80][50]; struct st{ char put[50]; int x1; int x2; int ves; }; st mas[100]; int min(int n) { int i, result; for(i=0;i<n;i++) if(!(flag[i])) result=i; for(i=0;i<n;i++) if((l[result]>l[i])&&(!flag[i])) result=i; return result; } word minim(word x, word y) { if(x<y) return x; return y; } void main(int argc, char* argv[]) { setlocale(LC_ALL, "Russian"); cout<<"введитечислоточек: ";// cin>>n; for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=0; for(i=0;i<n;i++) for(j=i+1;j<n;j++) { cout<<"введите расстояние x"<<i+1<<" до x"<<j+1<<":";// cin>>c[i][j];//записываем расстояния в матрицу с } cout<<" "; for(i=0;i<n;i++) cout<<" X"<<i+1; cout<<endl<<endl; for(i=0;i<n;i++) { printf("X%d",i+1); for(j=0;j<n;j++) { printf("%6d",c[i][j]); c[j][i]=c[i][j]; } printf("\n\n"); } for(i=0;i<n;i++){ for(j=0;j<n;j++) if(c[i][j]==0) c[i][j]=65535; }//бесконечность for(i=0;i<n;i++) { z=0; for(j=0;j<n;j++){ if(c[i][j]!=65535) z++; } if(z%2==1)//ищем вершины с нечетными степенями { Mas[k][0]=i;//сохраняем номера этих вершин Mas[0][k]=i; k++; } } for(int m=1;m<k;m++){ xn=Mas[0][m]; for(j=m;j<k-1;j++) { xk=Mas[j+1][0]; if(xn!=xk) deikstra(); } } eiler(); getch(); } //---------------------------------------------------------------------- void deikstra() { for(i=0;i<n;i++) { flag[i]=0; l[i]=65535; } l[xn]=0; flag[xn]=1; p=xn; itoa(xn+1,s,10);//преобразование числа в символы for(i=1;i<=n;i++) { strcpy(path[i],"X"); strcat(path[i],s); } do { for(i=0;i<n;i++) if((c[p][i]!=65535)&&(!flag[i])&&(i!=p)) { if(l[i]>l[p]+c[p][i]) { itoa(i+1,s,10); strcpy(path[i+1],path[p+1]); strcat(path[i+1],"-X"); strcat(path[i+1],s); } l[i]=minim(l[i],l[p]+c[p][i]); } p=min(n); flag[p]=1; } while(p!=xk); if(l[p]!=65535) { mas[p].ves=(int)l[p]; i=0; while(path[p+1][i]!='\0'){ mas[ch].put[i]=path[p+1][i]; i++; } mas[ch].x1=xk; mas[ch].x2=xn; printf("%i вес\n",mas[p].ves); printf("%s путь \n",mas[ch].put); } else cout<<"ЇгвЁ Ґв!"<<endl; ch++; } //----------------------------------------------------------------------------------------- void eiler() { int sum=0; for(i=0;i<n;i++) for(j=0;j<n;j++){ a[i+1][j+1]=(int) c[i][j]; if(a[i+1][j+1]==65535) a[i+1][j+1]=0; } count=0; for (int i=1;i<n;i++) { if (flag[i]==0) count++; if (count>1 ) no();// графнесвязен //komponenta(i); } for (int i=1;i< n;i++) if (vert[i]%2==1) no(); // есть вершины нечётной степени w=0; poisk(1); way[0]=way[1]; for (int i=1;i<=w;i++){ if((int)c[way[i]-1][way[i+1]-1]==65535){ for(j=0;j<ch;j++){ if((mas[j].x1+1==way[i]&&mas[j].x2+1==way[i+1])||(mas[j].x2+1==way[i]&&mas[j].x1+1==way[i+1])){ printf("%s-",mas[p].put); sum=sum+mas[p].ves; way[0]=mas[p].x1; } } } else printf("X%i-",way[i]); } if(way[0]!=way[w]){ if((int)c[way[1]-1][way[w]-1]!=65535){ printf("X%i",way[1]); sum=sum+(int)c[way[i]-1][way[w]-1]; } else{ for(j=0;j<ch;j++){ if(mas[p].x1==way[1]&&mas[p].x2==way[w-1]){ printf("%s-",mas[p].put); sum=sum+mas[p].ves; } } } } for (int i=0;i<=w;i++){ if((int)c[way[i]-1][way[i+1]-1]!=65535) sum=(int)c[way[i]-1][way[i+1]-1]+sum; } printf("\n"); printf("веспути %i ",sum); } //--------------------------------------------------- void no(){ printf("Эйлеров цикл не существует!"); exit(0); } //--------------------------------------------------- void komponenta(int i){ int z; flag[i]=count; for (int z=1;p<=n;j++) if ((a[i][z])&&(flag[z]==0)) komponenta(z); } //--------------------------------------------------- void poisk(int i){ int j; for (int j=1;j<=n;j++) if (a[i][j]!=0){ a[i][j]=0; a[j][i]=0; poisk(j); } w++; way[w]=i; } Список использованной литературы 1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г. 2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г. 3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г. 4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г. 5. О. Оре. Теория графов, Наука, 1982 г. |
РЕКЛАМА
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА | ||
 |
© 2010 | |