Поиск кратчайших путей с помощью поиска в ширину

1656581185 poisk kratchajshih putej s pomoshhyu poiska v shirinu

автор Сачин Малхотра

gOEnW7rmb55Rc4jGcDNTMizBtDmIi0X0kuuv

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

6eQAOZ4fqSw7oBxo8eAFormyD7h6woe8upoG
Источник: https://www.statista.com/statistics/564769/airline-industry-number-of-flights/

По данным Международной организации гражданской авиации (ICAO), в 2017 году авиационная отрасль перевезла рекордные 4,1 млрд пассажиров на регулярных рейсах. А количество рейсов в мире выросло до 37 миллионов в 2017 году.

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

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

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

Давайте посмотрим, сколько вариантов перелета StudentUniverse (предоставляет скидки для студентов?) предоставляет мне из Лос-Анджелеса в Нью-Дели.

X9oBIPVUCIw5YKvkkmc8TymNyLLWtZdKto31
Каждый рейс имеет гиперссылку «Детали», поэтому мы искали его и нашли 119 рейсов.

Всего предлагается 119 рейсов. Затем на веб-сайте появляется всплывающее окно с сообщением, что есть другие веб-сайты, которые могут предлагать подобные рейсы по более дешевым тарифам. ?

Так много веб-сайтов и бесчисленное количество авиарейсов только для одного источника и места назначения.

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

  • Общее количество доступных пунктов назначения (с максимальным количеством остановок) из моего текущего местоположения, а также список этих пунктов назначения.
    Надо оставлять свои возможности открытыми, когда они хотят путешествовать?
  • Известен факт (ИМО?), что маршрут с несколькими остановками, как правило, является более дешевой альтернативой прямым рейсам.
    Итак, учитывая источник и пункт назначения, мы можем захотеть найти маршруты по крайней мере 2-3 остановками.
  • Самое важное: какой самый дешевый маршрут от определенного источника к данному пункту назначения?
  • И…. В конце концов мы придем к этому?

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

Моделирование сети полетов в виде графика

Из заголовка этой статьи достаточно ясно, что графики будут где-то задействованы, не правда ли?

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

Мы моделируем воздушное движение как:

  • направленный
  • возможно, циклический
  • взвешенный
  • лес. G(V, E)

Режиссерский потому что каждый рейс будет иметь определенный источник и пункт назначения. Они несут много смысла.

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

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

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

вершины, Вбудут местами по всему миру, где есть действующие аэропорты.

Края, Е, будет репрезентативным для всех рейсов, составляющих воздушное движение. Край от u -->; v просто означает, что у вас есть прямой рейс с места/нетdЕС tов.

fUMFpsXMA9AJOyZjsIVzphouaIrojTB3nPbq
Образец сети рейсов с маркировкой стоимости для разных рейсов.

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

Общее количество доступных мест назначения

Кто не любит путешествовать?

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

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

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

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

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

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

Теперь, когда у нас есть хорошее представление о том, как инициализировать график, давайте посмотрим на код алгоритма BFS.

Выполнение bfs в Лос-Анджелесе даст нам следующие направления, до которых можно добраться:

{'Chicago', 'France', 'Ireland', 'Italy', 'Japan', 'New Delhi', 'Norway'}

Это было просто, не правда ли?

Мы рассмотрим, как мы можем ограничить BFS максимальным количеством остановок позже в статье.

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

Это случай использования, если сеть рейсов очень мала или касается только нескольких регионов Соединенных Штатов.

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

Маршруты с несколькими остановками

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

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

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

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

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

Как конечный пользователь мы можем не захотеть видеть рейсы в таком порядке для этого запроса:

