Как найти самый короткий путь информатика

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

1. начальному пункту всегда присваиваем значение 0.
2. чтобы найти метку для пункта 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 в остальные пункты.

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

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

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

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

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

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

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

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

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

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

Добрый день! Сегодня посмотрим, как “бороться” с 4 заданием из ОГЭ по информатике 2023.

Четвёртное задание из ОГЭ по информатике достаточно простое, хотя и может показаться кому-то скучным.

Рассмотрим простой пример из тренировочных заданий для 4 задания.

Задача (Стандартная)

Между населёнными пунктами A, B, C, D построены дороги, протяжённость которых (в километрах) приведена в таблице.

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

Решение:

Расставим точки, которые символизируют города, примерно по кругу.

Проведём дороги между городами так, как указано в таблице. Если на пересечении городов стоит число, значит, мы проводим линию между этими точками.

Поставим числа над каждой дорогой, характеризующие длины каждого отрезка.

Теперь найдём самый короткий путь из A в C.

Можно сразу попасть из A в C по прямой дороге за 8. Если пойдём через пункт D, то придём в город C за 7. Через город B так же можно прийти за 7 километров.

Но мы видим, что длина дороги из D в B равна 1. Попытаемся эту дорогу использовать при составлении маршрута. Получим путь: A-D-B-C. Получается 3+1+2=6. Это и есть искомый кратчайший путь.

Ответ: 6

