Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

Узнайте стоимость индивидуальной работы

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


Нахождение кратчайших путей в графе Алгоритм Йена

Тип Реферат
Предмет Математика
Просмотров
861
Размер файла
115 б
Поделиться

Ознакомительный фрагмент работы:

Нахождение кратчайших путей в графе Алгоритм Йена

Содержание

1. Введение…………………………………………………………….

2. Логико-функциональная модель алгоритма………………………

2.1. Теоретические сведения………………………………………...

2.2. Алгоритм Дейкстры……………………………………………..

2.3. Алгоритм Йена…………………………………………………..

3. Блок-схема алгоритма……………………………………………...

4. Анализ сложности алгоритма……………………………………...

4. Разработка программы……………………………………………..

4.1. Реализация алгоритма Дейкстры………………………………

4.2. Реализация алгоритма Йена…………………………………….

5. Заключение………………………………………………………….

2

3

3

5

6

7

10

12

12

16

18

1. Введение

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

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

В исследовании этих двух алгоритмов собственно и состоит задача курсовой работы.


2. Логико-функциональная модель алгоритма

2.1. Теоретические сведения

В математической теории графов и информатике граф — это совокупность объектов со связями между ними.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах

Граф с шестью вершинами и семью ребрами

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

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

· V это множество вершин или узлов,

· E это множество рёбер – связей между парами вершин.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

СтепеньюdegV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Задачу составления алгоритма нахождения k кратчайших путей в графе условно можно разбить на две подзадачи:

1) Нахождение одного кратчайшего пути между двумя точками (реализуется алгоритм Дейкстры)

2) Нахождение k кратчайших путей между двумя точками (реализуется алгоритм Йена)

2.2. Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием “кратчайший путь — первый” (Shortest Path First)

Объяснение:

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

2.3. Алгоритм Йена

Этот алгоритм предполагает, что мы умеем находить один кратчайший путь в графе.

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

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

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

3. Блок-схема алгоритма

4. Анализ сложности алгоритма

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

Скорость выполнения можно легко измерить, используя стандартные функции языка PHP, на котором был написан алгоритм. При этом будем циклически высчитывать время, затраченное на обработку графов размерности от 3 до 19 вершин. См. рис. 1

Рис. 1 – Зависимость времени выполнения tот числа вершин n

Несложно заметить, что функция имеет вид параболы. Это означает, что с увеличением размера графа довольно резко возрастает и время выполнения. Таким образом, алгоритм будет работать эффективно с графами размером до 20 вершин. Что же касается графов с большим размером, то, к примеру, граф размером 30 вершин будет обрабатываться 195.74 секунд, то есть немногим больше 3 минут. Это не очень удобно, однако стоит заметить, что данный алгоритм тестировался на компьютере с тактовой частотой 2.02 ГГц, что не так уж много по сегодняшним меркам.

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

Как уже говорилось, задача нахождения k кратчайших путей в графе состоит из двух алгоритмов: алгоритма Дейкстры и алгоритма Йена

5.1. Реализация алгоритма Дейкстры

Прежде всего необходимо проинициализировать матрицу данных. Матрица данных представляет собой двухмерный массив, значениями которого являются длины ребер, которые соединяют точки, являющиеся в матрице координатами по x и по y. На примере рассмотрен такой граф:

$matrix = array(

array(0, 7, 9, 0, 0, 14),

array(0, 0,10,15, 0, 0),

array(0, 0, 0,11, 0, 2),

array(0, 0, 0, 0, 6, 0),

array(0, 0, 0, 0, 0, 9),

array(0, 0, 0, 0, 0, 0)

);

Таким образом видно, что вес ребра, соединяющего, к примеру, 2-ю и 5-ю точки будет соответствовать значению 2-го ряда и 5-го столбца (или 5-го ряда и 2-го столбца) в матрице.

Продолжаем инициализацию: переменная $start хранит номер исходной точки (начиная с нуля), переменная $end – конечной, одномерный массив $dist – кратчайшие расстояния от исходной точки до всех остальных, а двухмерный массив $way– кратчайшие пути в графе.

Всем элементам массива $dist (кроме $dist[$start]) присваивается значение, которое будет заведомо больше длины любого пути в графе. В программе это число 1000. Элементу $dist[$start] присваивается значение 0. Также присваиваем значение первому шагу в массиве путей: $way[$start][0] = $start. Все это имеет такой вид:

for ($i = 0; $i < MAX_NODES; $i++)

{

if ($i == $start)

$dist[$i] = 0;

else

$dist[$i] = INFINITY;

}

$way[$start][] = $start;

Далее начинается основная часть алгоритма. Проходим в цикле по каждой точке графа: находим точку с минимальным значением расстояния. Дляэтогоиспользуемфункцию minDist:

function minDist($dist)

{

global $checked;

$min_v = INFINITY;

for ($i = 0; $i < MAX_NODES; $i++)

{

if (!isset($checked[$i]) && $dist[$i] < $min_v)

{

$min = $i;

$min_v = $dist[$i];

}

}

$checked[$min] = true;

return $min;

}

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

