306 подписчиков

Задание 1 ЕГЭ-2023 и задание 4 ОГЭ-2023 по информатике | Алгоритм Дейкстры по поиску кратчайшего пути

21 июля 202221 июл 2022

1165

4 мин

Всем привет, меня зовут Елена и мы продолжаем разбирать задачи из ЕГЭ по информатике. В прошлой статье мы рассмотрели азы теории графов, научились решать задачи на сопоставление двух информационных моделей - графа и таблицы. В конце были приведены задачи для самостоятельного разбора. Все ли удалось?) Если есть какие-то вопросы по задачам, пишите в комментарии, дам подсказку или разберу сложную задачу подробно. В этой статье опишу алгоритм, позволяющий решать остальные задачи первого типа, подробно рассмотрим его работу на примере. Приведу блок-схему алгоритма и дам подборку задач ЕГЭ по теме. Заметка для сдающих ОГЭ С помощью этого алгоритма вы сможете решать задачи типа 4. Возможно, алгоритм покажется вам сложным, но не бойтесь разобраться с ним. Помните, что привыкание - ключ к пониманию. Вернитесь к описанию алгоритма, разберите несколько номеров, двигаясь по блок-схеме. У вас получится! Алгоритм Дейкстры Область применения Сегодня разберем задачи первого типа на поиск кратчайшего

Оглавление

Алгоритм Дейкстры
Область применения
Формулировка условия

Всем привет, меня зовут Елена и мы продолжаем разбирать задачи из ЕГЭ по информатике.

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

Все ли удалось?) Если есть какие-то вопросы по задачам, пишите в комментарии, дам подсказку или разберу сложную задачу подробно.

В этой статье опишу алгоритм, позволяющий решать остальные задачи первого типа, подробно рассмотрим его работу на примере. Приведу блок-схему алгоритма и дам подборку задач ЕГЭ по теме.

Заметка для сдающих ОГЭ

С помощью этого алгоритма вы сможете решать задачи типа 4. Возможно, алгоритм покажется вам сложным, но не бойтесь разобраться с ним. Помните, что привыкание - ключ к пониманию. Вернитесь к описанию алгоритма, разберите несколько номеров, двигаясь по блок-схеме. У вас получится!

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

Область применения

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

Будем решать задачу из примера на Википедии (чтобы сравнить ответ), используя мою схему.

Формулировка условия

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

Решение

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

Пока запоминаем следующие правила:

начальному пункту всегда присваиваем значение 0.
чтобы найти метку для пункта B, нужно к значению метки для пункта A прибавить длину дороги AB.

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

Рисуем следующую схему. Располагаем начальный пункт сверху, рисуем от него три стрелки - дороги в соседние пункты (2, 3 и 6, оранжевым написаны длины этих дорог). Рядом с ними ставим метки (отмечены фиолетовым цветом) - длину маршрута до пункта.

Пункт 1 можно считать посещенным - всю возможную информацию из него мы вытянули (далее отмечен крестиком). Переходим к следующему пункту. К какому? Непосещенному с минимальной меткой. В нашем примере это пункт 2 с меткой 7.

Обрабатываем соседние с пунктом 2 вершины:

вершина 1 посещенная, ничего делать не нужно;
вершина 3. Проверяем, будет ли путь к пункту 3 через 2 короче, чем стоящая у пункта 3 метка (метка пункта 3 равна 9, длина пути в п.3 через п.2 будет равен сумме метки п.2 и длины дороги из 2 в 3: 7+10 = 17 > 9. Видим, что длина дороги 1-3 короче, чем длина пути 1-2-3. Метку у пункта 3 менять не нужно. Дорогу рисуем пунктиром - чтобы видеть, что мы ее обрабатывали);
вершины 4 еще нет на нашей схеме, добавляем, считаем метку для нее: к метке п.2 прибавляем длину дороги 2-4, получаем 7+15=22.

После этого отмечаем вершину 2 как посещенную.

Снова переходим к непосещенной вершине с минимальной меткой - вершине 3.

Соседние с ней вершины: 1, 2, 4, 6.

Вершины 1 и 2 посещенные.
Вершина 4. Проверяем сумму метки п.3 и дороги 3-4: 9+11 = 20 < 22. Получается, что более короткий путь до вершины 4 проходит через п.3. Тогда дорога 2-4 на нашей схеме лишняя, вычеркиваем ее (я отметила ее пунктиром). Метку у вершины 4 меняем на 20.
Вершина 6. Проверяем сумму метки п.3 и дороги 3-6: 9 + 2 = 11 < 14. Вычеркиваем дорогу 1-6, меняем значение метки п.6 на 11.

