Manchmal stehen wir vor der Aufgabe, den minimalen Weg von Punkt A nach Punkt B zu finden . "Bewegungskarte" kann Hindernisse haben und wie ein Labyrinth sein. Ähnliche Aufgaben treten bei der Spieleentwicklung, dem Leiterplattendesign und der Entwicklung von GPS-Navigatoren usw. auf.
Es gibt viele Algorithmen zum Finden des minimalen Pfads. Am einfachsten und effektivsten ist jedoch Wave Trace Algorithm (Lee's Algorithm) , der auf Breitensuchmethoden basiert.
Die Funktionsweise dieses Algorithmus ist nicht schwer zu verstehen. Es wird selbst einem Programmieranfänger klar sein.
Ich werde ein Beispiel meiner Arbeit geben. Ich habe eine Art zellulären Automaten (einen Graphen, der aus Knoten und Kanten zwischen ihnen besteht). Wir werden den Lee-Algorithmus darauf implementieren.
Die Implementierung des Algorithmus besteht aus 3 Stufen:
- Initialisierung von Anfangsdaten;
- Wellenausbreitung;
- Pfadwiederherstellung.
Erste Stufe - Initialisierung der Anfangsdaten
Sie benötigen ein Array von Objekten (Knoten, Zellen). Ich habe diese Klasse Node .
Jedes Objekt, außer anderen, hat ein near -Feld vom Typ zB ArrayList. In dieses Feld tragen Sie alle "Nachbarn" ( Nachbarn dieses Knotens ) ein.
Jeder Knoten ist mit „passierbar/unpassierbar“ gekennzeichnet.
Die Start- und Zielknoten werden aufgezeichnet.
Zweite Stufe - Wellenausbreitung
Sie müssen ein numerisches Array (nach Anzahl der Zellen) haben, in das die Zahlen (Markierungen) für jede Zelle geschrieben werden. Standardmäßig sind alle Zellenwerte Null.
Startknoten
wird auf 1 gesetzt.
Sie prüfen alle "benachbarten" Knoten dieses Knotens auf "Passierbarkeit" und prüfen, ob auf ihnen bereits Markierungen vorhanden sind. Da sollte die Marke nur einmal gesetzt werden.
Wenn alles zufriedenstellend ist, setzen Sie markiere 1 mehr als den vorherigen Knoten. Als nächstes überprüfen Sie die "Nachbarknoten".
Also bis du die Zielzelle erreichst.
Beispielcode:
public int[] WavePropagation(int fromNode, int toNode, ElementManager elementManager) { // распространение волны
int[] markedNode = new int[elementManager.GetNumberOfAllNodes()]; // массив, где будут хранится "отметки" каждого узла
int markNumber = 1; // счетчик
markedNode[fromNode] = markNumber; // инициализация стартового узла
while (markedNode[toNode] == 0) { // пока не достигли финишного узла
for (int i = 0; i < markedNode.length; i++) {
if (markedNode[i] == markNumber) { // начинаем со стартового узла
for (int j = 0; j < elementManager.GetNode(i).near.size(); j++) { // просматриваем все соседние узлы
if(markedNode[elementManager.GetNode(i).near.get(j).number] == 0 // если он еще не получил "отметку"
&& elementManager.GetNode(i).near.get(j).isEnable){ // если доступен
markedNode[elementManager.GetNode(i).near.get(j).number] = (markNumber + 1);
}
}
}
}
markNumber++;
}
return markedNode;
}
Dritte Phase - Wiederherstellung des Pfades
Geben Sie den Endknoten in das Pfadarray ein.
Betrachten Sie die Markierungen aller Knoten "angrenzend" an den Endknoten. Geben Sie in das Pfadarray den Knoten ein, dessen Höhe 1 kleiner ist als die des Zielknotens.
Wiederholen Sie diese Aktion, bis der Startknoten erreicht ist.
Beispielcode:
public ArrayList<Integer> PathRecovery(int fromNode, int toNode, int[] markedNode, ElementManager elementManager) { // восстановление пути
ArrayList<Integer> paramsPaveTheRoute = new ArrayList<>(); // массив, где хранится путь
if (markedNode[elementManager.GetNode(toNode).number] != 0) { // еще раз проверяем дошел ли алгоритм до финишного узла
paramsPaveTheRoute.add(toNode); // добавляем финишный узел к пути
ElementManager.Node currentNode = elementManager.GetNode(toNode);
while (currentNode.number != fromNode) { // пока не дошли до стартового узла
for (int i = 0; i < currentNode.near.size(); i++) { // проверяем соседние узлы
if (markedNode[elementManager.GetNode(currentNode.near.get(i).number).number]
== markedNode[currentNode.number] - 1) { // если значение пометки узла на 1 меньше, чем у предыдущего узла
currentNode = elementManager.GetNode(currentNode.near.get(i).number); //узел становится текущим
paramsPaveTheRoute.add(currentNode.number); // заносится в массив
}
}
}
}
return paramsPaveTheRoute;
}
Das Ergebnis des Programms:
Ich denke, Sie haben also gesehen, dass Wave Trace Algorithm (Lee's Algorithm) überhaupt nicht schwer zu implementieren ist. Es führt eine minimale Pfadsuche mit einem geringen Rechenaufwand durch. Falls gewünscht, kann dieser universelle Algorithmus kompliziert sein.
