Εύρεση πιο σύντομων διαδρομών χρησιμοποιώντας την Πρώτη αναζήτηση Breadth

Γνωρίζετε το ποσό της παγκόσμιας εναέριας κυκλοφορίας το 2017; Γνωρίζετε ποια είναι η άνοδος της εναέριας κυκλοφορίας τα τελευταία χρόνια; Λοιπόν, ας δούμε μερικά στατιστικά στοιχεία.

Σύμφωνα με τον Διεθνή Οργανισμό Πολιτικής Αεροπορίας (ICAO), ένα ρεκόρ 4,1 δισεκατομμυρίων επιβατών μεταφέρθηκε από την αεροπορική βιομηχανία σε προγραμματισμένες υπηρεσίες το 2017. Και, ο αριθμός των πτήσεων αυξήθηκε σε 37 εκατομμύρια παγκοσμίως το 2017.

Αυτό είναι πολλοί επιβάτες και πολλές πτήσεις καταλαμβάνουν τον εναέριο χώρο σε καθημερινή βάση σε όλο τον κόσμο. Δεδομένου ότι υπάρχουν εκατοντάδες και χιλιάδες από αυτές τις πτήσεις σε όλο τον κόσμο, σίγουρα θα υπάρχουν διαφορετικές διαδρομές με πολλαπλές στάσεις μεταξύ από το ένα μέρος στο άλλο.

Κάθε πτήση έχει μια δική της πηγή και έναν προορισμό και μια τυπική οικονομική θέση θέσης που σχετίζεται με αυτήν. Ας αφήσουμε τα φανταχτερά εισιτήρια επιχειρηματικής θέσης και επιπλέον χώρο για τα πόδια και τι όχι!

Σε ένα τέτοιο σενάριο, είναι πολύ συγκεχυμένο να επιλέξουμε ποια θα ήταν η καλύτερη πτήση αν θέλουμε να πάμε από το ένα μέρος στο άλλο.

Ας δούμε τον αριθμό των επιλογών πτήσεων StudentUniverse (παρέχει εκπτώσεις για μαθητές;) μου δίνει από το Λος Άντζελες στο Νέο Δελχί.

Προσφέρονται 119 συνολικές πτήσεις. Στη συνέχεια, εμφανίζεται ένα αναδυόμενο παράθυρο στον ιστότοπο που λέει ότι υπάρχουν άλλοι ιστότοποι που ενδέχεται να προσφέρουν παρόμοιες πτήσεις σε ακόμη φθηνότερες τιμές. ;

Τόσες πολλές ιστοσελίδες και αμέτρητες πτήσεις για μία μόνο πηγή και προορισμό.

Ως προγραμματιστής, εάν θέλω να λύσω αυτό το πρόβλημα, θα έκανα ένα σύστημα για την αποτελεσματική αντιμετώπιση των ακόλουθων ερωτημάτων:

  • Συνολικός αριθμός προορισμών που είναι προσβάσιμοι (με μέγιστο αριθμό στάσεων) από την τρέχουσα τοποθεσία μου, καθώς και κατάλογος αυτών των προορισμών

    Κάποιος πρέπει να διατηρήσει τις επιλογές του ανοιχτές όταν θέλουν να ταξιδέψουν;

  • Είναι γνωστό το γεγονός (IMO;) ότι μια διαδρομή με πολλές στάσεις τείνει να είναι μια φθηνότερη εναλλακτική λύση για τις απευθείας πτήσεις.

    Έτσι, δεδομένης μιας πηγής και ενός προορισμού, ίσως θέλουμε να βρούμε διαδρομές με τουλάχιστον 2 ή 3 στάσεις.

  • Το πιο σημαντικό: Ποια είναι η φθηνότερη διαδρομή από μια δεδομένη πηγή προς έναν συγκεκριμένο προορισμό;
  • Και…. Θα έρθουμε σε αυτό στο τέλος;

Όπως μπορείτε να μαντέψετε, θα υπήρχαν δυνητικά χιλιάδες πτήσεις ως αποτέλεσμα των δύο πρώτων ερωτημάτων. Αλλά μπορούμε σίγουρα να το μειώσουμε παρέχοντας κάποια άλλα κριτήρια για να μειώσουμε το μέγεθος της παραγωγής. Για το πεδίο εφαρμογής αυτού του άρθρου, ας επικεντρωθούμε σε αυτά τα αρχικά ερωτήματα οι ίδιοι.

Μοντελοποίηση του Δικτύου Πτήσης ως Γράφημα