for ($i = 0; $i < MAX_NODES; $i++)

{

$min = minDist($dist);

for ($j = 0; $j < MAX_NODES; $j++)

{

if ($dist[$min] + $matrix[$min][$j] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$min][$j];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

if ($dist[$min] + $matrix[$j][$min] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$j][$min];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

}

}

В результате получаем массив минимальных расстояний - $dist и двухмерный массив кратчайших путей - $way.

5.2. Реализация алгоритма Йена

Для нахождения k кратчайших путей в графе используется рекурсивная функция findWays, которая в качестве параметров принимает матрицу данных, номера исходной и конечной вершин. Алгоритм этой функции таков: выполняется поиск одного кратчайшего пути графа, проверяется, есть ли найденный путь в массиве путей $ways и, если нет – сохраняем путь и в цикле убираем по одному ребру в найденном пути и вызываем функцию findWays, передавая ей уже обновленную матрицу данных:

function findWays($matrix, $start, $end)

{

global $ways;

$res = findShortestWay($matrix, $start, $end);

if ($res != null && !in_array($res, $ways))

{

$ways[] = array();

$ways[count($ways)-1][1] = $res[1];

$ways[count($ways)-1][0] = $res[0];

for ($i = 0; $i < count($res[1])-1; $i++)

{

$invalid_matrix = $matrix;

$invalid_matrix[$res[1][$i]][$res[1][$i+1]] = INFINITY;

$invalid_matrix[$res[1][$i+1]][$res[1][$i]] = INFINITY;

findWays($invalid_matrix, $start, $end);

}

}

}

Стоит заметить, что массив $ways является трехмерным – первый ключ соответствует номеру пути, второй указывает на а) длину пути б) массив вершин пути

После этого выполняется сортировка полученного массива $ways по возрастанию по длине пути.

for ($i = 0; $i < count($ways)-1; $i++)

{

for ($j = $i+1; $j < count($ways); $j++)

{

if ($ways[$i][0] > $ways[$j][0])

{

$buf = $ways[$i];

$ways[$i] = $ways[$j];

$ways[$j] =$buf;

}

}

}

После возврата первых k элементов массива $ways наш алгоритм можно считать реализованным.

6. Заключение

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

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


Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
145460
рейтинг
icon
3086
работ сдано
icon
1335
отзывов
avatar
Математика
Физика
История
icon
142040
рейтинг
icon
5871
работ сдано
icon
2651
отзывов
avatar
Химия
Экономика
Биология
icon
94768
рейтинг
icon
2025
работ сдано
icon
1268
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
53 538 оценок star star star star star
среднее 4.9 из 5
МАДИ
Нормальная цена, быстрая и качественная работа, человеческие факторы) Всё супер, спасибо!
star star star star star
Университет Синергия
Огромное благодарность Вам! Приятно было с Вами работать.. Надеюсь и на дальнейшее сотрудн...
star star star star star
ТГУ
Спасибо большое за работу, выполненную досрочно и с высоким качеством! Всем рекомендую это...
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

создайте модель данных в веб-приложении Django и примените изменения в...

Решение задач, Средства програмной разработки

Срок сдачи к 17 июня

только что

реферат в соответствии с требованиями

Реферат, история государства и права России

Срок сдачи к 28 июня

1 минуту назад
1 минуту назад

чертеж компас а3

Чертеж, Инженерная графика

Срок сдачи к 18 июня

1 минуту назад

написать научную статью

Статья, Уголовная политика

Срок сдачи к 17 июля

1 минуту назад
3 минуты назад

Требований нет.

Курсовая, Технологические процессы технического обслуживания ремонта автомобилей

Срок сдачи к 30 июня

3 минуты назад

Сделать презентацию на по английскому

Презентация, Английский язык

Срок сдачи к 19 июня

4 минуты назад

Решить 6 задач по 4 варианта

Лабораторная, строительные машины

Срок сдачи к 20 июня

4 минуты назад

Произвести расчет и построить блок схему в Java.

Контрольная, Информатика в приложении к отрасли

Срок сдачи к 19 июня

5 минут назад

Сделать чертежи в Компас 3D.

Чертеж, Основы компьютерного инжиниринга.

Срок сдачи к 19 июня

5 минут назад

Ответить на несколько вопросов

Ответы на билеты, История

Срок сдачи к 19 июня

5 минут назад

Помощь на экзамене

Онлайн-помощь, Математика

Срок сдачи к 17 июня

6 минут назад
7 минут назад

Написать доклад по плану для защиты ВКР

Доклад, Юриспруденция

Срок сдачи к 18 июня

7 минут назад
7 минут назад

Необходимо написать приговор судебного заседания

Другое, Юриспруденция

Срок сдачи к 27 июня

8 минут назад

расчетно-графическую работу вариант 8

Контрольная, Теоретическая и прикладная механика, механика

Срок сдачи к 18 июня

8 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

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

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно