Ο αλγόριθμος Lee εξήγησε: Λαβύρινθος τρέξιμο και εύρεση της πιο σύντομης διαδρομής

Τι είναι ο αλγόριθμος Lee;

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

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

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

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

Εκτέλεση

Το 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(); } }