Είναι αρκετά σαφές από τον τίτλο αυτού του άρθρου ότι τα γραφήματα θα εμπλέκονταν κάπου, έτσι δεν είναι;

Η μοντελοποίηση αυτού του προβλήματος ως πρόβλημα διέλευσης γραφήματος το απλοποιεί πολύ και καθιστά το πρόβλημα πολύ πιο εύχρηστο. Έτσι, ως πρώτο βήμα, ας καθορίσουμε το γράφημα μας.

Διαμορφώνουμε την εναέρια κυκλοφορία ως:

  • σκηνοθεσία
  • πιθανώς κυκλικό
  • σταθμισμένο
  • δάσος. G (V, E)

Σκηνοθετείται επειδή κάθε πτήση θα έχει καθορισμένη πηγή και προορισμό. Αυτά έχουν πολύ νόημα.

Κυκλικό γιατί είναι πολύ πιθανό να ακολουθήσετε μια δέσμη πτήσεων που ξεκινούν από μια δεδομένη τοποθεσία και καταλήγουν στην ίδια τοποθεσία.

Σταθμισμένο επειδή κάθε πτήση έχει ένα κόστος που σχετίζεται με αυτό που θα ήταν το εισιτήριο πτήσης οικονομικής θέσης για αυτό το άρθρο.

Και τέλος, ένα δάσος επειδή μπορεί να έχουμε πολλά συνδεδεμένα στοιχεία. Δεν είναι απαραίτητο όλες οι πόλεις του κόσμου να έχουν κάποιο είδος δικτύου πτήσεων μεταξύ τους. Έτσι, το γράφημα μπορεί να αποσυνδεθεί, και ως εκ τούτου ένα δάσος.

Οι κορυφές, V , θα ήταν οι τοποθεσίες σε όλο τον κόσμο όπου υπάρχουν αεροδρόμια που λειτουργούν.

Τα άκρα, E , θα ήταν αντιπροσωπευτικά όλων των πτήσεων που αποτελούν την εναέρια κυκλοφορία. Ένα άκρο από u -->? v απλά σημαίνει ότι έχετε μια κατευθυνόμενη πτήση από τη θέση / δεν dε υ tov.

Τώρα που έχουμε μια ιδέα για το πώς να μοντελοποιήσουμε το δίκτυο πτήσεων ως γράφημα, ας προχωρήσουμε και να λύσουμε το πρώτο κοινό ερώτημα που μπορεί να έχει ένας χρήστης.

Συνολικός αριθμός προορισμών

Ποιος δεν του αρέσει να ταξιδεύει;

Ως κάποιος που του αρέσει να εξερευνά διαφορετικά μέρη, θα θέλατε να γνωρίζετε ποιοι είναι όλοι οι προορισμοί που είναι προσβάσιμοι από το τοπικό σας αεροδρόμιο. Και πάλι, θα υπήρχαν πρόσθετα κριτήρια εδώ για τη μείωση των αποτελεσμάτων αυτού του ερωτήματος. Αλλά για να διατηρήσουμε τα πράγματα απλά, θα προσπαθήσουμε απλώς να βρούμε όλες τις τοποθεσίες που είναι προσβάσιμες από το τοπικό μας αεροδρόμιο.

Τώρα που έχουμε ένα καλά καθορισμένο γράφημα, μπορούμε να εφαρμόσουμε εγκάρσιους αλγόριθμους για να το επεξεργαστούμε.

Ξεκινώντας από ένα δεδομένο σημείο, μπορούμε να χρησιμοποιήσουμε είτε Breadth First Search (BFS) είτε Depth First Search (DFS) για να εξερευνήσουμε το γράφημα ή τις τοποθεσίες που είναι προσβάσιμες από την αρχική θέση μέσα σε ένα μέγιστο αριθμό στάσεων. Δεδομένου ότι αυτό το άρθρο αφορά τον πρώτο αλγόριθμο αναζήτησης, ας δούμε πώς μπορούμε να χρησιμοποιήσουμε το περίφημο BFS για να ολοκληρώσουμε αυτήν την εργασία.

Θα ξεκινήσουμε την ουρά BFS με τη δεδομένη θέση ως σημείο εκκίνησης. Στη συνέχεια εκτελούμε το πρώτο πλάτος διασταύρωσης και συνεχίζουμε έως ότου η ουρά είναι κενή ή έως ότου εξαντληθεί ο μέγιστος αριθμός στάσεων.

