Ο αλγόριθμος του Lee εξηγείται με παραδείγματα

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

Κατανόηση πώς λειτουργεί

Ο αλγόριθμος είναι ένας breadth-firstβασισμένος αλγόριθμος που χρησιμοποιεί queuesγια την αποθήκευση των βημάτων. Συνήθως χρησιμοποιεί τα ακόλουθα βήματα:

  1. Επιλέξτε ένα σημείο εκκίνησης και προσθέστε το στην ουρά.
  2. Προσθέστε τα έγκυρα γειτονικά κελιά στην ουρά.
  3. Αφαιρέστε τη θέση στην οποία βρίσκεστε από την ουρά και συνεχίστε στο επόμενο στοιχείο.
  4. Επαναλάβετε τα βήματα 2 και 3 έως ότου η ουρά είναι κενή.

Μια βασική ιδέα που πρέπει να καταλάβουμε είναι ότι οι breadth-firstαναζητήσεις διευρύνονται, ενώ οι depth-firstαναζητήσεις πηγαίνουν βαθιά.

Χρησιμοποιώντας το παράδειγμα ενός αλγορίθμου επίλυσης λαβυρίνθου, μια depth-firstπροσέγγιση θα δοκιμάσει κάθε πιθανό μονοπάτι ένα προς ένα έως ότου φτάσει είτε σε αδιέξοδο είτε στο τέλος και επιστρέψει το αποτέλεσμα. Ωστόσο, η διαδρομή που επιστρέφει μπορεί να μην είναι η πιο αποτελεσματική, αλλά απλώς η πρώτη ολοκληρωμένη διαδρομή μέχρι το τέλος που μπόρεσε να βρει ο αλγόριθμος.

breadth-firstΑντίθετα, μια αναζήτηση θα βγει σε κάθε ανοιχτό χώρο δίπλα στο σημείο εκκίνησης και, στη συνέχεια, θα αναζητήσει άλλους πιθανούς ανοιχτούς χώρους. Θα συνεχίσει να το κάνει αυτό, βγαίνοντας κάθε στρώμα και δοκιμάζοντας κάθε πιθανή διαδρομή παράλληλα, μέχρι να βρει το σημείο τερματισμού. Δεδομένου ότι δοκιμάζετε κάθε διαδρομή ταυτόχρονα, μπορείτε να είστε σίγουροι ότι η πρώτη ολοκληρωμένη διαδρομή από την αρχή έως το τέλος είναι επίσης η πιο σύντομη.

Εκτέλεση

Το C ++ έχει ήδη εφαρμόσει την ουρά στη βιβλιοθήκη, αλλά αν χρησιμοποιείτε κάτι άλλο, μπορείτε να εφαρμόσετε τη δική σας έκδοση της ουράς.

Κωδικός C ++:

int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily int dc[] = {0, 1, 0, -1}; queue X, Y; // the queues used to get the positions in the matrix X.push(start_x); //initialize the queues with the start position Y.push(start_y); void lee() { int x, y, xx, yy; while(!X.empty()) // while there are still positions in the queue { x = X.front(); // set the current position y = Y.front(); for(int i = 0; i < 4; i++) { xx = x + dl[i]; // travel in an adiacent cell from the current position yy = y + dc[i]; if('position is valid') //here you should insert whatever conditions should apply for your position (xx, yy) { X.push(xx); // add the position to the queue Y.push(yy); mat[xx][yy] = -1; // you usually mark that you have been to this position in the matrix } } X.pop(); // eliminate the first position, as you have no more use for it Y.pop(); } }