Der Pfadfindungsalgorithmus ist einer der am häufigsten verwendeten Algorithmen im Bereich Computergrafik und künstliche Intelligenz, mit dem der kürzeste Weg oder optimale Weg von einem Punkt zum anderen berechnet wird. In diesem Artikel werde ich zwei häufig verwendete Pfadfindungsalgorithmen im Detail vorstellen: den Dijkstra-Algorithmus und den A*-Algorithmus Suchalgorithmus. Es funktioniert wie folgt:
Wir müssen eine Menge Q erstellen, um die Eckpunkte zu speichern, die noch nicht den kürzesten Weg gefunden haben
In der Initialisierung Wenn Sie das Distanzarray dist verwenden, müssen Sie den Abstand vom Startpunkt zu anderen Punkten auf unendlich und den Abstand vom Startpunkt zu sich selbst auf 0 einstellen.
Wiederholen Sie die folgenden Schritte, bis der Wert eingestellt ist Q ist leer:
in Finden Sie den Scheitelpunkt u, der dem Startpunkt in der Menge Q am nächsten liegt, und fügen Sie ihn der Menge S hinzu.
Aktualisieren Sie für jeden Nachbarscheitelpunkt v des Scheitelpunkts u den Abstand dist[v] vom Startpunkt auf v. Wenn dist[v] > dist[u] + Kante(u, v), aktualisieren Sie dist[v] ist dist[u] + Kante(u, v).
class DijkstraAlgorithm
{
private int[,] graph;
private int size;
public DijkstraAlgorithm(int[,] graph)
{
this.graph = graph;
this.size = graph.GetLength(0);
}
public int[] FindShortestPath(int start, int end)
{
int[] dist = new int[size];
bool[] visited = new bool[size];
for (int i = 0; i <p><span>A-Algorithmus</span></p><p style="text-align: justify;"><span>A Der Algorithmus ist ein heuristischer Suchalgorithmus, der verwendet wird, um den kürzesten Weg zwischen zwei Punkten in einem Diagramm zu finden. Die Idee des Algorithmus ist wie folgt: </span></p><h4><span>Erstellen Sie eine Prioritätswarteschlange openSet, um die zu erkundenden Scheitelpunkte zu speichern</span></h4><p><span>Wir müssen ein Array mit dem Namen gScore erstellen, um die tatsächlichen Kosten vom Startpunkt bis zu jedem zu speichern vertex</span></p><p> <span>Wir müssen ein Array mit dem Namen fScore erstellen, um die geschätzten Kosten vom Startpunkt bis zum Zielpunkt zu speichern</span></p><p><span>Fügen Sie den Startpunkt zu openSet hinzu, setzen Sie gScore[start] auf 0 und setzen Sie fScore[start ] auf 0 Geschätzte Kosten vom Startpunkt zum Zielpunkt </span></p><p><span> Wiederholen Sie die folgenden Schritte, bis openSet leer ist: </span></p><p><span></span>Finden Sie den Scheitelpunktstrom mit dem kleinsten fScore in openSet. </p><p><span></span> Wenn der Strom gleich dem Zielpunkt ist, bedeutet dies, dass der kürzeste Weg gefunden wurde und der Weg zurückgegeben wird. </p>import java.util.*;class AStarAlgorithm {private int[][] graph;private int size;public AStarAlgorithm(int[][] graph) {this.graph = graph;this.size = graph.length;}public List<integer> findShortestPath(int start, int end) {PriorityQueue<node> openSet = new PriorityQueue();int[] gScore = new int[size];int[] fScore = new int[size];int[] cameFrom = new int[size];boolean[] visited = new boolean[size];Arrays.fill(gScore, Integer.MAX_VALUE);Arrays.fill(fScore, Integer.MAX_VALUE);Arrays.fill(cameFrom, -1);gScore[start] = 0;fScore[start] = heuristicCostEstimate(start, end);openSet.offer(new Node(start, fScore[start]));while (!openSet.isEmpty()) {int current = openSet.poll().index;if (current == end) {return reconstructPath(cameFrom, current);}visited[current] = true;for (int neighbor = 0; neighbor reconstructPath(int[] cameFrom, int current) {List<integer> path = new ArrayList();path.add(current);while (cameFrom[current] != -1) {current = cameFrom[current];path.add(0, current);}return path;}private class Node implements Comparable<node> {public int index;public int fScore;public Node(int index, int fScore) {this.index = index;this.fScore = fScore;}@Overridepublic int compareTo(Node other) {return Integer.compare(this.fScore, other.fScore);}@Overridepublic boolean equals(Object obj) {if (this == obj) {return true;}if (obj == null || getClass() != obj.getClass()) {return false;}Node other = (Node) obj;return index == other.index;}@Overridepublic int hashCode() {return Objects.hash(index);}}}</node></integer></node></integer>Das Obige ist ein Vergleich zwischen Dijkstras Algorithmus und A*. Detaillierte Einführung in den Algorithmus, einschließlich Algorithmusideen, Prozesse und in C# oder Java implementiertem Quellcode. Beide Algorithmen sind häufig verwendete Pfadfindungsalgorithmen und können entsprechend den spezifischen Anforderungen ausgewählt und verwendet werden. Natürlich kann Navigationssoftware in den heutigen Städten Dinge für uns planen.
Das obige ist der detaillierte Inhalt vonBesprechen Sie die Routenplanungsanalyse des Pfadfindungsalgorithmus und die Codeimplementierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