Σημείωση: Εάν δεν είστε εξοικειωμένοι με την πρώτη αναζήτηση εύρους ή την πρώτη αναζήτηση βάθους, θα συνιστούσα να διαβάσετε αυτό το άρθρο πριν συνεχίσετε.

Ας δούμε τον κώδικα για να αρχίσουμε τη δομή δεδομένων γραφημάτων. Πρέπει επίσης να δούμε πώς θα καταλήξει ο αλγόριθμος BFS, δίνοντάς μας όλους τους προορισμούς που είναι προσβάσιμοι από μια δεδομένη πηγή.

Τώρα που έχουμε μια καλή ιδέα για το πώς θα αρχικοποιηθεί το γράφημα, ας δούμε τον κώδικα για τον αλγόριθμο BFS.

Η παράσταση bfsστην πόλη του Λος Άντζελες θα μας έδινε τους ακόλουθους προορισμούς που είναι προσβάσιμοι:

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

Αυτό ήταν απλό, έτσι δεν είναι;

We will look at how we can limit the BFS to a maximum number of stops later on in the article.

In case we have a humongous flight network, which we would have in a production scenario, then we would not ideally want to explore all the reachable destinations from a given starting point.

This is a use case if the flight network is very small or pertains only to a few regions in the United States.

But, for a large network, a more realistic use case would be to find all the flight routes with multiple stops. Let us look at this problem in some more detail and see how we can solve it.

Routes with multiple stops

It is a well known fact that more often than not, for a given source and destination, a multi stop trip is cheaper than a direct, non-stop flight.

A lot of times we prefer the direct flight to avoid the layovers. Also because the multi-stop flights do tend to take a lot of time — which we don’t have.

However, if you don’t have any deadlines approaching and you want to save some bucks (and are comfortable with the multi-stop route that a lot of airlines suggest), then you might actually benefit a lot from something like this.

Also, you might get to pass through some of the most beautiful locations in the world with some of the most advanced airports which you can enjoy. So, that’s enough motivation as it is.

In terms of the graph model that we have been talking about, given a source and a destination, we need to come up with routes with 2 or more stops for a given source and destination.

As an end user, we might not want to see flights in this order for this query:

[A, C, D, B], 2 stops, $X[A, E, D, C, F, W, G, T, B], 8 stops, $M[A, R, E, G, B], 3 stops, $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] and we keep popping elements. Every time we encounter a None element, we know that a level has ended and a new one has started. We push another None to mark the end of this new level.

Consider a very simple graph here, and then we will dry run this through the graph.

**************************************************** 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

I hope this sums up the algorithm pretty well. This certainly is a neat trick to do level order traversal, keep track of the levels, and not encounter too much of a memory concern. This certainly reduces the memory footprint of the code.

Don’t get complacent now thinking this is a great improvement.

It is, but you should be asking two questions:

  1. How big of an improvement is this?
  2. Can we do better?

I will answer both of these questions now starting with the second question. The answer to that is Yes!

We can do one better here and completely do away with the need for the None in the queue. The motivation for this approach comes from the previous approach itself.

If you look closely at the dry run above, you can see that every time we pop a None, one level is finished and the other one is ready for processing. The important thing is that an entire next level exists in the queue at the time of popping of a None . We can make use of this idea of considering the queue size into the traversal logic.

Here is the pseudo code for this improved algorithm:

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

And here is the code for the same.

The pseudo code is self explanatory. We essentially do away with the need for an extra None element per level and instead make use of the queue’s size to change levels. This would also lead to improvement over the last method, but how much?

Have a look at the following Jupyter Notebook to see the memory difference between the three methods.

  • We track the maximum size of the queue at any time by considering the sum of sizes of individual queue elements.
  • According to Python’s documentation, sys.getsizeof returns the object’s pointer or reference’s size in bytes. So, we saved almost 4.4Kb space (20224 — 15800 bytes) by switching to the None method from the original level order traversal method. This is just the memory savings for this random example, and we went only until the 5th level in the traversal.
  • The final method only gives an improvement of 16 bytes over the None method. This is because we got rid of just 4 None objects which were being used to mark the 4 levels (apart from the first one) that we processed. Each pointer’s size (pointer to an object) is 4 bytes in Python on a 32 bit system.

Now that we have all these interesting multi-path routes from our source to our destination and highly efficient level order traversal algorithms to solve it, we can look at a more lucrative problem to solve using our very own BFS.

What’s the cheapest flight route from my source to a given destination? This is something everybody would be instantly interested in. I mean who doesn’t want to save some bucks?

