Содержание
Введение 4
Отображение алгоритмов 6
Метод Дейкстры розыска кратчайшего пути меж вершинами графа 6
Метод Прима розыска малого остовного бревна в графе 8
Осуществление алгоритмов 9
Тестирование алгоритмов 12
Доклад 18 с. , 6 рис. , 3 табл. , 7 источников, 1 прил.
ГРАФ, ВЕРШИНА, РЕБРО, КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО
Объектом изучения являются методы решения графовых задач.
Мишень работы - разработка алгоритмического и программного снабжения для решения задач розыска кратчайшего пути меж вершинами глава и малого остовного бревна глава.
В итоге изучений были осмотрены методы решения графовых задач.
Изобретен программный продукт на языке программирования высочайшего уровня Delphi, реализующий метод Дейкстры розыска кратчайшего пути меж вершинами глава.
Перечень использованных источников
ОмГТУ, Канева, первый курс, актуально для Заочного отделения, может быть и для Очного подойдет.
Содержание курсового проекта(КП)сообразно дисциплине \'Дискретная математика:"Разработка алгоритмического и программного снабжения для решения графовых задач"
Курсовой проект базируется на разработанной програмке на языке программирования - Delphi и подключает готовую, рабочую програмку в архиве, бросать необходимо Project1. exe
******************************************************
Само поручение фактически:
Методические указания к исполнению курсового проекта сообразно дисципли-не"Дискретная математика"
Содержание курсового проекта(КП)сообразно дисциплине"Дискретная математика: «Разработка алгоритмического и программного снабжения для решения графовых задач».
Задачка курсового проекта разработка и осуществление на языке программирования вы-сокого уровня личного либо уже имеющегося метода для решения последующих задач:
1)нахождения кратчайшего пути меж двумя данными вершинами глава;
2)нахождения малого остовного бревна глава.
В истоке курсового проектирования требуется ознакомиться с главными определе-ниями сообразно теме"Графы". Особенное интерес следует выкроить методу нахождения кратчай-шего пути меж двумя данными вершинами гафа и методу нахождения малого остовного бревна глава. Потом, применяя пригнанный перечень литературы, и привлекая раз-личные интернет-источники ознакомиться с состоянием вопросца на реальный момент сообразно решению задач 1 и 2. Итоги сообразно проведенному изучению оформляете в раздел"Вве-дение" отчета сообразно исполнению КП.
При исследовании либо разработке личного метода рекомендуется постановить практи-ческие задачки собственного варианта сообразно теме"Графы"(папка Практикум), а этак же выдумывать остальные тестовые задачки, какие позже будут Вами применены при тестировании разра-ботанного программного продукта(ПП). В разделе"Отображение метода" приводите вы-бранные Вами либо разработанные методы в форме"по шагам" с объяснениями всех обо-значений, какие применяете в описаниях алгоритмов. В этом же разделе приводите схемы алгоритмов(\"блок-схема").
Сообразно разработанным схемам реализуете методы на всяком языке программирования высочайшего уровня(Pascal, Delphi, C , C# и др. ). Для поручения глава рекомендуется использо-вать матрицу смежности либо инцидентности глава. Для тестирования правильности работы метода применяйте образцы, какие были прорешаны на шаге разработки метода. Приобретенный программный продукт непременно требуется протестировать на вариантах выро-жденного глава. Этак же требуется вести тестирование вашего ПП на графах большущий размерности(50 и наиболее вершин). Сообразно результатам проведенной работы оформляются разде-лы"Осуществление алгоритмов" и"Тестирование алгоритмов".
Целый листинг реализованного ПП приводится в прибавлении, а в разделе"Реализа-ция алгоритмов" требуется сориентировать и объяснить более достойные внимания и принципиальные моменты кода программ. Раздел"Тестирование алгоритмов" обязан кормить тестовую подборку, сообразно кото-рой разрешено изготовить вывод о правильности работы разработанных вами и реализованных ал-горитмов.
Выдержка
Введение
В крайние годы существенно возросла известность теории графов ветки дискретной арифметики. Графы видятся во почти всех областях под различными наименованиями:"структуры" в гражданском строительстве,"сети" в электронике,"социограммы" в социологии и экономике,"молекулярные структуры" в химии,"дорожные игра в карты", электрические либо газовые распределительные козни и т. д.
Родившись при решении головоломок и игр, таковых, к примеру, как задачка о кенигсбергских мостах и забава Гамильтона, концепция графов стала массивным средством изучения и решения почти всех задач, появляющихся при исследовании огромных и трудных систем.
Невзирая на обилие систем, представимых с поддержкой графов, разрешено отметить типовые графовые задачки.
1-ая из задач, решаемых на графах задачка розыска кратчайшего пути меж вершинами. Задачка розыска кратчайших стезей в графе(Shortest Path Problem)в общем случае содержится в последующем:
Заданы n вершин глава(узлов козни)v1, v2,. . vn и цельные длины дуг меж ними. Чему одинакова меньшая вероятная длина пути, водящего из vi в vj, для всех i и j?
Ежели длины дуг неотрицательны, то разрешено применять, к примеру, метод Дейкстры, ежели имеется отрицательные длины, однако недостает циклов отрицательного веса(ежели такие циклы имеется то рационального решения разумеется не есть), то разрешено применять метод Флойда-Уоршолла.
2-ая известная задачка задачка нахождения малого остовного бревна глава. Задачка о наименьшем остовном бревне(В английской литературе «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.
Литература
1. Метод Дейкстры //Википедия. [Электрический ресурс]. Режим доступа: http://ru. wikipedia. org/wiki/Алгоритм_Дейкстры
2. Алексеев В. Е. , Таланов В. А. Графы и методы. //Веб институт информационных технологий. [Электрический ресурс]. Режим доступа: http://www. intuit. ru/department/algorithms/gaa/15/
3. Кормен Т. , Лейзерсон Ч. , Ривест Р. Методы: построение и анализ. М. : Двучлен, 2000. 960с.
4. Красиков И. В. , Красикова И. Е. Методы элементарно как дважды 2. М. : Эксмо, 2007. 256с.
5. Новиков Ф. А. Дискретная математика для программистов. СПб. : Питер, 2004. 368с.
6. Розыск малого покрывающего бревна в графе(метод Прима). [Электрический ресурс]. Режим доступа: http://www. software. unn. ac. ru/cluster/cgi-bin/index. cgi ?id=101work=10topic=0
7. Рыбаков Г. Малые остовные деревья. //Дискретная математика: методы. [Электрический ресурс]. Режим доступа: http://rain. ifmo. ru/cat/view. php/theory/graph-spanning-trees/mst-2005
Введение
В последние годы значительно возросла популярность теории графов ветви дискретной математики. Графы встречаются во многих областях под разными назван