Решение графа с помощью программы - Контрольная работа

Метка самой первой вершины полагается равной нулю, метки остальных вершин - бесконечности, т.к. метки остальных вершин нам еще неизвестны и вершины графа отмечаются как не посещенные. Если значение длины меньше значения метки соседа, заменим значение полученным значением длины, отметим данную вершину как посещенную и повторим алгоритм к следующей. Эйлер нашел критерий существования обхода у графа: Граф должен быть связанным и каждая его вершина должна быть инцидентна четному числу ребер. Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j - обратной дугой (или обратным ребром). Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников.Для решения задач, связанных с поиском минимального пути, имеется немало методов: простой перебор, метод ветвей и границ, деревянный алгоритм, алгоритм Дейкстры и пр.

граф программа математический

В этой курсовой работе будет представлено решение определенной задачи теории графов, в частности, с использованием алгоритма Дейкстры. Суть состоит в том, чтобы найти кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Также будет рассмотрена программа решения данной задачи, написанная на объектно-ориентированном языке программирования Delphi 7.

Объяснение алгоритма Дейкстры: алгоритм не должен содержать петель и дуг отрицательного веса. Метка самой первой вершины полагается равной нулю, метки остальных вершин - бесконечности, т.к. метки остальных вершин нам еще неизвестны и вершины графа отмечаются как не посещенные. Выбирается вершина, имеющая минимальную метку, рассматриваются всевозможные маршруты. Вершины, в которые идут ребра из этой метки, называются соседями этой вершины. Далее, для каждого соседа этой вершины, кроме отмеченных как посещенные, рассматривают новую длину пути, равную сумме значений текущей метки и длины ребра соединяющую с соседом. Если значение длины меньше значения метки соседа, заменим значение полученным значением длины, отметим данную вершину как посещенную и повторим алгоритм к следующей.

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

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

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

Вариант 2: Почтальон разносит почту в определенном микрорайоне. Найти кратчайший маршрут от главпочтамта до крайней точки маршрута.

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

1.Теоретическая часть

1.1 История теории графов

Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания. Первая работа по теории графов, принадлежит известному швейцарскому математику Л. Эйлеру. В 1736 г. Эйлер решил задачу о Кенигсбергских мостах. Задача состояла в следующем: «Найти маршрут прохождения всех четырех участков суши, который бы начинался на любом из них, кончался на этом же участке и ровно один раз проходил по каждому из них».

Утверждение о существовании положительного решения задачи о Кенигсбергских мостах эквивалентно утверждению о невозможности обойти этот граф. Эйлер нашел критерий существования обхода у графа: Граф должен быть связанным и каждая его вершина должна быть инцидентна четному числу ребер.

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

Толчок к развитию, теория графов получила на рубеже ХІХ и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

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

1.2 Основные термины теории графов

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

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

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

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

Маршрут в графе - это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.

Путь в графе (иногда говорят простой путь) - это маршрут без повторения вершин (а значит, и ребер).

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

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j - обратной дугой (или обратным ребром).

Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины - это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

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

1.3 Задача коммивояжера

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

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

Общая постановка задачи, впрочем, как и большинство ее частных случаев, относится к классу NP-полных задач . Задача коммивояжера относится к числу трансвычислительных : уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Непременным условием и единственным смыслом задачи коммивояжера является поиск самого выгодного пути. Для этого необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения. Если мы не просчитали все пути в выбранном варианте решения, то мы не можем утверждать, что найденное решение самое выгодное. Что такое проверка решения? - это поиск ошибки в процессе решения или сверка полученного результата с заведомо правильным. Второй вариант временно отбрасываем, так как нет практического смысла в решении задачи, если уже есть решение (в свою очередь, использование ранее выполненного верного решения для части имеющейся задачи - способ уменьшить решение). В рамках данной работы не ставилось целью сравнение различных методов и способов решения, поэтому принимаем, что проверяющий также считает выбранный способ решения оптимальным и проверяет его на правильность. Что нужно сделать проверяющему? - повторить работу, проделанную при решении, в полном объеме для поиска ошибки на каждом этапе решения. Если будет найдена ошибка, то проверяющему будет необходимо продолжить процесс решения для поиска более выгодного маршрута. Таким образом, мы получаем, что проверка решения задачи коммивояжера равна или больше самого решения. Следовательно, либо задача относится к Р-классу либо NP=P!.

1.4 Описание алгоритма Дейкстры

Алгоритм Дейкстры - алгоритм на графах, изобретенный нидерландским ученым Э. Дейкстрой в 1959 году . Находит кратчайшее расстояние от одной из вершин графа до всех остальных.

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

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит, что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5. Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере. Присвоим 1-й вершине метку равную 0, потому как эта вершина - источник. Остальным вершинам присвоим метки равные бесконечности.

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

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещенную, и выбираем из еще не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения, какую из них мы выберем как W. Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые еще не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины. Выполнив все действия, получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р - Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W - P[4]=5. В результате получим вектор Р = {1, 1, 5, 5, 1}. Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

2.Практическая часть

2.1 Математическое решение

Матрица длин дуг для заданного графа имеет вид: Таблица 1 - Исходные данные.