Shortest Path from a given source to destination

There’s not much description to give for the problem statement. We just need to find the shortest path and make the end user happy.

Algorithmically, given a weighted directed graph, we need to find the shortest path from source to destination. Shortest or cheapest would be one and the same thing from the point of the view of the algorithm.

We will not go into describing a possible BFS solution to this problem because such a solution would be intractable. Let us look at the graph below to understand why that is the case.

We say that BFS is the algorithm to use if we want to find the shortest path in an undirected, unweighted graph. The claim for BFS is that the first time a node is discovered during the traversal, that distance from the source would give us the shortest path.

The same cannot be said for a weighted graph. Consider the graph above. If say we were to find the shortest path from the node A to B in the undirected version of the graph, then the shortest path would be the direct link between A and B. So, the shortest path would be of length 1 and BFS would correctly find this for us.

However, we are dealing with a weighted graph here. So, the first discovery of a node during traversal does not guarantee the shortest path for that node. For example, in the diagram above, the node B would be discovered initially because it is the neighbor of A and the cost associated with this path (an edge in this case) would be 25 . But, this is not the shortest path. The shortest path is A --> M --> E --> B of length 10.

Breadth first search has no way of knowing if a particular discovery of a node would give us the shortest path to that node. And so, the only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from source to the destination vertex.

This solution is not feasible for a huge network like our flight network that would have potentially thousands of nodes.

We won’t go into the details of how we can solve this. That is out of scope for this article.

What if I told you that BFS is just the right algorithm to find the shortest path in a weighted graph with a slight constraint ?

Constrained Shortest Paths

Since the graph we would have for the flight network is humongous, we know that exploring it completely is not really a possibility.

Consider the problem of shortest paths from the customer’s perspective. When you want to book a flight, these are the following options you ideally consider:

  • It shouldn’t be too long a flight.
  • It should be under your budget (Very Important).
  • It may have multiple stops but not more than K where K can vary from person to person.
  • Finally we have personal preferences which involve things like lounge access, food quality, layover locations, and average leg room.

The important point to consider here is the third one above: it may have multiple stops, but not more than K where K can vary from person to person.

A customer wants the cheapest flight route, but they also don’t want say 20 stops in between their source and destination. A customer might be okay with a maximum of 3 stops, or in extreme cases maybe even 4 — but not more than that.

We would want an application that would find out the cheapest flight route with at most K stops for a given source and destination.

This question from LeetCode has been the primary motivation for me to write this article. I strongly recommend going through the question once and not only relying on the snapshot above.

“Why would BFS work here?” one might ask. “This is also a weighted graph and the same reason for the failure of BFS that we discussed in the previous section should apply here.” NO!

The number of levels that the search would go to is limited by the value K in the question or in the description provided at the start of section. So, essentially, we would be trying to find the shortest path, but we won’t have to explore the entire graph as such. We will just go up to the level K.

From a real life scenario, the value of K would be under 5 for any sane traveler ?.

Let us look at the pseudo-code for the algorithm:

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 ++ }

This again is level order traversal and the approach being used here is the one that makes use of the queue’s size at every level. Let us look at a commented version of the code to solve this problem.

Essentially, we keep track of the minimum distance of every node from the given source. The minimum distance for the source would be 0 and +inf for all others initially.

Whenever we encounter a node, we check if the current minimum path length can be improved or not. If it can be improved, that means that we have found an alternate path from source to this vertex with cheaper cost — a cheaper flight route until this vertex. We queue this vertex again so that locations and nodes reachable from this vertex on are updated (may or may not be) as well.

The key thing is this:

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

So we just popped the a node represented by element in the code and neighbor can either be a destination or a random other node. If we have already exhausted our K stops with the element being the Kth stop, then we shouldn’t process and update (possibly) the minimum distance for neighbor. This would violate our maximum K stops condition in that case.

As it turns out, I solved this problem originally using Dynamic Programming and it took around 165ms to run on the LeetCode platform. I ran using BFS and it was blazing fast with just 45ms to execute. Motivation enough to write this article for you guys.

Ελπίζω να μπορέσατε να αντλήσετε κάποιο όφελος από αυτό το άρθρο σχετικά με το Breadth First Search και ορισμένες από τις εφαρμογές του. Η κύρια εστίαση ήταν να δείξει την εφαρμογή της σε συντομότερες διαδρομές σε ένα σταθμισμένο γράφημα υπό ορισμένους περιορισμούς;