Курсовой проект, Дискретная математика, Канева, ОмГТУ..

Введение

В последние годы значительно возросла популярность теории графов ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" в электронике, "социограммы" в социологии и экономике, "молекулярные структуры" в химии, "дорожные карты", электрические или газовые распределительные сети и т. д.
Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем.
Несмотря на разнообразие систем, представимых с помощью графов, можно выделить типовые графовые задачи.
Первая из задач, решаемых на графах задача поиска кратчайшего пути между вершинами. Задача поиска кратчайших путей в графе (Shortest Path Problem) в общем случае заключается в следующем:
Заданы n вершин графа (узлов сети) v1, v2, .. vn и целые длины дуг между ними. Чему равна наименьшая возможная длина пути, ведущего из vi в vj, для всех i и j?
Если длины дуг неотрицательны, то можно использовать, например, алгоритм Дейкстры, если есть отрицательные длины, но нет циклов отрицательного веса (если такие циклы есть то оптимального решения очевидно не существует), то можно использовать алгоритм Флойда-Уоршолла.
Вторая распространенная задача задача нахождения минимального остовного дерева графа. Задача о минимальном остовном дереве (В англоязычной литературе «Minimum Spanning Tree»), заключается в следующем: задан связный неориентированный граф G=(V,E), где V множество вершин, |V|=n, E множество ребер между ними, и весовая функция .
Иными словами, есть n вершин v1, v2, .. vn и положительные целые веса дуг между ними. (Можно вводить веса на ребрах, как ).
Чему равен наименьший возможный вес остовного дерева? Т.е., требуется найти минимально возможное значение суммы где минимум берется по всем остовным деревьям на n вершинах, т. е. по всем множествам T из (n-1) дуг, связывающим все n вершин в единую сеть.
Для решения этой задачи можно применять алгоритм Прима или алгоритм Краскала (Kruskal).
В рамках данной работы более подробно будут рассмотрены алгоритм Дейкстры (на его основе будет написан программный продукт для поиска кратчайшего пути между вершинами графа) и алгоритм Прима.


Описание алгоритмов
Алгоритм Дейкстры поиска кратчайшего пути между вершинами графа

Каждой вершине i из V сопоставим метку d[i] минимальное известное расстояние от этой вершины до a вершины, пути из которой требуется найти. Алгоритм работает пошагово на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
1 этап - инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа, кроме a, помечаются как непосещенные (вектор done).
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина v, имеющая минимальную метку. Рассматриваются всевозможные маршруты, в которых v является предпоследним пунктом. Вершины u, соединенные с вершиной v ребрами, называются соседями этой вершины. Для каждого соседа рассчитывается новая длина пути, равная сумме текущей метки v и длины ребра, соединяющего v с этим соседом (w[v,u]). Если полученная длина меньше метки соседа, метка заменяется этой длиной. Вершину v помечают как посещенную и повторяют шаг.
Схема алгоритма (блок-схема) представлена на рисунке 1.

Содержание
Введение 4
Описание алгоритмов 6
Алгоритм Дейкстры поиска кратчайшего пути между вершинами графа 6
Алгоритм Прима поиска минимального остовного дерева в графе 8
Реализация алгоритмов 9
Тестирование алгоритмов 12

Отчет 18 с., 6 рис., 3 табл., 7 источников, 1 прил.
ГРАФ, ВЕРШИНА, РЕБРО, КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО
Объектом исследования являются алгоритмы решения графовых задач.
Цель работы - разработка алгоритмического и программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа и минимального остовного дерева графа.
В результате исследований были рассмотрены алгоритмы решения графовых задач.
Разработан программный продукт на языке программирования высокого уровня Delphi, реализующий алгоритм Дейкстры поиска кратчайшего пути между вершинами графа.
Список использованных источников
ОмГТУ, Канева, 1-ый курс, актуально для Заочного отделения, возможно и для Очного подойдет.

Тема курсового проекта (КП) по дисциплине 'Дискретная математика: "Разработка алгоритмического и программного обеспечения для решения графовых задач"

Курсовой проект основывается на разработанной программе на языке программирования - Delphi и включает готовую, рабочую программу в архиве, запускать нужно Project1.exe


******************************************************
Само задание собственно:

Методические указания к выполнению курсового проекта по дисципли-не "Дискретная математика"
Тема курсового проекта (КП) по дисциплине "Дискретная математика: «Разработка алгоритмического и программного обеспечения для решения графовых задач».

Задача курсового проекта разработка и реализация на языке программирования вы-сокого уровня собственного или уже существующего алгоритма для решения следующих задач:
1) нахождения кратчайшего пути между 2-мя заданными вершинами графа;
2) нахождения минимального остовного дерева графа.
В начале курсового проектирования требуется ознакомиться с основными определе-ниями по теме "Графы". Особое внимание следует уделить алгоритму нахождения кратчай-шего пути между 2-мя заданными вершинами гафа и алгоритму нахождения минимального остовного дерева графа. Затем, используя приведенный список литературы, и привлекая раз-личные интернет-источники ознакомиться с состоянием вопроса на настоящий момент по решению задач 1 и 2. Результаты по проведенному исследованию оформляете в раздел "Вве-дение" отчета по выполнению КП.
При изучении или разработке собственного алгоритма рекомендуется решить практи-ческие задачи своего варианта по теме "Графы" ( папка Практикум), а так же придумывать другие тестовые задачи, которые потом будут Вами использованы при тестировании разра-ботанного программного продукта (ПП). В разделе "Описание алгоритма" приводите вы-бранные Вами или разработанные алгоритмы в форме "по шагам" с пояснениями всех обо-значений, которые используете в описаниях алгоритмов. В этом же разделе приводите схемы алгоритмов ("блок-схема").
По разработанным схемам реализуете алгоритмы на любом языке программирования высокого уровня (Pascal, Delphi, C++, C# и др.). Для задания графа рекомендуется использо-вать матрицу смежности или инцидентности графа. Для тестирования правильности работы алгоритма используйте примеры, которые были прорешаны на этапе разработки алгоритма. Полученный программный продукт обязательно требуется протестировать на случаях выро-жденного графа. Так же требуется провести тестирование вашего ПП на графах большой размерности (50 и более вершин). По результатам проведенной работы оформляются разде-лы "Реализация алгоритмов" и "Тестирование алгоритмов".
Полный листинг реализованного ПП приводится в приложении, а в разделе "Реализа-ция алгоритмов" требуется указать и пояснить наиболее интересные и важные моменты кода программ. Раздел "Тестирование алгоритмов" должен содержать тестовую выборку, по кото-рой можно сделать вывод о правильности работы разработанных вами и реализованных ал-горитмов.

1. Алгоритм Дейкстры //Википедия. [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
2. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. //Интернет университет информационных технологий. [Электронный ресурс]. Режим доступа: http://www.intuit.ru/department/algorithms/gaa/15/
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Бином, 2000. 960с.
4. Красиков И.В., Красикова И.Е. Алгоритмы просто как дважды два. М.: Эксмо, 2007. 256с.
5. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2004. 368с.
6. Поиск минимального покрывающего дерева в графе (алгоритм Прима). [Электронный ресурс]. Режим доступа: http://www.software.unn.ac.ru/cluster/cgi-bin/index.cgi?id=101&work=10&topic=0
7. Рыбаков Г. Минимальные остовные деревья. //Дискретная математика: алгоритмы. [Электронный ресурс]. Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005