Теперь непосещенной вершиной с минимальной меткой является п.6. Его соседи - вершины 1, 3 (посещенные) и 5 (не отмечен на нашей схеме). Добавляем п.5 на схему, считаем его метку. Вычеркиваем п.6 как посещенный.

Осталось два непосещенных пункта - 4 и 5. Можем обрабатывать их в любом порядке.

Рассмотрим п.4. Он связан с вершинами 2, 3 (посещенные) и 5. Если попробуем пройти в п.5 через п.4, дорога займет 20 + 6 = 26 > 20 - метку у п.5 менять не нужно, п.4 отмечаем как посещенный.

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

Фиолетовые числа возле чисел - конечные метки, равные кратчайшим маршрутам из п.1 в остальные пункты.

Хотите пройтись по алгоритму еще раз? Для вашего удобства повторю в галерее все шаги:

Ставим метку 0 у начального пункта.
Метки его соседей меняем на значения длин дорог от начального пункта до соседних. — Ставим метку 0 у начального пункта. Метки его соседей меняем на значения длин дорог от начального пункта до соседних.

Отмечаем п.1 как посещенный.
Выбираем пункт с минимальной меткой (п.2). Рассматриваем его соседей: ничего не делаем с посещенным п.1; добавляем п.4 на схему как новый, считаем его метку как сумму метки п.2 и длины дороги 2-4; проверяем, будет ли длина пути в п.3 через п.2 меньше метки у п.3.
Отмечаем п.2 как посещенный. — Отмечаем п.1 как посещенный. Выбираем пункт с минимальной меткой (п.2). Рассматриваем его соседей: ничего не делаем с посещенным п.1; добавляем п.4 на схему как новый, считаем его метку как сумму метки п.2 и длины дороги 2-4; проверяем, будет ли длина пути в п.3 через п.2 меньше метки у п.3. Отмечаем п.2 как посещенный.

Пункт с минимальной меткой - п.3.
1) Соседние п.1 и п.2 посещены.
2) Проверяем, будет ли длина пути через п.3 в п.4 меньше, чем метка у п.4 - да. Добавляем дорогу 3-4, переписываем метку у п.4, вычеркиваем ведущую в п.4 дорогу 2-4.
3) Проверяем, будет ли длина пути через п.3 в п.6 меньше, чем его метка. Действуем аналогично п.2)
4) Вычеркиваем п.3 как посещенный. — Пункт с минимальной меткой - п.3. 1) Соседние п.1 и п.2 посещены. 2) Проверяем, будет ли длина пути через п.3 в п.4 меньше, чем метка у п.4 - да. Добавляем дорогу 3-4, переписываем метку у п.4, вычеркиваем ведущую в п.4 дорогу 2-4. 3) Проверяем, будет ли длина пути через п.3 в п.6 меньше, чем его метка. Действуем аналогично п.2) 4) Вычеркиваем п.3 как посещенный.

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

Исходный граф может иметь много вершин, что затрудняет решение задачи (придется делать много перекрывающих друг друга пометок).
Но главное: при решении задачи моим способом (не авторским, а подсмотренным где-то на просторах интернета) мы сразу можем ответить на вопросы в нескольких формулировках, предлагаемых в заданиях для подготовки к ЕГЭ (через сколько пунктов проходит кратчайший путь из пункта А в пункт К? Какова длина самой длинной дороги кратчайшего пути? Перечислите все пункты, через которые проходит кратчайший маршрут).

Блок-схема алгоритма Дейкстры

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

Домашнее задание

Не вижу смысла решать здесь какую-то задачу из ЕГЭ, так как алгоритм решения будет точно такой, как и в рассмотренном примере. Лучше дам список задач для самостоятельной отработки. Если возникают сложности - пишите в комментариях, постараюсь помочь. Также буду рада обратной связи по материалу. Все ли понятно? Может, что-то нуждается в большей подробности?

Домашка! Заходим на сайт К.Полякова, находим номера №№ 1591, 1596, 3641, 1601, 5026, 92, 86. Успехов!

Напоминалочка

Если вам нужна помощь в подготовке к ЕГЭ или ОГЭ по информатике, пишите, у меня еще есть окошки! Провожу занятия офлайн с использованием графического планшета, записи с занятия высылаю pdf-файлом.