Поиск оптимального пути

Вокруг нас очень много информации. Для того, чтобы с информацией было проще работать, её структурируют и представляют в виде понятных и простых образов. Данные образы и называются информационными моделями. Формулы в учебнике по физике, таблицы с расписанием рейсов в аэропорту, схема эвакуации в торговом центре – это все информационные модели. По способу передачи информации модели делят на образные (рисунки, чертежи), знаковые (формулы, программы на языке программирования) и смешанные. В экзамене в первую очередь встречаются смешанные модели. В них входят таблицы, графики, диаграммы и схемы. Среди схем самыми важными для экзамена являются графы (ориентированные и не ориентированные) и деревья.

Граф

С помощью графа удобно описать, например, схему дорог с указанием расстояния между всеми пунктами. На примере ниже приведена карта (сверху) и построенный по ней граф (снизу):

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

Дерево

Данный вид графа имеет ветвистую структуру, поэтому и получил такое название:

Таблица

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

Построение дерева по таблице и алгоритм Дейкстры

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

Есть 2 способа решения данного задания:

1) Построить дерево по заданной таблице.

2) Применить алгоритм Дейкстры

Начнем с первого способа. Нам необходимо построить граф, соответствующий заданной таблице. Из всех видов графов для этой задачи подойдет дерево, его мы и будем строить. Из вершины А можно попасть в вершины Б, В и Д (длины путей соответственно 2, 5 и 10):

Из вершины Б можно попасть в вершины В и Г (длины путей соответственно, 2 и 5):

Из вершины В можно попасть только в вершину Г (длина дороги – 2):

Из вершины Г есть путь только в вершину Д (длина пути – 1):

Получаем, что кратчайший путь – это А-Б-В-Г-Д, длина которого равна 7.

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

Первое, и самое важное, - правильно нарисовать граф.

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

Отметим начало и конец.

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

Начинаем со стартовой вершины. Рассматриваем возможные передвижения из нее. То есть в

вершины Б, В и Д. Рассчитываем новую временную вершину следующим образом:

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

вершине:

Для вершины Б: 0 + 2 = 2

Для вершины В: 0 + 5 = 5

Для вершины В: 0 + 10 = 10

Далее определяем, является ли новая метка, меньше чем предыдущая?

Для вершины Б: 2 меньше чем бесконечность, поэтому бесконечность зачеркиваем и пишем

новую временную метку – 2.

Для вершины В: аналогично. Зачеркиваем предыдущую временную метку, и ставим новую – 5.

Для вершины Д: аналогично. Зачеркиваем предыдущую временную метку, и ставим новую – 10.

Так как мы рассмотрели вершину А, ее временная метка становится постоянной и не может быть

изменена.

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

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

В нашем случае это вершина Б.

Б–В: 2 + 2 = 4. Четверка меньше пяти, поэтому зачеркиваем 5, и ставим новую метку – 4.

Б–Г: 2 + 5 = 7. Семь меньше бесконечности, поэтому зачеркиваем бесконечность, и ставим

новую метку – 7.

Делаем временную метку 2 у вершины Б постоянной, тем самым показывая, что эта вершина

рассмотрена.

Следующая вершина – В.

В–Г: 4 + 2 = 6. Шесть меньше чем 7, поэтому зачеркиваем 7, и ставим новую временную метку – 6.

Временная метка у В теперь постоянная.

Идем в вершину Г.

Из нее ведет только одна дорога – в Д.

Г-Д: 6 + 1 = 7. Семь меньше чем 10, потому зачеркиваем 10, и ставим новую временную метку – 7.

Временная метка у Г теперь постоянная.

Остается последняя вершина Д, которая является конечной. И ее временная метка становится

постоянной и является ответом на нашу задачу. Кратчайший путь между вершинами А и Д – 7.

Ответ сошелся с предыдущим способом!

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

Нахождение оптимального пути с дополнительными условиями

Стоит отметить, что в задании на поиск оптимального пути бывают прототипы с дополнительными условиями:

1. Нельзя проходить через указанный пункт.
2. Нужно обязательно пройти через указанный пункт.

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

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

Дальше по уже упрощённой таблице мы решаем задание любым из двух методов.

При использовании дерева решение будет выглядеть следующим образом:

Минимальный путь, с учетом дополнительного условия, получился А-Б-Г-Д, то есть в ответ мы напишем 8.

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

После преобразования графа, применяем алгоритм для нахождения оптимального пути:

Видим, что получившийся ответ совпал с ответом, полученным при решении деревом. Итоговый ответ – 8.

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

Минимальный путь, с учетом дополнительного условия, получился А-Б-В-Г-Д, то есть в ответ мы напишем 7.