Задача (C обязательным узлом)

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых
(в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С.
Передвигаться можно только по дорогам, протяжённость которых указана в таблице, два раза
посещать один пункт нельзя.

Решение:

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

Проведём линии между городами так, как указано в задаче. Поставим числа над каждой дорогой, чтобы было понятно, к какой дороге конкретное число принадлежит.

Теперь можно начать искать кратчайший путь от A до E, проходящего через C.

Найдём кратчайший путь до точки С. Это и есть путь A-C. Он равен 5.

От С до E можно добраться разными путями:

C-E = 8
C-D-E = 2 + 5 = 7
C-B-E = 4 + 3 = 7

Это и есть самый короткий путь.

В ответе напишем путь: A-C-D-B-E = 5 + 6 = 11.

Ответ: 11

Задача (Закрепление)

Между населёнными пунктами А, B, С, D, E, F построены дороги, протяжённости которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение:

Расставим точки А, B, С, D, E, F по кругу.

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

Получилась наглядная карта городов. Оценив все пути от пункта A до пункта F, определяем, что самый короткий путь будет 4 + 3 + 4 + 3 = 14.

Ответ: 14.

Учимся находить кратчайший путь через простой двумерный алгоритм на Python

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

Поиск пути – типичная задача программирования, решаемая в самых разных ситуациях. Она известна в основном из навигационных задач и разработки игр. Но, изучив ключевые алгоритмы поиска пути, вы узнаете, что они применимы к более абстрактным задачам оптимизации и построения последовательностей.

В этом руководстве рассмотрен простейший алгоритм поиска пути, основанный на алгоритме Дейкстры. Этот алгоритм также известен под названием поиск по первому наилучшему совпадению, ключевая логика у него общая со многими другими алгоритмами, например, A*, заливка методом наводнения и диаграммы Вороного.

Здесь мы рассмотрим практическое применение этого алгоритма. Вам понадобятся базовые знания программирования и языка Python.

Настройка Python

Весь код к этому посту находится в репозитории path-finding. Его нужно клонировать и переключиться в ветку tutorial_1. Также установите пакет pygame, он понадобится нам для графики.

python3 -m pip install -U pygame
git clone git@github.com:mortoray/path-finding.git
cd path-finding
git checkout path_finding_1

Теперь проверим, все ли сделали правильно:

python3 find-basic.py

Должно появиться окно с клетками, а в клетках – цифры. Теперь можете закрыть это окно. Мы вернемся к нему позже.

Лабиринт

Поиск пути – это продвижение из точки А в точку B. Алгоритм может описывать прогулку человека по парку, движение автомобиля по городу, либо курс персонажа, который преследует вас в игре. Давайте сведем все эти окружения к абстракции, которую назовем «лабиринт».

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

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

Запускаем код

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

import mortoray_path_finding as mpf

maze = mpf.create_wall_maze( 20, 12 )

Мы создали лабиринт размером 20x12. Поле maze.board – это решетка из объектов Cell. Нам нужен способ отобразить наш лабиринт.

finder = mpf.Finder()
finder.set_board(maze.board)
finder.run()

Исходный файл: tutorial_1_1.py

Finder – это утилита, отображающая за нас лабиринт. Серые клетки свободны, то есть, путь может пройти через них. Коричневые клетки – это стены, через них путь пройти не может. В каждой из клеток также записан ноль, это значение Cell.count для данной позиции. Оно пригодится нам при поиске пути.

Измерение расстояния

Поиск пути во многом основан на исходном алгоритме Дейкстры. Существует множество его вариаций, например, алгоритм Флойда-Уоршелла, он же B*. Они действуют по схожему принципу: в них используются списки узлов и подсчитывается расстояние. Для разных ситуаций можно сочетать различные приемы.

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

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

1. Получаем из списка открытых узлов тот узел, от которого нас отделяет наименьшее расстояние  

2. Вычисляем расстояние до каждого из соседних узлов

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

Термины

Для начала рассмотрим некоторые термины, поскольку они могут быть вам неизвестны.

«Узел» – это общий термин, применимый в графах любых типов. Узел может представлять собой пересечение дорог на карте или, в нашем случае, стык клеток в лабиринте. У каждого узла есть местоположение, и от узла прокладываются пути к ближайшим узлам. В теории графов узлы также называются «вершинами».

Узлы, которые можно соединить, проложив между ними путь, являются соседними. Путь между узлами-соседями характеризуется расстоянием, для которого есть более общий термин «стоимость». В теории графов путь называют «ребром».

«Список открытых узлов» – это в буквальном смысле список узлов. «Открытые» узлы – это узлы, которые алгоритм все равно должен проверить. Например, если вы ищете елочные игрушки, разложенные в ящиках у вас в подвале, то вы просматриваете каждый из ящиков и отмечаете его в списке. Если внутри большого ящика обнаружатся более мелкие, то их также можно добавить в список.

Алгоритм

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

def fill_shortest_path(board, start, end, max_distance = math.inf):
  nboard = board.clone()
  nboard.clear_count(math.inf)

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

nboard.at( start ).count = 0
    
open_list = [ start ]

Этого достаточно, чтобы запустить алгоритм. Перебираем узлы, пока open_list не опустеет.

  while open_list:
    	cur_pos = open_list.pop(0)
    	cur_cell = nboard.at( cur_pos )

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

Для каждого узла рассмотрим всех его соседей.

# (x,y) смещения от текущей клетки
neighbours = [ [-1,0], [1,0], [0,-1], [0,1] ]
for neighbour in neighbours:
  ncell_pos = mpf.add_point(cur_pos, neighbour)
  if not nboard.is_valid_point(ncell_pos):
continue
  
  cell = nboard.at( ncell_pos )

Каждый элемент в neighbors – это Евклидово смещение от текущей клетки до соседней. Например, [-1,0] – это сосед слева. Если cur_pos равно [ 5, 7 ], то сложив его с [-1, 0] получим [4, 7], то есть, ход на клетку влево. Аналогично, [1,0] – это движение в положительном направлении по оси x, то есть, на клетку вправо. [0,-1] влияет только на y и является переходом на одну позицию вверх, тогда как [0,1] – на одну вниз.

Пользуясь численными абстракциями направлений, можно в рамках данного алгоритма точно так же обработать любые другие переходы. Можно учесть и другие направления, например, [1,1], это ход по диагонали вверх и далее вправо. Но при этом мы должны держать в уме и края решетки, за что и отвечает is_valid_point. Например, если мы дойдем до правого края решетки,  то смещение [1,0], соответствующее одному переходу вправо, выведет нас за пределы графа, поэтому мы такой ход пропустим.

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

if cell.type != mpf.CellType.Empty:
  continue

Переходим к вычислению расстояния.

dist = cur_cell.count + 1

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

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

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

Используем обобщенное поле cell.count для измерения расстояния, а также обновим поле path_from, указывающее, каким путем мы пришли в данную точку.

Ранее мы говорили, что первым в open_list всегда идет узел с наименьшим значением count. Уже понятно, почему, ведь каждый соседний узел удален от нас ровно на 1. Стартовый узел считается как 0, поэтому добавляем в список открытых несколько узлов, значения которых равны 1. Теперь, поскольку все узлы мы обрабатываем по порядку, добавляем в список несколько двоек, пока не будут охвачены все единицы. В итоге у нас в списке останутся двойки. Продолжим охватывать двойки, также добавляя в список некоторые тройки.

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

Визуализируем

Давайте уделим немного времени визуализации. Вызовем fill_shortest_path из кода, входящего в дистрибутив.

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.run()

Исходник: tutorial_1_2.py

Откроется такое окно, как показано ниже. Стартовая клетка обозначена желтым, в ней стоит 0. Числа увеличиваются по мере отдаления от этой точки, с инкрементом в единицу. Все клетки в решетке обозначены в соответствии с манхэттенским расстоянием от стартовой точки до них. Находим клетку, обозначенную зеленым, и вычисляем, каково расстояние от стартовой точки до нее.

Получение пути

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

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

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

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

if cell.count > dist:
  cell.count = dist
  cell.path_from = cur_cell
  open_list.append(ncell_pos)

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

def backtrack_to_start(board, end):
  """ Возвращает путь до конечной точки, при этом предполагается, что поле заполнялось при помощи алгоритма fill_shortest_path """
  cell = board.at( end )
  path = []
  while cell != None:
    	path.append(cell)
    	cell = cell.path_from
   	 
  return path

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

import mortoray_path_finding as mpf
    
maze = mpf.maze.create_wall_maze( 20, 12 )
filled = mpf.tutorial_1.fill_shortest_path(maze.board, maze.start, maze.end)
path = mpf.tutorial_1.backtrack_to_start(filled, maze.end)

finder = mpf.draw.Finder()
finder.set_board(filled)
finder.set_path(path)
finder.run()

Исходник: tutorial_1_3.py

Здесь есть любопытный момент: функция fill_shortest_path вычисляет расстояние «от старта» для каждой клетки, а не только для конечной. Тот же самый код для отслеживания обратного пути до любого узла. Оказывается, такие исчерпывающие знания могут во многих отношениях пригодиться при поиске пути. Но, если наша приоритетная цель – оптимизация, то мы адаптируем алгоритм так, чтобы он прекращал поиск, как только найдет выход из лабиринта. Также есть алгоритм A*, использующий эвристику, которая позволяет обходиться без сканирования всей карты.

Заключение

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