0 5 11 6 8 15 8

5 0 9 12 6 7 2

11 9 0 3 6 3 7

6 12 3 0 2 4 13

8 6 6 2 0 1 5

15 7 3 4 1 0 4

8 2 7 13 5 4 0

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1. Находим ближайшую вершину к окрашенной нами, используя формулу: d(x)=min{d(x); d(y) a(y,x)} d(2)=min{d(2);

d(1) a(1,2)}=min{?; 0 5}=5 d(3)=min{d(3);

d(1) a(1,3)}=min{?; 0 11}=11 d(4)=min{d(4);

d(1) a(1,4)}=min{?; 0 6}=6 d(5)=min{d(5);

d(1) a(1,5)}=min{?; 0 8}=8 d(6)=min{d(6);

d(1) a(1,6)}=min{?; 0 15}=15 d(7)=min{d(7);

d(1) a(1,7)}=min{?; 0 8}=8

Минимальную длину имеет путь от вершины 1 до вершины 2 d(2)=5. Включаем вершину №2 в текущее ориентированное дерево, а также дугу, ведущую в эту вершину. Согласно выражению, это дуга (1,2)

d(3)=min{d(3);

d(2) a(2,3)}=min{11; 5 9}=11 d(4)=min{d(4);

d(2) a(2,4)}=min{6; 5 12}=6 d(5)=min{d(5);

d(2) a(2,5)}=min{8; 5 6}=8 d(6)=min{d(6);

d(2) a(2,6)}=min{15; 5 7}=12 d(7)=min{d(7);

d(2) a(2,7)}=min{8; 5 2}=7

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=6. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,4) d(3)=min{d(3) ;

d(4) a(4,3)}=min{11; 6 3}=9 d(5)=min{d(5);

d(4) a(4,5)}=min{8; 6 2}=8 d(6)=min{d(6);

d(4) a(4,6)}=min{12; 6 4}=10 d(7)=min{d(7);

d(4) a(4,7)}=min{7; 6 13}=7

Минимальную длину имеет путь от вершины 1 до вершины 7 d(7)=7. Включаем вершину №7 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (2,7) d(3)=min{d(3);

d(7) a(7,3)}=min{9; 7 7}=9 d(5)=min{d(5) ;

d(7) a(7,5)}=min{8; 7 5}=8 d(6)=min{d(6) ;

d(7) a(7,6)}=min{10; 7 4}=10

Минимальную длину имеет путь от вершины 1 до вершины 5 d(5)=8. Включаем вершину №5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,5) d(3)=min{d(3) ;

d(5) a(5,3)}=min{9; 8 6}=9 d(6)=min{d(6);

d(5) a(5,6)}=min{10; 8 1}=9

Минимальную длину имеет путь от вершины 1 до вершины 3 d(3)=9. Включаем вершину №3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (4,3) d(6)=min{d(6) ; d(3) a(3,6)}=min{9; 9 3}=9

Минимальную длину имеет путь от вершины 1 до вершины 6 d(6)=9. Включаем вершину №6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (5,6) Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа. d(1)=1 Длина маршрута L=0 d(2)=1-2 Длина маршрута L=5 d(3)=1-4-3 Длина маршрута L=9 d(4)=1-4 Длина маршрута L=6 d(5)=1-5 Длина маршрута L=8 d(6)=1-5-6 Длина маршрута L=9 d(7)=1-2-7 Длина маршрута L=7

3.Создание приложения для решения задачи

3.1 Описание алгоритма

Блок-схема в общем виде (Рисунок 1).

3.2 Разработка программы

Программу разрабатывал на языке программирования Delphi.

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

Создал button, при нажатии которой работает программа, в которой и прописан весь код.

3.3 Тестирование программы

Внешний вид программы (рисунок 2):

Рисунок 2 -Внешний вид программы.

Нажимаем кнопку «Выгрузить данные» и программа задает нам исходное значение (Рисунок 3):

Рисунок 3 - Выгружаем данные.

Нажимаем на кнопку «ОК» и программа выводит решение задачи (рисунок 4)

Рисунок 4- Результат.

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

3.4 Руководство пользователя

Запустив приложение, “Deykstra_v_1.2.exe” перед Вами откроется окно, дающее возможность решать задачу коммивояжера с помощью Алгоритма Дейкстры.

В поле «Начальная вершина» вводим вершину, с которой будет начинаться алгоритм. Далее, при нажатии кнопки «Выгрузить данные» перед Вами появится матрица расстояний между городами, определенная условием задачи. При нажатии кнопки «ОК» в поле «Ответы» будут выводиться ответы. При нажатии кнопки «Очистить» очистятся все поля.

Информацию о программе и руководство пользователя можно посмотреть в меню «Справка».

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

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

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

1.Новиков, Ф.А. Дискретная математика для программистов. - Санкт-Петербург: изд. дом «Питер», 2012.

2. Новиков, Ф.А. Дискретная математика: Учебник для вузов. Стандарт третьего поколения. - Санкт-Петербург: изд. дом «Питер», 2011.

3.Партыка, Т.Л., Попов, И.И. Математические методы - Москва: Форум, 2005.

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