Οι μέθοδοι Traversal Graph με εντυπωσίαζαν πάντα. Από την αποτελεσματική επικοινωνία peer έως peer έως την εύρεση των πλησιέστερων εστιατορίων και καφέ που χρησιμοποιούν GPS, οι μέθοδοι διέλευσης έχουν ένα ποικίλο σύνολο εφαρμογών στο πραγματικό σενάριο. Σε αυτό το ιστολόγιο για τον αλγόριθμο Breadth-First Search, θα συζητήσουμε τη λογική των μεθόδων διέλευσης γραφημάτων και θα χρησιμοποιήσουμε παραδείγματα για να κατανοήσουμε τη λειτουργία του αλγορίθμου Breadth-First Search.
Για να αποκτήσετε σε βάθος γνώση της Τεχνητής Νοημοσύνης και της Μηχανικής Μάθησης, μπορείτε να εγγραφείτε ζωντανά από την Edureka με 24ωρη υποστήριξη και πρόσβαση σε όλη τη διάρκεια ζωής.
Ακολουθεί μια λίστα θεμάτων που θα είναι καλύπτεται σε αυτό το ιστολόγιο:
- Εισαγωγή στο γράφημα διέλευσης
- Τι είναι το Breadth-First Search;
- Κατανόηση του αλγορίθμου Breadth-First Search με ένα παράδειγμα
- Breadth-First Search Αλγόριθμος Ψευδοκώδικας
- Εφαρμογές της Πρώτης Αναζήτησης
Εισαγωγή στο γράφημα διέλευσης
Η διαδικασία της επίσκεψης και της εξερεύνησης ενός γραφήματος για επεξεργασία ονομάζεται διάγραμμα διέλευσης. Για να είμαστε πιο συγκεκριμένοι, έχει να κάνει με την επίσκεψη και την εξερεύνηση κάθε κορυφής και άκρης σε ένα γράφημα έτσι ώστε όλες οι κορυφές να εξερευνηθούν ακριβώς μία φορά.
Ακούγεται απλό! Αλλά υπάρχει μια παγίδα.
Υπάρχουν αρκετές τεχνικές διασταύρωσης γραφημάτων όπως Breadth-First Search, Depth First Search και ούτω καθεξής. Η πρόκληση είναι να χρησιμοποιήσετε ένα γράφημα διασταυρούμενη τεχνική που είναι πιο κατάλληλη για την επίλυση ενός συγκεκριμένου προβλήματος. Αυτό μας φέρνει στην τεχνική Breadth-First Search.
Τι είναι ο αλγόριθμος αναζήτησης πρώτου εύρους;
Ο αλγόριθμος Breadth-First Search είναι μια τεχνική διέλευσης γραφήματος, όπου επιλέγετε έναν τυχαίο αρχικό κόμβο (πηγή ή ριζικό κόμβο) και αρχίζετε να διασχίζετε το γράφημα στο επίπεδο με τέτοιο τρόπο ώστε όλοι οι κόμβοι και οι αντίστοιχοι θυγατρικοί κόμβοι να επισκέπτονται και να εξερευνούνται.
Πριν προχωρήσουμε περαιτέρω και κατανοήσουμε το Breadth-First Search με ένα παράδειγμα, ας εξοικειωθούμε με δύο σημαντικούς όρους που σχετίζονται με τη διάγραμμα γραφήματος:
- Επίσκεψη σε έναν κόμβο: Όπως υποδηλώνει το όνομα, η επίσκεψη σε έναν κόμβο σημαίνει την επίσκεψη ή την επιλογή ενός κόμβου.
- Εξερεύνηση ενός κόμβου: Εξερεύνηση του γειτονικοί κόμβοι (θυγατρικοί κόμβοι) ενός επιλεγμένου κόμβου.
Ανατρέξτε στο παραπάνω σχήμα για να το κατανοήσετε καλύτερα.
Κατανόηση του αλγόριθμου αναζήτησης Πρώτου εύρους με ένα παράδειγμα
Ο αλγόριθμος Breadth-First Search ακολουθεί μια απλή προσέγγιση με βάση το επίπεδο για την επίλυση ενός προβλήματος. Εξετάστε το παρακάτω δυαδικό δέντρο (το οποίο είναι ένα γράφημα). Στόχος μας είναι να διασχίσουμε το γράφημα χρησιμοποιώντας τον αλγόριθμο Breadth-First Search.
Πριν ξεκινήσουμε, πρέπει να είστε εξοικειωμένοι με την κύρια δομή δεδομένων που εμπλέκεται στον αλγόριθμο Breadth-First Search.
τι κάνει .innerhtml
Η ουρά είναι μια αφηρημένη δομή δεδομένων που ακολουθεί τη μεθοδολογία First-In-First-Out (τα δεδομένα που εισάγονται πρώτα θα έχουν πρόσβαση πρώτα). Είναι ανοιχτό και στα δύο άκρα, όπου το ένα άκρο χρησιμοποιείται πάντα για την εισαγωγή δεδομένων (enqueue) και το άλλο χρησιμοποιείται για την αφαίρεση δεδομένων (dequeue).
Τώρα ας ρίξουμε μια ματιά στα βήματα που συνεπάγεται η διασταύρωση ενός γραφήματος χρησιμοποιώντας το Breadth-First Search:
Βήμα 1: Πάρτε μια κενή ουρά.
Βήμα 2: Επιλέξτε έναν αρχικό κόμβο (επισκέπτεστε έναν κόμβο) και εισαγάγετέ τον στην ουρά.
Βήμα 3: Υπό την προϋπόθεση ότι η ουρά δεν είναι κενή, εξαγάγετε τον κόμβο από την ουρά και εισαγάγετε τους θυγατρικούς κόμβους (εξερεύνηση ενός κόμβου) στην ουρά.
Βήμα 4: Εκτυπώστε τον εξαγόμενο κόμβο.
Μην ανησυχείτε αν είστε μπερδεμένοι, θα το καταλάβουμε με ένα παράδειγμα.
Ρίξτε μια ματιά στο παρακάτω γράφημα, θα χρησιμοποιήσουμε τον αλγόριθμο Breadth-First Search για να διασχίσουμε το γράφημα.
Στην περίπτωσή μας, θα ορίσουμε τον κόμβο «a» ως τον ριζικό κόμβο και θα αρχίσουμε να διασχίζουμε προς τα κάτω και να ακολουθούμε τα βήματα που αναφέρονται παραπάνω.
java τι είναι ένα διάνυσμα
Η παραπάνω εικόνα απεικονίζει τη διαδικασία από άκρο σε άκρο του αλγόριθμου Breadth-First Search. Επιτρέψτε μου να το εξηγήσω σε βάθος.
- Αντιστοιχίστε το 'a' ως τον ριζικό κόμβο και εισαγάγετέ το στην ουρά.
- Εξαγάγετε τον κόμβο «a» από την ουρά και εισαγάγετε τους θυγατρικούς κόμβους «a», δηλαδή «b» και «c».
- Εκτύπωση κόμβου «a».
- Η ουρά δεν είναι κενή και έχει τον κόμβο «b» και «c». Επειδή το 'b' είναι ο πρώτος κόμβος στην ουρά, ας το εξαγάγουμε και εισάγουμε τους θυγατρικούς κόμβους 'b', δηλαδή τον κόμβο 'd' και 'e'.
- Επαναλάβετε αυτά τα βήματα έως ότου η ουρά αδειάσει. Σημειώστε ότι οι κόμβοι που έχουν ήδη επισκεφτεί δεν πρέπει να προστεθούν στην ουρά πάλι.
Ας δούμε τώρα τον ψευδοκώδικα του αλγορίθμου Breadth-First Search.
Breadth-First Search Αλγόριθμος Ψευδοκώδικας
Ακολουθεί ο ψευδοκώδικας για την εφαρμογή του αλγόριθμου Breadth-First Search:
Είσοδος: s ως κόμβος προέλευσης BFS (G, s) αφήνει το Q να βρίσκεται στην ουρά. Q.enqueue (s) επισημαίνεται ως επισκέφθηκε ενώ (το Q δεν είναι κενό) v = Q.dequeue () για όλους τους γείτονες w του v στο γράφημα G εάν δεν γίνει επίσκεψη
Στον παραπάνω κώδικα, εκτελούνται τα ακόλουθα βήματα:
- (G, s) εισάγεται, εδώ G είναι το γράφημα και s είναι ο ριζικός κόμβος
- Δημιουργείται μια ουρά 'Q' και αρχικοποιείται με τον κόμβο προέλευσης 's'
- Σημειώνονται όλοι οι θυγατρικοί κόμβοι του «s»
- Εξαγάγετε «s» από την ουρά και επισκεφθείτε τους θυγατρικούς κόμβους
- Επεξεργαστείτε όλους τους θυγατρικούς κόμβους του v
- Καταστήματα w (θυγατρικοί κόμβοι) στο Q για να επισκεφθείτε περαιτέρω τους θυγατρικούς κόμβους του
- Συνεχίστε έως ότου είναι το 'Q' αδειάζω
Πριν ολοκληρώσουμε το ιστολόγιο, ας δούμε μερικές εφαρμογές του αλγορίθμου Breadth-First Search.
Εφαρμογές αλγόριθμου αναζήτησης πρώτου εύρους
Το Breadth-first Search είναι μια απλή μέθοδος διασταύρωσης γραφημάτων που έχει ένα εκπληκτικό εύρος εφαρμογών. Ακολουθούν μερικοί ενδιαφέροντες τρόποι με τους οποίους χρησιμοποιείται η Πρώτη αναζήτηση Bread:
Ανιχνευτές στις μηχανές αναζήτησης: Το Breadth-First Search είναι ένας από τους κύριους αλγόριθμους που χρησιμοποιούνται για την ευρετηρίαση ιστοσελίδων. Ο αλγόριθμος ξεκινά να διασχίζει από τη σελίδα προέλευσης και ακολουθεί όλους τους συνδέσμους που σχετίζονται με τη σελίδα. Εδώ κάθε ιστοσελίδα θα θεωρείται κόμβος σε ένα γράφημα.
how to run atom python
Συστήματα πλοήγησης GPS: Το Breadth-First Search είναι ένας από τους καλύτερους αλγόριθμους που χρησιμοποιούνται για την εύρεση γειτονικών τοποθεσιών χρησιμοποιώντας το σύστημα GPS.
Βρείτε τη συντομότερη διαδρομή και το ελάχιστο δέντρο έκτασης για ένα μη σταθμισμένο γράφημα: Όταν πρόκειται για ένα μη σταθμισμένο γράφημα, ο υπολογισμός της συντομότερης διαδρομής είναι αρκετά απλός, καθώς η ιδέα πίσω από τη συντομότερη διαδρομή είναι να επιλέξετε μια διαδρομή με τον μικρότερο αριθμό άκρων. Το Breadth-First Search μπορεί να το επιτρέψει διασχίζοντας έναν ελάχιστο αριθμό κόμβων ξεκινώντας από τον κόμβο προέλευσης. Ομοίως, για ένα δέντρο που εκτείνεται, μπορούμε να χρησιμοποιήσουμε μία από τις δύο μεθόδους, Breadth-First Search ή Depth-first traversal για να βρούμε ένα δέντρο που εκτείνεται.
Ραδιοφωνικός: Η δικτύωση χρησιμοποιεί αυτό που αποκαλούμε πακέτα επικοινωνίας. Αυτά τα πακέτα ακολουθούν μια διασταυρούμενη μέθοδο για να φτάσουν σε διάφορους κόμβους δικτύωσης. Μία από τις πιο συχνά χρησιμοποιούμενες διασταυρούμενες μεθόδους είναι το Breadth-First Search. Χρησιμοποιείται ως αλγόριθμος που χρησιμοποιείται για την επικοινωνία μεταδιδόμενων πακέτων σε όλους τους κόμβους ενός δικτύου.
Δικτύωση Peer to Peer: Το Breadth-First Search μπορεί να χρησιμοποιηθεί ως διασταυρούμενη μέθοδος για την εύρεση όλων των γειτονικών κόμβων σε δίκτυο Peer to Peer. Για παράδειγμα, το BitTorrent χρησιμοποιεί Breadth-First Search για επικοινωνία peer to peer.
Αυτό λοιπόν αφορούσε τη λειτουργία του αλγορίθμου Breadth-First Search. Τώρα που γνωρίζετε πώς να διασχίζετε γραφήματα, είμαι βέβαιος ότι θέλετε να μάθετε περισσότερα. Ακολουθούν μερικά σχετικά ιστολόγια που σας ενδιαφέρουν:
Με αυτό, φτάνουμε στο τέλος αυτού του ιστολογίου. Αν έχετε απορίες σχετικά με αυτό το θέμα, αφήστε ένα σχόλιο παρακάτω και θα επικοινωνήσουμε μαζί σας.
Εάν επιθυμείτε να εγγραφείτε για ένα πλήρες μάθημα Τεχνητής Νοημοσύνης και Μηχανικής Μάθησης, η Edureka διαθέτει μια ειδικά επιμελημένη που θα σας κάνει ικανό σε τεχνικές όπως η εποπτευόμενη μάθηση, η μη εποπτευόμενη εκμάθηση και η επεξεργασία φυσικής γλώσσας. Περιλαμβάνει εκπαίδευση σχετικά με τις τελευταίες εξελίξεις και τεχνικές προσεγγίσεις στην Τεχνητή Νοημοσύνη & Μηχανική Μάθηση όπως η Βαθιά Μάθηση, τα Γραφικά Μοντέλα και η Ενίσχυση Μάθησης.