Задачи на алгоритм дейкстры

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

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

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Инициализация

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

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 Реализация на C++

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
<
int a[SIZE][SIZE]; // матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system( «chcp 1251» );
system( «cls» );
// Инициализация матрицы связей
for ( int i = 0; i for ( int j = i + 1; j "Введите расстояние %d — %d: " , i + 1, j + 1);
scanf( «%d» , &temp);
a[i][j] = temp;
a[j][i] = temp;
>
>
// Вывод матрицы связей
for ( int i = 0; i for ( int j = 0; j "%5d " , a[i][j]);
printf( "
" );
>
//Инициализация вершин и расстояний
for ( int i = 0; i // Шаг алгоритма
do <
minindex = 10000;
min = 10000;
for ( int i = 0; i // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i] // Переприсваиваем значения
min = d[i];
minindex = i;
>
>
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
<
for ( int i = 0; i if (a[minindex][i] > 0)
<
temp = min + a[minindex][i];
if (temp while (minindex // Вывод кратчайших расстояний до вершин
printf( "
Кратчайшие расстояния до вершин:
" );
for ( int i = 0; i "%5d " , d[i]);

// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 — 1
ver[0] = end + 1; // начальный элемент — конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины

while (end != begin_index) // пока не дошли до начальной вершины
<
for ( int i = 0; i // просматриваем все вершины
if (a[end][i] != 0) // если связь есть
<
int temp = weight — a[end][i]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
< // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
>
>
>
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf( "
Вывод кратчайшего пути
" );
for ( int i = k — 1; i >= 0; i--)
printf( "%3d " , ver[i]);
getchar(); getchar();
return 0;
>

Эта отрывок из бесплатной книги «Парадигмы алгоритмического проектирования (жадные алгоритмы, разделяй и властвуй и динамическое программирование)» -Brandon Algorithmic Design Paradigms (Greedy, Divide & Conquer, and Dynamic Programming)... ✨

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

Читайте также:  Как в ворде оформить содержание автоматически

Почему жадные алгоритмы называются жадными?

Алгоритмы называются жадными, когда они используют жадное свойство. Жадное свойство:

В каждый момент времени, что есть лучший выбор?

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

Для чего используются жадные алгоритмы?

Жадные алгоритмы очень быстрые. Намного быстрее, чем две другие альтернативы (Разделяй и властвуй — Divide & Conquer, и Динамическое программирование Dynamic Programming). Они популярные, потому что они быстрые.

Примеры популярных жадных алгоритмов:

Мы собираемся рассмотреть жадные алгоритмы, на известном примере — подсчет выдачи сдачи. Это не так сложно для этой парадигмы.

Как мне создать жадный алгоритм?

Ваш алгоритм должен всегда отвечать на этот вопрос:

Каков лучший выбор в этот момент времени?

Вот и все. Не так уж и много. Жадные алгоритмы, как правило, легче кодировать, чем «разделяй и властвуй»(Divide & Conquer) или динамическое программирование (Dynamic Programming).

Представьте, что вы торговый автомат. Кто-то дает вам £1 и покупает напиток за £0,70. В фунте стерлингов нет монеты 30 пенсов (30p). Как рассчитать, сколько сдачи вернуть?

Для справки, номинал каждой монеты в Великобритании:

Жадный алгоритм начинается с самого высокого номинала и работает в обратном направлении. Наш алгоритм начинается с £1.
£1 фунт больше, чем 30 пенсов, поэтому он не может его использовать. Далее смотрим на 50р, видим то же самое. Потом 20р. 20p 10p. Затем идет до 10р. Он выбирает 1 монету на 10p, и теперь возвращается 0, мы останавливаем алгоритм.

Итого мы возвращаем 1x20p и 1x10p.

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

Алгоритм попросили снова вернуть сдачу на 30p. 100р (£ 1) — это нет. То же самое для 50. Далее 20p, мы можем сделать это. Мы выбираем 1x 20p. Теперь нам нужно вернуть 10р. 20p закончилось, поэтому мы идем вниз на 1 номинал.

10p закончилось, поэтому мы идем далее вниз еще на 1 номинал.

У нас 5p, поэтому мы выбираем 1x5p. Теперь нам нужно вернуть еще . Проверяем 5p но они закончились, поэтому мы спускаемся вниз.

Мы выбираем 1 монету на 2p. Теперь нам нужно вернуть . Мы выбираем еще 2 монеты. Теперь нам нужно вернуть . Мы спускаемся еще раз вниз. Тут мы выбираем 1x1p монета.

В общем, наш алгоритм выбрал следующие монеты, чтобы вернуть сдачу:

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

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

Если наш список denominations такой же, как указано выше, то [6, 3, 0, 0, 0, 0, 0] представляет собой взятие 6 монет 1p и 3 монет 2p, но 0 всех других монет.

Создаем полный список denominations и отствующие значения заполним нулями.

Мы хотим пройтись от самого большого до самого маленького. Reversed(x) переворачивает x и позволяет нам зацикливаться в обратном направлении. Enumerate означает «цикл по этому списку, но сохраняйте позицию в другой переменной». В нашем примере, когда мы запускаем цикл. coin = 100 и pos = 6.

Наш следующий шаг — многократный выбор монеты, пока мы можем использовать эту монету. Если нам нужно дать сдачу change = 40, мы хотим, чтобы наш алгоритм выбрал 20, затем снова 20, пока он больше не сможет использовать 20. Мы делаем это с помощью цикла for.

В то время как coin все еще меньше или равно change, добавим эту coin в наш список возврата toGiveBack и удалим ее из сдачи.

Сложность выполнения этого алгоритма (О большое) определяется двумя циклами, поэтому оно равно O(n 2) .

Является ли жадный алгоритм лучшим? Жадность всегда работает?

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

Допустим у нас есть условие:

  • пусть у нас будет монеты трех номиналов [1p, 15p, 25p].

И нас попросим выдать сдачу в 30 пенсов. Теперь посмотрим, что вернет наш алгоритм.

То есть он выбирает 1x25p и 5x1p. Хотя лучшим решением будет — 2×15р.

Наш алгоритм потерпел неудачу, потому что он вообще не смотрел на 15p. Он первым делом посмотрел на 25р и подумал: «Да, это подходит. Давайте возьмем это».

Читайте также:  Бессмертный трон diablo 3 что делать

Затем он посмотрел на 15p и подумал, что «это не подходит, давайте двигаться дальше» (так как 25 + 15 > 30).

Это пример того, где жадные алгоритмы не лучший выбор.

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

Но жадные алгоритмы иногда могут быть лучшими на глобальном уровне то есть глобально оптимальными . Ранее мы видели, что эти алгоритмы глобально оптимальны:

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

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

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

Алгоритм следует следующим правилам:

  1. Каждый раз, когда мы хотим посетить новый узел, мы выберем узел с наименьшим известным расстоянием.
  2. Как только мы переместились в узел, мы проверяем каждый из соседних узлов. Мы вычисляем расстояние от соседних узлов до корневых узлов, суммируя стоимость ребер, которые ведут к этому новому узлу.
  3. Если расстояние до узла меньше известного расстояния, мы обновим самое короткое расстояние.

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

Мы отмечаем A в нашем списке не посещенных узлов. Расстояние от A до A равно 0. Расстояние от A до B равно 4. Расстояние от A до C равно 2. Наш список расстояний с правой стороны рисунка.

Затем мы выбираем наименьшее ребро, где вершина не была выбрана. Наименьшее ребро A ->C, и мы еще не выбрали C. Далее мы посещаем С.

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

Мы можем добраться до B из C. Теперь нам нужно выбрать минимум. min(4, 2 + 1) = 3.

Поскольку A->C->B меньше, чем A->B, мы обновляем B этой информацией. Затем мы добавляем расстояния от других узлов, которые теперь можем достичь.

Наша следующая наименьшая вершина с узлом, который мы еще не посетили, это B, с 3. Мы посещаем B.

Мы делаем то же самое для B. Затем мы выбираем самую маленькую вершину, которую мы еще не посетили, D.

На этот раз мы не обновляем расстояния. Наш последний узел тогда E.

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

Сначала мы выбираем A, затем C, а затем B. Если вам нужно создать кратчайший путь от A до каждого другого узла в виде графика, вы можете запустить этот алгоритм, используя таблицу с правой стороны.

Используя эту таблицу легко нарисовать кратчайшее расстояние от A до каждого другого узла на графике:

Дробная задача о ранце с использованием жадного алгоритма

Представь, что ты вор. Ты врываешься в дом Джуди Холлидей — обладателя Оскара 1951 года за лучшую женскую роль. Джуди кладезь драгоценных камней. Дом Джуди выложен до краев драгоценными камнями.

Ты принес с собой сумку — рюкзак. Максимальный вместимость этой сумки — 7 пунктов веса. У тебя был список всех предметов Джуди из какой-то страховой бумаги. Пункты читаются как:

Первым шагом к решению проблемы дробного ранца является расчет стоимости/веса для каждого предмета.

И теперь мы жадно отбираем самые крупные. Для этого мы можем отсортировать их по значению/весу в порядке убывания. К счастью для нас, они уже отсортированы. Самый большой — 3,2.

Затем мы выбираем Francium (я знаю, что это не драгоценный камень, но Джуди немного странная &#128521;)

Теперь мы добавляем Сапфир. Но если мы добавим Сапфир, наш общий вес достигнет 8 пунктов.

В задаче дробного ранца мы можем разрезать предметы, чтобы взять их дроби. У нас в сумке осталось 1 пункт веса. Наш сапфир имеет вес 2 пункта. Мы рассчитываем соотношение:

Свободное место в рюкзаке / вес товара

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

½ * 6 = 3

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

Сложность алгоритма для него O(n log n). Расчетное значение/вес O (1). Наш основной шаг — сортировка по наибольшему значению/весу, что занимает O(n log n) времени.

Заключение

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

Читайте также:  Вскоре начался дождь и ребята вынуждены

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

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

Для программной реализации алгоритма понадобиться два массива: логический visited — для хранения информации о посещенных вершинах и численный distance, в который будут заноситься найденные кратчайшие пути. Итак, имеется граф G=(V, E). Каждая из вершин входящих во множество V, изначально отмечена как не посещенная, т. е. элементам массива visited присвоено значение false.

Поскольку самые выгодные пути только предстоит найти, в каждый элемент вектора distance записывается такое число, которое заведомо больше любого потенциального пути (обычно это число называют бесконечностью, но в программе используют, например максимальное значение конкретного типа данных). В качестве исходного пункта выбирается вершина s и ей приписывается нулевой путь: distance[s]=0, т. к. нет ребра из s в s (метод не предусматривает петель).

Далее, находятся все соседние вершины (в которые есть ребро из s) [пусть таковыми будут t и u] и поочередно исследуются, а именно вычисляется стоимость маршрута из s поочередно в каждую из них:

  • distance[t]=distance[s]+весинцидентного s и t ребра;
  • distance[u]=distance[s]+ весинцидентного s и u ребра.

Но вполне вероятно, что в ту или иную вершину из s существует несколько путей, поэтому цену пути в такую вершину в массиве distance придется пересматривать, тогда наибольшее (неоптимальное) значение игнорируется, а наименьшее ставиться в соответствие вершине.

После обработки смежных с s вершин она помечается как посещенная: visited[s]=true, и активной становится та вершина, путь из s в которую минимален. Допустим, путь из s в u короче, чем из s в t, следовательно, вершина u становиться активной и выше описанным образом исследуются ее соседи, за исключением вершины s. Далее, u помечается как пройденная: visited[u]=true, активной становится вершина t, и вся процедура повторяется для нее. Алгоритм Дейкстры продолжается до тех пор, пока все доступные из s вершины не будут исследованы.

Теперь на конкретном графе проследим работу алгоритма, найдем все кратчайшие пути между истоковой и всеми остальными вершинами. Размер (количество ребер) изображенного ниже графа равен 7 (|E|=7), а порядок (количество вершин) — 6 (|V|=6). Это взвешенный граф, каждому из его ребер поставлено в соответствие некоторое числовое значение, поэтому ценность маршрута необязательно определяется числом ребер, лежащих между парой вершин.

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

У вершины 1 ровно 3 соседа (вершины 2, 3, 5), и чтобы вычислить длину пути до них нужно сложить вес дуг, лежащих между вершинами: 1 и 2, 1 и 3, 1 и 5 со значением первой вершины (с нулем):

Как уже отмечалось, получившиеся значения присваиваются вершинам, лишь в том случае если они «лучше» (меньше) тех которые значатся на настоящий момент. А так как каждое из трех чисел меньше бесконечности, они становятся новыми величинами, определяющими длину пути из вершины 1 до вершин 2, 3 и 5.

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

У вершины 2 всего один не рассмотренный сосед (вершина 1 помечена как посещенная), расстояние до которого из нее равно 9, но нам необходимо вычислить длину пути из истоковой вершины, для чего нужно сложить величину приписанную вершине 2 с весом дуги из нее в вершину 4

Условие «краткости» (10 10, поэтому новое значение игнорируется, старое остается.

Аналогичная ситуация с вершиной 6. Значение самого близкого пути до нее из вершины 1 равно 10, а оно получается только в том случае, если идти через вершину 5.

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

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