Lees Algorithmus anhand von Beispielen erklärt

Der Lee-Algorithmus ist eine mögliche Lösung für Labyrinth-Routing-Probleme. Es gibt immer eine optimale Lösung, wenn es eine gibt, ist aber langsam und benötigt viel Speicher für ein dichtes Layout.

Verstehen, wie es funktioniert

Der Algorithmus ist ein breadth-firstbasierter Algorithmus, der queueszum Speichern der Schritte verwendet wird. In der Regel werden die folgenden Schritte ausgeführt:

  1. Wählen Sie einen Startpunkt und fügen Sie ihn der Warteschlange hinzu.
  2. Fügen Sie der Warteschlange die gültigen Nachbarzellen hinzu.
  3. Entfernen Sie die Position, an der Sie sich befinden, aus der Warteschlange und fahren Sie mit dem nächsten Element fort.
  4. Wiederholen Sie die Schritte 2 und 3, bis die Warteschlange leer ist.

Ein Schlüsselkonzept, das zu verstehen ist, ist, dass die breadth-firstSuche weit geht, während die depth-firstSuche tief geht.

Am Beispiel eines Labyrinthlösungsalgorithmus versucht ein depth-firstAnsatz jeden möglichen Pfad einzeln, bis er entweder eine Sackgasse oder das Ende erreicht und das Ergebnis zurückgibt. Der zurückgegebene Pfad ist jedoch möglicherweise nicht der effizienteste, sondern lediglich der erste vollständige Pfad zum Ziel, den der Algorithmus finden konnte.

Eine breadth-firstSuche wird stattdessen zu jedem offenen Raum neben dem Startpunkt durchgeführt und dann nach anderen möglichen offenen Räumen gesucht. Es wird dies weiterhin tun, Schicht für Schicht ausgehen und jeden möglichen Pfad im Tandem ausprobieren, bis es den Endpunkt findet. Da Sie jeden Pfad gleichzeitig ausprobieren, können Sie sicher sein, dass der erste vollständige Pfad von Anfang bis Ende auch der kürzeste ist.

Implementierung

In C ++ ist die Warteschlange bereits in der Bibliothek implementiert. Wenn Sie jedoch etwas anderes verwenden, können Sie gerne Ihre eigene Version der Warteschlange implementieren.

C ++ - Code:

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