[A, C, D, B]2 остановки, $X[A, E, D, C, F, W, G, T, B]8 остановок, млн. долл.[A, R, E, G, B]3 остановки, $K[A, Z, X, C, V, B, N, S, D, F, G, H, B, 11 stops, $P

I know. Nobody in their right minds would want to go for a flight route with 11 stops. But the point I’m trying to make is that an end user would want symmetry. Meaning that they would want to see all the flights with 2 stops first, then all the flights with 3 stops and so on till maybe a max of, say, 5 stops.

But, all the flight routes with the same number of stops in between should be displayed together. That is a requirement we need to satisfy.

Let’s look at how we can solve this. So, given the graph of flight networks, a source S and a destination D, we have to perform a level order traversal and report flight routes from S -->; D with at least 2 and at most 5 stops in between. This means we have to do a level order traversal until a depth of 7 from the start node S .

Have a look at the code for solving this problem:

This might not be the best way to go about solving this problem at scale — the largest memory constraint would be due to the nodes currently present in the queue.

Since every node or location can have thousands of flights to other destinations in the world, the queue could be humongous if we store actual flight data like this. This is just to demonstrate one of the use cases of the breadth first search algorithm.

Now, let us just focus on the traversal and look at the way it is done. The traversal algorithm is simple as it is. However, the entire space complexity of the level order traversal comes from the elements in the queue and the size of each element.

There are multiple ways to implement the algorithm. Also, each of them varies in terms of maximum memory consumed at any given time by the elements in the queue.

We want to see the maximum memory consumed by the queue at any point in time during the level order traversal. Before that, let’s construct a random flight network with random prices.

Now let us look at the implementation of level order traversal.

This above is the easiest and most straightforward implementation of the level order traversal algorithm.

With every node we add to the queue, we also store the level information and we push a tuple of (node, level) into the queue. So every time we pop an element from the queue, we have the level information attached with the node itself.

The level information for our use case would mean the number of stops from the source to this location in the flight route.

It turns out that we can do better as far as memory consumption of the program is concerned. Let us look at a slightly better approach to doing level order traversal.

The idea here is that we don’t store any additional information with the nodes being pushed into the queue. We use a None object to mark the end of a given level. We don’t know the size of any level before hand except for the first level, which just has our source node.

So, we start the queue with [source, None] и мы продолжаем отображать элементы. Каждый раз, когда мы сталкиваемся с а None элемент, мы знаем, что уровень истек и начался новый. Подталкиваем другого None чтобы отметить конец этого нового уровня.

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

goYMjFvXtEMQAndVXKeUTy2gPORYPARq1H3k
**************************************************** LEVEL 0 beginslevel = 0, queue = [A, None]level = 0, pop, A, push, B, C, queue = [None, B, C]pop None ******************************************* LEVEL 1 beginspush Nonelevel = 1, queue = [B, C, None]level = 1, pop, B, push, C, D, F, queue = [C, None, C, D, F]level = 1, pop, C, push, D, D (lol!), queue = [None, C, D, F, D, D]pop None ******************************************* LEVEL 2 beginspush Nonelevel = 2, queue = [C, D, F, D, D, None] .... and so on

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

Не успокойтесь сейчас, думая, что это большое улучшение.

Да, но вы должны задать два вопроса:

  1. Насколько это великое улучшение?
  2. Можем ли мы улучшить?

Сейчас я отвечу на оба этих вопроса, начиная со второго вопроса. Ответ на это да!

Здесь мы можем сделать что-то лучшее и полностью избавиться от потребности None в очереди. Мотивация этого подхода происходит от самого предыдущего подхода.

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

Вот псевдокод для этого улучшенного алгоритма:

queue = Queue()queue.push(S)level = 0while queue is not empty {      size = queue.size()      // size represents the number of elements in the current level      for i in 1..size {          element = queue.pop()          // Process element here          // Perform a series of queue.push() operations here
      level += 1

И вот код для того же.

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

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

  • Мы отслеживаем максимальный размер очереди в любой момент с учетом суммы размеров отдельных элементов очереди.
  • Согласно документации Python, sys.getsizeof возвращает указатель объекта или размер ссылки в байтах. Таким образом, мы сэкономили почти 4,4 Кб места (20224 — 15800 bytes) путем переключения на None метод от исходного метода обхода порядка уровня Это только экономия памяти для этого случайного примера, и мы прошли лишь до 5-го уровня в обходе.
  • Окончательный метод дает только улучшение на 16 байт по сравнению с None метод. Это потому, что мы избавились только 4 None объекты, которые использовались для обозначения 4 уровней (кроме первого), которые мы обрабатывали. Размер каждого указателя (указатель на объект) составляет 4 байта в Python в 32-разрядной системе.

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

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

Кратчайший путь от заданного источника к месту назначения

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

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

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

ISBXi5XsxIfQ5AhgHeKmsEwBw12x8GtAsZRM

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

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

Однако здесь мы имеем дело со взвешенным графиком. Итак, первое открытие узла при обходе не гарантирует кратчайший путь для этого узла. К примеру, на схеме выше узел B будет обнаружено сначала, поскольку соседствует A и стоимость, связанная с этим путем (преимущество в данном случае), будет 25 . Но это не самый короткий путь. Кратчайший путь A --> M --> E —> Б оf длина 10.

Поиск в ширину не может узнать, даст ли нам конкретное открытие узла кратчайший путь к этому узлу. Таким образом, единственный возможный способ для BFS (или DFS) найти кратчайший путь во взвешенном графе – искать весь граф и продолжать записывать минимальное расстояние от источника до вершины назначения.

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

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

Что если бы я скажу вам, что BFS — это правильный алгоритм для поиска кратчайшего пути во взвешенном графике с небольшим ограничением ?

Ограничены кратчайшие пути

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

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

  • Это не должно быть слишком долгим полетом.
  • Это должно быть в пределах вашего бюджета (очень важно).
  • Он может иметь несколько остановок, но не больше K где K может отличаться от человека к человеку.
  • Наконец, у нас есть личные преимущества, которые включают в себя такие вещи, как доступ к лаунжу, качество пищи, места пересадки и среднее пространство для ног.

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

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

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

A3qPvKhi2p6Rfed4e28pAsR5wFDaB31-ai5V
Источник: Leetcode.com

Этот вопрос от LeetCode стал основной мотивацией для меня написать статью. Я настоятельно рекомендую рассмотреть вопрос один раз, а не полагаться только на снимок повыше.

Почему BFS будет работать здесь? можно спросить. «Это также взвешенный график, и здесь должна применяться та же причина сбоя BFS, о которой мы говорили в предыдущем разделе». НЕТ!

Количество уровней, на которые будет производиться поиск, ограничено значением K в вопросе или описании, представленном в начале раздела. Итак, по сути, мы пытались бы найти кратчайший путь, но нам не придется изучить весь график как таковой. Мы просто поднимемся на уровень K.

С реального жизненного сценария значение K было бы до 5 лет для любого умного путешественника?

Давайте посмотрим на псевдокод для алгоритма:

def bfs(source, destination, K):      min_cost = dictionary representing min cost under K stops for each node reachable from source. 
      set min_cost of source to be 0
      Q = queue()      Q.push(source)      stops = 0      while Q is not empty {
           size = Q.size           for i in range 1..size {                 element = Q.pop() 
                 if element == destination then continue
                 for neighbor in adjacency list of element {                        if stops == K and neighbor != destination        then continue  
                        if min_cost of neighbor improves, update and add back to the queue.                }           }               stops ++       }

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

По сути мы отслеживаем минимальное расстояние каждого узла от данного источника. Минимальное расстояние для источника сначала будет 0 и +inf для всех остальных.

Каждый раз, когда мы сталкиваемся с узлом, мы проверяем, можно ли улучшить текущую минимальную длину пути или нет. Если его можно улучшить, значит мы нашли альтернативный путь от источника к этой вершине с меньшей стоимостью — более дешевый маршрут полета к этой вершине. Мы снова ставим эту вершину в очередь, чтобы расположения и узлы, доступные из этой вершины, также обновлялись (могут или не быть).

Главное вот что:

# No need to update the minimum cost if we have already exhausted our K stops. if stops == K and neighbor != dst:    continue

Так что мы просто открыли узел, представленный element в коде и neighbor может быть либо пунктом назначения, либо случайным другим узлом. Если мы уже исчерпали свое K останавливается с element будучи Kth остановка, тогда мы не должны обрабатывать и обновлять (возможно) минимальное расстояние для neighbor. Это нарушило бы наш максимум K останавливает состояние в этом случае.

Как выяснилось, я решил эту проблему сначала с помощью динамического программирования, и для работы на платформе LeetCode понадобилось около 165 мс. Я работал с помощью BFS, и это было очень быстро, всего за 45 мс на выполнение. Мотивации достаточно, чтобы написать эту статью для вас.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *