{"id":19520,"date":"2021-01-27T09:00:00","date_gmt":"2021-01-27T08:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=19520"},"modified":"2025-06-12T09:17:58","modified_gmt":"2025-06-12T07:17:58","slug":"a-stern-algorithmus-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/a-stern-algorithmus-java\/","title":{"rendered":"A*-Algorithmus (mit Java-Beispiel)"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Wie findet ein Navigationssystem den schnellsten Weg vom Start zum Ziel in m\u00f6glichst geringer Zeit? Dieser Frage (und \u00e4hnlichen) geht diese Artikelserie \u00fcber \"Shortest Path\"-Algorithmen nach.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im vorangegangenen Teil \u00fcber <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Dijkstras Algorithmus<\/a> haben wir festgestellt, dass dieser vom Startpunkt aus erreichbaren Pfaden in alle Richtungen folgt \u2013 und zwar unabh\u00e4ngig davon, in welcher Richtung sich das Ziel befindet. Das ist nat\u00fcrlich nicht optimal.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der A*-Algorithmus (ausgesprochen \"A Stern\" oder englisch \"A Star\") ist eine Weiterentwicklung des Dijkstra-Algorithmus. Der A*-Algorithmus beendet die Pr\u00fcfung von Pfaden, die in die falsche Richtung f\u00fchren, vorzeitig. Dazu verwendet er eine Heuristik, die mit minimalem Aufwand f\u00fcr jeden Knoten die k\u00fcrzestm\u00f6gliche Entfernung zum Ziel berechnen kann. Wie das genau funktioniert, erf\u00e4hrst du in diesem Artikel.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Themen im Einzelnen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wie funktioniert der A*-Algorithmus (Schritt f\u00fcr Schritt an einem Beispiel erkl\u00e4rt)<\/li>\n\n\n\n<li>Was unterscheidet den A*-Algorithmus von Dijkstras Algorithmus?<\/li>\n\n\n\n<li>Wie implementiert man den A*-Algorithmus in Java?<\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t?<\/li>\n\n\n\n<li>Messung der Laufzeit der Java-Implementierung<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Den Quellcode zur gesamten Artikelserie findest du in meinem <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-beispiel\">A*-Algorithmus \u2013 Beispiel<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Wir beginnen mit einem Beispiel. Der Einfachheit halber verwenden wir das gleiche Beispiel wie bei der Erkl\u00e4rung des Dijkstra-Algorithmus. Die folgende Zeichnung stellt eine Stra\u00dfenkarte dar:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1174\" height=\"850\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x.png\" alt=\"\" class=\"wp-image-17370\" style=\"width:587px;height:425px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x.png 1174w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-224x162.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-336x243.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-504x365.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-672x487.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-400x290.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-600x434.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-800x579.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map-2x-944x683.png 944w\" sizes=\"(max-width: 1174px) 100vw, 1174px\" \/><figcaption class=\"wp-element-caption\">Stra\u00dfenkarte<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Orte werden durch Kreise mit Buchstaben dargestellt. Die Linien dazwischen sind Schnellstra\u00dfen (dicke Linien), Dorfstra\u00dfen (d\u00fcnne Linien) und Feldwege (gestrichelte Linien).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Stra\u00dfenkarte bilden wir auf den folgenden Graphen ab. Orte werden zu Knoten; Stra\u00dfe und Wege werden zu Kanten:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1000\" height=\"728\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x.png\" alt=\"A*-Algorithmus: Stra\u00dfenkarte als gewichteter Graph\" class=\"wp-image-17365\" style=\"width:500px;height:364px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x.png 1000w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-224x163.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-336x245.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-504x367.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-672x489.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-400x291.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-600x437.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-800x582.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_street_map_graph-2x-944x687.png 944w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><figcaption class=\"wp-element-caption\">Stra\u00dfenkarte als gewichteter Graph<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die Gewichte der Kanten stellen die Kosten eines Weg dar. Das ist beispielsweise die Zeit in Minuten, die man f\u00fcr das Zur\u00fccklegen eines Weges ben\u00f6tigt. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ein k\u00fcrzerer Weg f\u00fchrt nicht zwingenderma\u00dfen zu niedrigeren Kosten. Es kann z. B. deutlich l\u00e4nger dauern einen kurzen Feldweg zu passieren als eine lange Schnellstra\u00dfe.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir k\u00f6nnen nun z. B. ablesen, dass der k\u00fcrzeste Weg von D nach H \u00fcber F f\u00fchrt und insgesamt 11 Minuten dauert (gelbe Strecke). \u00dcber die l\u00e4ngere Strecke \u00fcber C und G (blaue Strecke) brauchen wir hingegen nur 9 Minuten:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1000\" height=\"778\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2.png\" alt=\"A*-Algorithmus: schnellster Weg und k\u00fcrzester Weg\n\" class=\"wp-image-17363\" style=\"width:500px;height:389px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2.png 1000w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-224x174.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-336x261.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-504x392.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-672x523.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-400x311.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-600x467.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-800x622.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/11\/dijkstras_algorithm_shortest_path-2x-v2-944x734.png 944w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><figcaption class=\"wp-element-caption\">Stra\u00dfenkarte: schnellster Weg und k\u00fcrzester Weg<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Wir Menschen schaffen das mit einem Blick. Auch auf komplexeren Stra\u00dfenkarten k\u00f6nnen wir relativ problemlos navigieren. Die erfahreneren von uns k\u00f6nnen sich sicher noch gut an die Zeiten erinnern, zu denen wir im Auto auf eine Stra\u00dfenkarte blickten anstatt auf ein Navigationssystem.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Ein Computer braucht hierf\u00fcr einen Algorithmus, z. B. den A*-Algorithmus.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-heuristik-funktion\">A*-Algorithmus \u2013 Heuristik-Funktion<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In der Einleitung habe ich eine Heuristik-Funktion erw\u00e4hnt, die den schnellstm\u00f6glichen Weg von allen Knoten des Graphen zum Zielknoten berechnen kann. Da unser Graph eine zweidimensionale Landkarte repr\u00e4sentiert, eignet sich f\u00fcr die Heuristik-Funktion die euklidische Distanz oder \u2013 lapidar gesagt \u2013 die Luftlinie zum Ziel-Knoten.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Heuristik wird im sp\u00e4teren Verlauf daf\u00fcr sorgen, dass der Algorithmus bei der Wegsuche diejenigen Knoten priorisiert, die grob in die richtige Richtung f\u00fchren.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wichtig ist dabei, dass die Heuristik die tats\u00e4chlichen Kosten, die bis zum Ziel anfallen k\u00f6nnten, <em>niemals \u00fcbersch\u00e4tzen<\/em> darf. Damit wir im Beispiel die tats\u00e4chlichen Kosten zum Ziel nicht \u00fcbersch\u00e4tzen, berechnen wir als Heuristik die Anzahl der Minuten, die man auf einer der Luftlinie folgenden Schnellstra\u00dfe zum Ziel ben\u00f6tigen w\u00fcrde.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Um Entfernungen messen zu k\u00f6nnen, f\u00fcgen wir ein Koordinatensystem hinzu:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"908\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates.png\" alt=\"A*-Algorithmus: Stra\u00dfenkarte mit Koordinatensystem\" class=\"wp-image-19682\" style=\"width:600px;height:454px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-224x169.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-336x254.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-504x381.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-672x508.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-400x303.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-600x454.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-800x605.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-map-with-coordinates-944x714.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Stra\u00dfenkarte mit Koordinatensystem<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Wir berechnen nun die L\u00e4nge der zwei Schnellstra\u00dfen von A nach C und von C nach G mit Hilfe des Satzes des Pythagoras. Dann teilen wir die L\u00e4nge durch die Kosten der Strecke, um die Geschwindigkeit zu erhalten:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Weg A\u2013C<\/td><td>Entfernung: 3,414 km<br>Kosten: 2 min<br>Geschwindigkeit: 3,414 km \/ 2 min = 1,707 km\/min (= 102,42 km\/h)<\/td><\/tr><tr><td>Weg C\u2013G<\/td><td>Entfernung: 3,406 km<br>Kosten: 2 min<br>Geschwindigkeit: 3,406 km \/ 2 min = 1,703 km\/min (= 102,18 km\/h)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Die schnellstm\u00f6gliche Geschwindigkeit (v<sub>max<\/sub>) auf unserer Karte wird also auf der Strecke A\u2013C erreicht und betr\u00e4gt etwa 1,7 km\/min (dies entspricht 102 km\/h).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Eigentlich m\u00fcssten wir die Geschwindigkeit f\u00fcr alle Wege berechnen. Aber wir hatten die Karte ja initial so konstruiert, dass alle anderen Stra\u00dfen langsamer sind. Deshalb sparen wir uns das an dieser Stelle.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In einem Navigationssystem ist die schnellstm\u00f6gliche Geschwindigkeit vorberechnet und in den Kartendaten enthalten.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Anwendung der Heuristik-Funktion<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Mit Hilfe der schnellstm\u00f6glichen Geschwindigkeit v<sub>max<\/sub> berechnen wir nun die k\u00fcrzest m\u00f6gliche Fahrtzeit von jedem Punkt der Karte zum Zielpunkt. Dazu berechnen wir jeweils die Entfernung in Form der euklidische Distanz und teilen diese durch v<sub>max<\/sub>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr Knoten A beispielsweise wie folgt:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten A<\/td><td>Entfernung zu Zielknoten H: 6,588 km<br>v<sub>max<\/sub>: 1,707 km\/min<br>Minimale Kosten: 6,588 km \/ 1,707 km\/min = 3,859 min \u2248 3,9 min<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Genauso gehen wir f\u00fcr alle anderen Knoten vor. Es ergeben sich folgende k\u00fcrzestm\u00f6gliche Fahrtzeiten (auf eine Nachkommastelle gerundet):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1000\" height=\"724\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost.png\" alt=\"A*-Algorithmus Stra\u00dfenkarte mit durch die Heuristik-Funktion berechneten Restkosten\" class=\"wp-image-19679\" style=\"width:500px;height:362px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost.png 1000w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-224x162.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-336x243.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-504x365.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-672x487.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-400x290.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-600x434.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-800x579.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-heuristic-remaining-cost-944x683.png 944w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" \/><figcaption class=\"wp-element-caption\">Durch die Heuristik-Funktion berechnete Restkosten<\/figcaption><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vorbereitung-tabelle-der-knoten\">Vorbereitung \u2013 Tabelle der Knoten<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Zur weiteren Vorbereitung erstellen wir eine Tabelle der Knoten. Die Tabelle hat folgende Spalten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Knotenname<\/li>\n\n\n\n<li>Vorg\u00e4nger-Knoten<\/li>\n\n\n\n<li>Gesamtkosten vom Start-Knoten<\/li>\n\n\n\n<li>Minimale Restkosten zum Ziel-Knoten<\/li>\n\n\n\n<li>Summe beider Kosten<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die Vorg\u00e4nger-Knoten bleiben zun\u00e4chst leer. Als Gesamtkosten vom Start tragen wir f\u00fcr den Startknoten selbst eine 0 ein; f\u00fcr alle anderen Knoten <em>unendlich<\/em>, da wir noch nicht wissen, ob diese vom Startknoten \u00fcberhaupt erreichbar sind.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Als minimale Restkosten tragen wir die im vorherigen Abschnitt berechneten Restkosten zum Zielknoten ein.  <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Tabelle wird letztlich nach der Summe der zwei Kostenspalten (Gesamtkosten vom Start-Knoten + Minimale Restkosten zum Ziel-Knoten) sortiert. Die Knoten, bei der die Summe der Kosten <em>unendlich<\/em> ist, bleiben unsortiert (im Beispiel sind sie alphabetisch sortiert):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,5<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,5<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,9<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,2<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,5<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,5<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">G<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,8<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">H<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Im folgenden ist es wichtig die Begriffe&nbsp;<em>Kosten<\/em>, <em>Gesamtkosten<\/em> und <em>Restkosten<\/em> zu unterscheiden:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Kosten<\/em> bezeichnet die Kosten von einem Knoten zu seinen Nachbarknoten.<\/li>\n\n\n\n<li><em>Gesamtkosten<\/em> bezeichnet die Summe aller Teilkosten vom Startknoten \u00fcber eventuelle Zwischenknoten zu einem bestimmten Knoten.<\/li>\n\n\n\n<li><em>Restkosten<\/em> bezeichnet die durch die Heuristik-Funktion berechneten Kosten, die auf dem Weg zum Ziel noch mindestens entstehen werden.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-schritt-fuer-schritt-abarbeitung-der-knoten\">A*-Algorithmus Schritt f\u00fcr Schritt \u2013 Abarbeitung der Knoten<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In den folgenden Grafiken stelle ich in den Knoten den jeweiligen Vorg\u00e4ngerknoten sowie die Gesamt- und Restkosten mit dar. Diese Daten sind in der Regel nicht im Graph enthalten, sondern nur in der oben beschriebenen Tabelle. Sie hier mit anzuzeigen wird das Verst\u00e4ndnis erleichtern.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 1: Betrachten aller Nachbarn des Startpunkts<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Wir entnehmen das erste Element \u2013 Knoten D \u2013 aus der Tabelle und betrachten seine Nachbarn, also C, E und F:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"400\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d.png\" alt=\"A*-Algorithmus Schritt 2: Von D aus erreichbare Knoten\" class=\"wp-image-19599\" style=\"width:400px;height:200px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-224x112.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-336x168.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-504x252.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-672x336.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-400x200.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-600x300.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von D aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die Gesamtkosten der Nachbarknoten stehen zu diesem Zeitpunkt noch auf dem Initialwert <em>unendlich<\/em>, was bedeutet, dass wir bisher noch keine Wege dorthin gefunden haben. Nun <em>haben<\/em> wir Wege dorthin gefunden \u2013 n\u00e4mlich direkt vom Ausgangspunkt D.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir tragen daher als <em>Gesamtkosten vom Start<\/em> die Kosten von D zum jeweiligen Knoten ein und bilden die Summe mit den Restkosten. Au\u00dferdem hinterlegen wir Knoten D als Vorg\u00e4nger.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr C beispielsweise ergeben sich folgende Werte:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Gesamtkosten vom Start: 3,0 (die Kosten von D zu C)<\/li>\n\n\n\n<li>Restkosten: 3,2 (diese haben wir im vorherigen Abschnitt f\u00fcr alle Knoten berechnet)<\/li>\n\n\n\n<li>Summe aller Kosten: 3,0 + 3,2 = 6,2<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr E und F gehen wir genauso vor. F\u00fcr ein einfaches Verst\u00e4ndnis trage ich die Ergebnisse in den Graph ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"400\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after.png\" alt=\"A*-Algorithmus: Kosten und Vorg\u00e4nger der Knoten C, E, F wurden aktualisiert\" class=\"wp-image-19600\" style=\"width:400px;height:200px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-224x112.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-336x168.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-504x252.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-672x336.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-400x200.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-node-d-after-600x300.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Kosten und Vorg\u00e4nger der Knoten C, E, F wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die aktualisierte Tabelle sortieren wir erneut nach der Summe der Kosten (die ge\u00e4nderten Eintr\u00e4ge sind fett markiert):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>1,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">2,5<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>3,5<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>F<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>4,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">1,5<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>5,5<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>3,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">3,2<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>6,2<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,5<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,8<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">G<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,8<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">H<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Die \u00c4nderungen sind so lesen: Knoten E, F und C wurden entdeckt. Sie k\u00f6nnen \u00fcber D in 1, 4 bzw. 3 Minuten erreicht werden. Addiert man die minimalen Restkosten zum Ziel, ergeben sich 3,5, 5,5 und 6,2 Minuten, die man \u00fcber die jeweiligen Knoten mindestens brauchen w\u00fcrde, um das Ziel zu erreichen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Unterschied zum Dijkstra-Algorithmus: Umwege werden gemieden<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Hier wird bereits der Unterschied zum Dijkstra-Algorithmus deutlich. Dort hatten wir die Tabelle nach Gesamtkosten sortiert, weshalb Knoten C (Gesamtkosten 3,0) vor Knoten F (Gesamtkosten 4,0) einsortiert wurde.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Durch die heuristische Komponente liegt beim A*-Algorithmus Knoten F (Kostensumme 5,3) vor Knoten C (Kostensumme 5,8). Der A*-Algorithmus h\u00e4lt es also f\u00fcr wahrscheinlicher das Ziel schneller \u00fcber Knoten F zu erreichen als \u00fcber Knoten C. Wenn wir noch einmal einen Blick auf denjenigen Ausschnitt der Karte werden, den der Algorithmus bis jetzt betrachtet hat, macht das Sinn:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"512\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part.png\" alt=\"A*-Algorithmus: Bisher betrachteter Ausschnitt der Karte\" class=\"wp-image-19602\" style=\"width:400px;height:256px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-224x143.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-336x215.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-504x323.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-672x430.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-400x256.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step2-visible-part-600x384.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Bisher betrachteter Ausschnitt der Karte<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Knoten F liegt in der direkten Richtung zum Zielknoten H, w\u00e4hrend der Weg \u00fcber Knoten C in die falsche Richtung f\u00fchrt.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dass der Umweg \u00fcber Knoten C letztendlich schneller ist, wird A* bald feststellen. In der Regel sind Umwege aber l\u00e4nger. Deshalb ist es gerechtfertig, diese niedriger zu priorisieren.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 2: Betrachten aller Nachbarn von Knoten E<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Wir wiederholen den Prozess f\u00fcr denjenigen Knoten, der jetzt an erster Stelle der Tabelle steht. Das ist Knoten E. Wir entnehmen ihn und betrachten seine Nachbarn, A, B, D und F:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"532\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e.png\" alt=\"A*-Algorithmus: Von E aus erreichbare Knoten\" class=\"wp-image-19604\" style=\"width:400px;height:266px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-224x149.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-336x223.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-504x335.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-672x447.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-400x266.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-600x399.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von E aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Knoten D ist in der Tabelle nicht mehr enthalten. Dies bedeutet, dass wir den k\u00fcrzesten Weg dorthin bereits entdeckt haben (es ist der Startknoten, den wir im vorangegangenen Schritt behandelt haben). Wir k\u00f6nnen ihn daher an dieser Stelle ignorieren.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Knoten A und B haben als Gesamtkosten <em>unendlich<\/em>, d. h. zu ihnen wurde noch kein Weg gefunden. Wir berechnen f\u00fcr diese Knoten die Gesamtkosten vom Start, in dem wir die Gesamtkosten des aktuellen Knotens E und die Kosten von Knoten E zu Knoten A bzw. B addieren:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten A<\/td><td>&nbsp;&nbsp;&nbsp;1,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu E)<\/span><br>+ 3,0 <span style=\"font-size:90%\">(Kosten E\u2013A)<\/span><br>= 4,0<\/td><\/tr><tr><td>Knoten B<\/td><td>&nbsp;&nbsp;&nbsp;1,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu E)<\/span><br>+ 5,0 <span style=\"font-size:90%\">(Kosten E\u2013B)<\/span><br>= 6,0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Zu den jeweiligen Gesamtkosten addieren wir die vorab berechneten minimalen Restkosten zum Ziel:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten A<\/td><td>&nbsp;&nbsp;&nbsp;4,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu A)<\/span><br>+ 3,9 <span style=\"font-size:90%\">(minimale Restkosten von A zum Ziel)<\/span><br>= 7,9<\/td><\/tr><tr><td>Knoten B<\/td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;6,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu B)<\/span><br>+ &nbsp;&nbsp;4,3 <span style=\"font-size:90%\">(minimale Restkosten von B zum Ziel)<\/span><br>= 10,3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Wir aktualisieren die Eintr\u00e4ge in der Grafik:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"532\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after.png\" alt=\"A*-Algorithmus: Kosten und Vorg\u00e4nger der Knoten A, B wurden aktualisiert\" class=\"wp-image-19605\" style=\"width:400px;height:266px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-224x149.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-336x223.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-504x335.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-672x447.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-400x266.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step3-node-e-after-600x399.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Kosten und Vorg\u00e4nger der Knoten A, B wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Zu Knoten F wurde bereits ein Weg gefunden mit Gesamtkosten von 4. Es w\u00e4re m\u00f6glich, dass der Weg \u00fcber den aktuellen Knoten E schneller ist. Um dies zu pr\u00fcfen, berechnen wir auch f\u00fcr Knoten F die Gesamtkosten \u00fcber E:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten F<\/td><td>&nbsp;&nbsp;&nbsp;1,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu E)<\/span><br>+ 6,0 <span style=\"font-size:90%\">(Kosten E\u2013F)<\/span><br>= 7,0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Die \u00fcber E berechneten Gesamtkosten (7,0) sind h\u00f6her als die bisher hinterlegten Gesamtkosten (4,0). Das bedeutet: Wir konnten zwar einen neuen Weg zu F finden, allerdings ist dieser teurer als der bisher bekannte. Somit ignorieren wir ihn, d. h. wir lassen die Tabelleneintr\u00e4ge f\u00fcr Knoten F unver\u00e4ndert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Tabelle sieht nun wie folgt aus (die \u00c4nderungen sind wieder fett markiert):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,5<\/td><td class=\"has-text-align-center\" data-align=\"center\">5,5<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,2<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,2<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>4,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">3,9<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>7,9<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>6,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>10,3<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">G<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,8<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">H<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Die neuen Eintr\u00e4ge sind so lesen: Knoten A und B wurden entdeckt. Sie k\u00f6nnen \u00fcber Knoten E in 4 bzw. 6 Minuten erreicht werden. Addiert man die minimalen Restkosten zum Ziel, ergeben sich 7,9 bzw. 10,3 Minuten, die man \u00fcber die jeweiligen Knoten mindestens brauchen w\u00fcrde, um das Ziel zu erreichen. Diese Werte sind h\u00f6her als die der Knoten F und C, weshalb die Knoten A und B in der Tabelle hinter F und C bleiben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 3: Betrachten aller Nachbarn von Knoten F<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Wir wiederholen das Ganze f\u00fcr Knoten F und betrachten dessen Nachbarn D, E und H:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"586\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f.png\" alt=\"A*-Algorithmus: Von F aus erreichbare Knoten\" class=\"wp-image-19607\" style=\"width:400px;height:293px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-224x164.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-336x246.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-504x369.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-672x492.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-400x293.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-600x440.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von F aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Knoten D und E sind nicht mehr in der Tabelle. Wir haben die k\u00fcrzesten Wege dorthin bereits entdeckt (in den vorangegangenen zwei Schritten). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir m\u00fcssen also nur Knoten H betrachten. Wir berechnen, wie zuvor, die Gesamtkosten vom Start zu Knoten H:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten H<\/td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu F)<\/span><br>+ &nbsp;&nbsp;7,0 <span style=\"font-size:90%\">(Kosten F\u2013H)<\/span><br>= 11,0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Knoten H ist das Ziel. Daher existieren keine Restkosten, die wir noch addieren m\u00fcssten. Wir tragen Vorg\u00e4nger und Gesamtkosten ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"586\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after.png\" alt=\"A*-Algorithmus: Kosten und Vorg\u00e4nger von Knoten H wurde aktualisiert\" class=\"wp-image-19608\" style=\"width:400px;height:293px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-224x164.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-336x246.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-504x369.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-672x492.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-400x293.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step4-node-f-after-600x440.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Kosten und Vorg\u00e4nger von Knoten H wurde aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Wir haben also <em>einen<\/em> Weg zum Zielknoten H gefunden. Dieser f\u00fchrt \u00fcber Knoten F und hat Gesamtkosten von 11,0. Wir aktualisieren Knoten H in der Tabelle:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,2<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,2<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,9<\/td><td class=\"has-text-align-center\" data-align=\"center\">7,9<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\">10,3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>H<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>F<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>11,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>11,0<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">G<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">2,8<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">In der Tabelle existieren noch drei Knoten mit einer Kostensumme von weniger als 11,0. Das bedeutet, dass wir \u00fcber diese drei Knoten m\u00f6glicherweise einen schnelleren Weg zum Ziel finden k\u00f6nnten. Wir m\u00fcssen den Prozess so lange weiterf\u00fchren, bis der Zielknoten die erste Position der Tabelle erreicht hat.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 4: Betrachten aller Nachbarn von Knoten C<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Der n\u00e4chste Knoten in der Tabelle ist Knoten C. Wir entfernen ihn und betrachten seine Nachbarn, A, D und G:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"756\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c.png\" alt=\"A*-Algorithmus: Von C aus erreichbare Knoten\" class=\"wp-image-19611\" style=\"width:400px;height:378px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-224x212.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-336x318.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-504x476.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-672x635.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-400x378.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-600x567.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von C aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Knoten D (unser Startknoten) ist nicht mehr in der Tabelle.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir berechnen, wie schon zuvor, die Gesamtkosten vom Start \u00fcber den aktuellen Knoten C zu den Knoten A und G:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten A<\/td><td>&nbsp;&nbsp;&nbsp;3,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu C)<\/span><br>+ 2,0 <span style=\"font-size:90%\">(Kosten C\u2013A)<\/span><br>= 5,0<\/td><\/tr><tr><td>Knoten G<\/td><td>&nbsp;&nbsp;&nbsp;3,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu C)<\/span><br>+ 2,0 <span style=\"font-size:90%\">(Kosten C\u2013G)<\/span><br>= 5,0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Zu Knoten A hatten wir bereits einen Weg \u00fcber E mit Gesamtkosten vom Start von 4 entdeckt. Die Gesamtkosten \u00fcber den neuen Weg zu A sind mit 5 h\u00f6her, wir ignorieren also den neu entdeckten Weg zu A.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Zu Knoten G hatten wir noch keinen Weg entdeckt. Zu den soeben berechneten Gesamtkosten vom Start addieren wir noch die vorab berechneten Restkosten zum Ziel:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten G<\/td><td>&nbsp;&nbsp;&nbsp;5,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu G)<\/span><br>+ 2,8 <span style=\"font-size:90%\">(minimale Restkosten von G zum Ziel)<\/span><br>= 7,8<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Wir tragen Vorg\u00e4nger und Kosten f\u00fcr Knoten G in die Grafik ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"756\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after.png\" alt=\"A*-Algorithmus: Kosten und Vorg\u00e4nger von Knoten G wurde aktualisiert\" class=\"wp-image-19612\" style=\"width:400px;height:378px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-224x212.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-336x318.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-504x476.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-672x635.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-400x378.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step5-node-c-after-600x567.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Kosten und Vorg\u00e4nger von Knoten G wurde aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Und wir aktualisieren Knoten G in der Tabelle:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>G<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>5,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">2,8<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>7,8<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,9<\/td><td class=\"has-text-align-center\" data-align=\"center\">7,9<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\">10,3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">H<\/td><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">11,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">11,0<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Knoten G ist in der Tabelle auf Platz eins vorger\u00fcckt. Der A*-Algorithmus geht nun also \u2013 mit Hilfe der Heuristik \u2013 davon aus, \u00fcber Knoten G den schnellsten Weg zum Ziel zu finden. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">(Dijkstras Algorithmus w\u00fcrde \u2013 aufgrund der niedrigeren Gesamtkosten vom Start \u2013 mit Knoten A fortfahren.)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 5: Betrachten aller Nachbarn von Knoten G<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Wir entnehmen also Knoten G und betrachten dessen Nachbarn, C und H:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"534\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2.png\" alt=\"A*-Algorithmus: Von G aus erreichbare Knoten\" class=\"wp-image-19619\" style=\"width:400px;height:267px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-224x150.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-336x224.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-504x336.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-672x449.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-400x267.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-v2-600x401.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von G aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Knoten C ist nicht mehr in der Tabelle, diesen hatten wir im vorangegangenen Schritt abgearbeitet.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir berechnen die Gesamtkosten vom Start \u00fcber Knoten G zu Knoten H:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders\"><table><tbody><tr><td>Knoten H<\/td><td>&nbsp;&nbsp;&nbsp;5,0 <span style=\"font-size:90%\">(Gesamtkosten vom Start zu G)<\/span><br>+ 4,0 <span style=\"font-size:90%\">(Kosten G\u2013H)<\/span><br>= 9,0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Die aktuell in Knoten H hinterlegten Kosten betragen 11,0. Wir haben also \u00fcber Knoten G einen schnelleren Weg zum Zielknoten H entdeckt. Wir aktualisieren Vorg\u00e4nger und Kosten in Knoten H:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"534\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after.png\" alt=\"A*-Algorithmus: Kosten und Vorg\u00e4nger von Knoten H wurde aktualisiert\" class=\"wp-image-19617\" style=\"width:400px;height:267px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-224x150.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-336x224.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-504x336.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-672x449.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-400x267.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step6-node-g-after-600x401.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Kosten und Vorg\u00e4nger von Knoten H wurde aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Restkosten existieren im Zielknoten keine.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die aktualisierte Tabelle sieht wie folgt aus:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3,9<\/td><td class=\"has-text-align-center\" data-align=\"center\">7,9<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\"><strong>H<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>G<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>9,0<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>9,0<\/strong><\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\">10,3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Knoten A ist in der Tabelle noch vor dem Zielknoten. Die Summe aller Kosten in diesem Knoten ist mit 7,9 niedriger als die eben berechnete Kostensumme zu Knoten H. Das bedeutet: W\u00fcrden es eine Luftlinienverbindung von Knoten A zum Ziel H geben, dann w\u00e4re der Weg \u00fcber A schneller als der eben gefundene \u00fcber G.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im n\u00e4chsten Schritt wird der Algorithmus herausfinden, ob es einen solchen Weg gibt oder nicht.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 6: Betrachten aller Nachbarn von Knoten A<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Gehen wir es also an: Wir entnehmen Knoten A und betrachten dessen Nachbarn, C und E:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"444\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a.png\" alt=\"A*-Algorithmus: Von A aus erreichbare Knoten\" class=\"wp-image-19630\" style=\"width:400px;height:222px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-504x280.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-672x373.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-400x222.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-step7-node-a-600x333.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Von A aus erreichbare Knoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Beide Knoten sind nicht mehr in der Tabelle enthalten. Wir haben beide schon bearbeitet. Einen unentdeckten Weg zum Ziel finden wir in diesem Schritt also nicht.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Tabelle sieht nun so aus:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Vorg\u00e4nger<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\"><strong>Gesamtkosten<\/strong><br><strong>vom Start<\/strong><\/th><th class=\"has-text-align-center\" data-align=\"center\">Minimale Restkosten<br>zum Ziel<\/th><th class=\"has-text-align-center\" data-align=\"center\">Summe<br>aller Kosten<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">H<\/td><td class=\"has-text-align-center\" data-align=\"center\">G<\/td><td class=\"has-text-align-center\" data-align=\"center\">9,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">0,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">9,0<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">6,0<\/td><td class=\"has-text-align-center\" data-align=\"center\">4,3<\/td><td class=\"has-text-align-center\" data-align=\"center\">10,3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">I<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1,6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Unser Zielknoten hat Platz 1 der Tabelle erreicht.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schnellster Weg zum Ziel wurde gefunden<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Das bedeutet: Es gibt keinen Knoten, \u00fcber den ein noch k\u00fcrzerer Weg zum Ziel gefunden werden k\u00f6nnte.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Auch nicht \u00fcber Knoten B?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Gesamtkosten vom Start zu Knoten B betragen zwar nur 6,0, doch mit den minimalen Restkosten zum Ziel von 4,3 ergeben sich Gesamtkosten von mindestens 10,3, so dass der bisherige Bestwert 9,0 nicht mehr eingeholt werden kann.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"backtrace-zur-bestimmung-des-vollstaendigen-weges\">Backtrace zur Bestimmung des vollst\u00e4ndigen Weges<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Aus der Tabelle k\u00f6nnen wir ablesen: Der Zielknoten H ist am schnellsten \u00fcber Knoten G erreichbar. Doch wie bestimmen wir den vollst\u00e4ndigen Weg vom Startknoten D zum Ziel? Hierzu f\u00fchren wir einen sogenannten \"Backtrace\" durch: Wir beginnen beim Zielknoten und folgen allen Vorg\u00e4ngerknoten, bis wir den Startknoten erreichen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Am einfachsten l\u00e4sst sich das am Graph demonstrieren:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"582\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2.png\" alt=\"A*-Algoroithmus: Backtrace zur Bestimmung des vollst\u00e4ndigen Weges\n\" class=\"wp-image-19722\" style=\"width:400px;height:291px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-224x163.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-336x244.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-504x367.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-672x489.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-400x291.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-backtrace-v2-600x437.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Backtrace zur Bestimmung des vollst\u00e4ndigen Weges<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Der Vorg\u00e4nger des Zielknotens H ist G; der Vorg\u00e4nger von G ist C; und der Vorg\u00e4nger von C ist der Startknoten D. Der schnellste Weg lautet also: D\u2013C\u2013G\u2013H.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"unterschied-a-algorithmus-zu-dijkstras-algorithmus\">Unterschied A*-Algorithmus zu Dijkstras Algorithmus<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Im letzten Schritt wurde der Unterschied zu Dijkstras Algorithmus noch einmal deutlich: Knoten B hat niedrigere Gesamtkosten vom Start (6) als Knoten H (9). Dijkstras Algorithmus w\u00fcrde an dieser Stelle noch pr\u00fcfen m\u00fcssen, ob das Ziel \u00fcber Knoten B schneller erreicht werden k\u00f6nnte. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Durch die Heuristik wei\u00df der A*-Algorithmus an dieser Stelle, dass die Gesamtkosten des Weges \u00fcber Knoten B mindestens 10,3 betragen w\u00fcrden (Kosten vom Start 6,0 plus minimale Restkosten 4,3). Die Kosten des aktuellen Weges (9,0) sind also au\u00dfer Reichweite.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der A*-Algorithmus hat den schnellsten Weg zum Ziel somit in einem Schritt weniger gefunden als Dijkstras Algorithmus ben\u00f6tigt h\u00e4tte. Wir werden sp\u00e4ter sehen, dass der Unterschied bei komplexeren Graphen (wie beispielsweise bei echten Stra\u00dfenkarten) deutlich h\u00f6her ausfallen wird.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-informelle-beschreibung\">A*-Algorithmus \u2013 Informelle Beschreibung<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Vorbereitung:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Erstelle eine Tabelle aller Knoten mit Vorg\u00e4ngerknoten, Gesamtkosten vom Start, minimalen Restkosten zum Ziel und Kostensumme.<\/li>\n\n\n\n<li>Setze die Gesamtkosten des Startknotens auf 0 und die aller anderer Knoten auf&nbsp;<em>unendlich<\/em>.<\/li>\n\n\n\n<li>Berechne \u00fcber die Heuristik-Funktion die minimalen Restkosten zum Ziel f\u00fcr alle Knoten.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Abarbeitung der Knoten:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Solange die Tabelle nicht leer ist, entnehme das Element mit der kleinsten Kostensumme und mache damit folgendes:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ist das entnommene Element der Zielknoten? Wenn ja, ist die Abbruchbedingung erf\u00fcllt. Folge dann den Vorg\u00e4ngerknoten zur\u00fcck zum Startknoten, um den k\u00fcrzesten Weg zu bestimmen.<\/li>\n\n\n\n<li>Andersfalls betrachte alle Nachbarknoten des entnommenen Elements, die sich noch in der Tabelle befinden. F\u00fcr jeden Nachbarknoten:\n<ol class=\"wp-block-list\">\n<li>Berechne die Gesamtkosten vom Start als Summe der Gesamtkosten vom Start zum entnommenen Knoten plus der Kosten vom entnommenen Knoten zum betrachteten Nachbarknoten.<\/li>\n\n\n\n<li>Sind die neu berechneten Gesamtkosten vom Start niedriger als die bisher gespeicherten? Wenn nein, dann ignoriere diesen Nachbarknoten. Wenn ja, dann:\n<ol class=\"wp-block-list\">\n<li>Berechne f\u00fcr den Nachbarknoten die Summe aus den soeben berechneten Gesamtkosten vom Start und den Restkosten zum Ziel. <\/li>\n\n\n\n<li>Trage als Vorg\u00e4nger des Nachbarknotens den entnommenen Knoten ein.<\/li>\n\n\n\n<li>Trage f\u00fcr den Nachbarknoten die neu berechneten Gesamtkosten und die Kostensumme ein.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-java-quellcode\">A*-Algorithmus \u2013 Java-Quellcode<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Im folgenden zeige ich dir, Schritt f\u00fcr Schritt, wie man den A*-Algorithmus in Java implementiert und welche Datenstrukturen man daf\u00fcr optimalerweise verwendet.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Den Code findest du im Paket <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/tree\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\" target=\"_blank\" rel=\"noopener\"><code>eu.happycoders.pathfinding.astar<\/code> in meinem GitHub-Repository<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-fuer-die-knoten-nodewithxycoordinates\">Datenstruktur f\u00fcr die Knoten: NodeWithXYCoordinates<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Zun\u00e4chst brauchen wir eine Datenstruktur, die zu jedem Knoten die X- und Y-Koordinaten speichert (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/NodeWithXYCoordinates.java\" target=\"_blank\">NodeWithXYCoordinates<\/a> im GitHub-Repository):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">NodeWithXYCoordinates<\/span> <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">Comparable<\/span>&lt;<span class=\"hljs-title\">NodeWithXYCoordinates<\/span>&gt; <\/span>{\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> String name;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">double<\/span> x;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">double<\/span> y;\n\n  <span class=\"hljs-comment\">\/\/ Constructur, getters, equals(), hashCode(), compareTo()<\/span>\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die hier nicht mit abgedruckten Methoden <code>equals()<\/code>, <code>hashCode()<\/code> und <code>compareTo()<\/code> basieren auf dem Namen des Knoten.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-fuer-den-graph-guava-valuegraph\">Datenstruktur f\u00fcr den Graph: Guava ValueGraph<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Als Datenstruktur f\u00fcr den Graph verwenden wir die Klasse <a rel=\"noopener\" href=\"https:\/\/guava.dev\/releases\/30.0-jre\/api\/docs\/com\/google\/common\/graph\/ValueGraph.html\" target=\"_blank\">ValueGraph<\/a>&nbsp;der&nbsp;<em>Google Core Libraries for Java<\/em>. Diese stellt verschiedene Graph-Typen bereit, welche <a rel=\"noopener\" href=\"https:\/\/github.com\/google\/guava\/wiki\/GraphsExplained\" target=\"_blank\">hier<\/a>&nbsp;erl\u00e4utert werden. Wir verwenden einen <code>MutableValueGraph<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der folgende Code zeigt, wie wir einen Graph erstellen, der dem aus dem Beispiel oben entspricht. Die X- und Y-Koordinaten habe ich aus der Grafik mit dem Koordinatensystem abgelesen. Die Einheit ist Meter; tats\u00e4chlich ist die Einheit aber irrelevant f\u00fcr das Finden des schnellsten Weges.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> ValueGraph&lt;NodeWithXYCoordinates, Double&gt; <span class=\"hljs-title\">createSampleGraph<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n  MutableValueGraph&lt;NodeWithXYCoordinates, Double&gt; graph =\n      ValueGraphBuilder.undirected().build();\n\n  NodeWithXYCoordinates a = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"A\"<\/span>, <span class=\"hljs-number\">2_410<\/span>, <span class=\"hljs-number\">6_230<\/span>);\n  NodeWithXYCoordinates b = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-number\">8_980<\/span>, <span class=\"hljs-number\">6_080<\/span>);\n  NodeWithXYCoordinates c = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"C\"<\/span>,   <span class=\"hljs-number\">560<\/span>, <span class=\"hljs-number\">3_360<\/span>);\n  NodeWithXYCoordinates d = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-number\">2_980<\/span>, <span class=\"hljs-number\">3_900<\/span>);\n  NodeWithXYCoordinates e = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-number\">4_220<\/span>, <span class=\"hljs-number\">4_280<\/span>);\n  NodeWithXYCoordinates f = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"F\"<\/span>, <span class=\"hljs-number\">4_000<\/span>, <span class=\"hljs-number\">2_600<\/span>);\n  NodeWithXYCoordinates g = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"G\"<\/span>,     <span class=\"hljs-number\">0<\/span>,     <span class=\"hljs-number\">0<\/span>);\n  NodeWithXYCoordinates h = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"H\"<\/span>, <span class=\"hljs-number\">4_850<\/span>,   <span class=\"hljs-number\">110<\/span>);\n  NodeWithXYCoordinates i = <span class=\"hljs-keyword\">new<\/span> NodeWithXYCoordinates(<span class=\"hljs-string\">\"I\"<\/span>, <span class=\"hljs-number\">7_500<\/span>,     <span class=\"hljs-number\">0<\/span>);\n\n  graph.putEdgeValue(a, c, <span class=\"hljs-number\">2.0<\/span>);\n  graph.putEdgeValue(a, e, <span class=\"hljs-number\">3.0<\/span>);\n  graph.putEdgeValue(b, e, <span class=\"hljs-number\">5.0<\/span>);\n  graph.putEdgeValue(b, i, <span class=\"hljs-number\">15.0<\/span>);\n  graph.putEdgeValue(c, d, <span class=\"hljs-number\">3.0<\/span>);\n  graph.putEdgeValue(c, g, <span class=\"hljs-number\">2.0<\/span>);\n  graph.putEdgeValue(d, e, <span class=\"hljs-number\">1.0<\/span>);\n  graph.putEdgeValue(d, f, <span class=\"hljs-number\">4.0<\/span>);\n  graph.putEdgeValue(e, f, <span class=\"hljs-number\">6.0<\/span>);\n  graph.putEdgeValue(f, h, <span class=\"hljs-number\">7.0<\/span>);\n  graph.putEdgeValue(g, h, <span class=\"hljs-number\">4.0<\/span>);\n  graph.putEdgeValue(h, i, <span class=\"hljs-number\">3.0<\/span>);\n\n  <span class=\"hljs-keyword\">return<\/span> graph;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die Typparameter des&nbsp;<code>ValueGraph<\/code>&nbsp;sind:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Typ der Knoten: im Beispiel <code>NodeWithXYCoordinates<\/code>&nbsp;f\u00fcr die Knoten mitsamt ihren X- und Y-Koordinaten<\/li>\n\n\n\n<li>Typ der Kantenwerte: im Beispiel <code>Double<\/code> f\u00fcr die Kosten zwischen zwei Knoten<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Der Graph ist ungerichtet; es spielt also keine Rolle, in welcher Reihenfolge wir die Knoten in der <code>putEdgeValue()<\/code>-Methode angeben.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"heuristik-funktion-heuristicfornodeswithxycoordinates\">Heuristik-Funktion: HeuristicForNodesWithXYCoordinates<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die Heuristik-Funktion muss zu einem gegebenen Knoten die minimalen Restkosten zum Ziel berechnen k\u00f6nnen. Es bietet sich an das <code>Function<\/code>-Interface zu implementieren (im GitHub-Repository findest du die Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/HeuristicForNodesWithXYCoordinates.java\" target=\"_blank\">HeuristicForNodesWithXYCoordinates<\/a> mit zus\u00e4tzlichen Kommentaren und Debug-Ausgaben):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">HeuristicForNodesWithXYCoordinates<\/span>\n    <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">Function<\/span>&lt;<span class=\"hljs-title\">NodeWithXYCoordinates<\/span>, <span class=\"hljs-title\">Double<\/span>&gt; <\/span>{\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">double<\/span> maxSpeed;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> NodeWithXYCoordinates target;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">HeuristicForNodesWithXYCoordinates<\/span><span class=\"hljs-params\">(\n      ValueGraph&lt;NodeWithXYCoordinates, Double&gt; graph, NodeWithXYCoordinates target)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.maxSpeed = calculateMaxSpeed(graph);\n    <span class=\"hljs-keyword\">this<\/span>.target = target;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">double<\/span> <span class=\"hljs-title\">calculateMaxSpeed<\/span><span class=\"hljs-params\">(\n      ValueGraph&lt;NodeWithXYCoordinates, Double&gt; graph)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">return<\/span> graph.edges().stream()\n        .map(edge -&gt; calculateSpeed(graph, edge))\n        .max(Double::compare)\n        .get();\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">double<\/span> <span class=\"hljs-title\">calculateSpeed<\/span><span class=\"hljs-params\">(\n      ValueGraph&lt;NodeWithXYCoordinates, Double&gt; graph,\n      EndpointPair&lt;NodeWithXYCoordinates&gt; edge)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">double<\/span> euclideanDistance = calculateEuclideanDistance(edge.nodeU(), edge.nodeV());\n    <span class=\"hljs-keyword\">double<\/span> cost = graph.edgeValue(edge).get();\n    <span class=\"hljs-keyword\">double<\/span> speed = euclideanDistance \/ cost;\n    <span class=\"hljs-keyword\">return<\/span> speed;\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">double<\/span> <span class=\"hljs-title\">calculateEuclideanDistance<\/span><span class=\"hljs-params\">(\n      NodeWithXYCoordinates source, NodeWithXYCoordinates target)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">double<\/span> distanceX = target.getX() - source.getX();\n    <span class=\"hljs-keyword\">double<\/span> distanceY = target.getY() - source.getY();\n    <span class=\"hljs-keyword\">return<\/span> Math.sqrt(distanceX * distanceX + distanceY * distanceY);\n  }\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Double <span class=\"hljs-title\">apply<\/span><span class=\"hljs-params\">(NodeWithXYCoordinates node)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">double<\/span> euclideanDistance = calculateEuclideanDistance(node, target);\n    <span class=\"hljs-keyword\">double<\/span> minimumCost = euclideanDistance \/ maxSpeed;\n    <span class=\"hljs-keyword\">return<\/span> minimumCost;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Dem Konstrukor werden der Graph und der Zielknoten \u00fcbergeben. In der Methode <code>calculateMaxSpeed()<\/code> wird f\u00fcr alle Kanten die Geschwindigkeit und davon das Maximum bestimmt. Maximalgeschwindigkeit und Zielknoten werden in Instanzvariablen gespeichert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In der <code>apply()<\/code>-Methode wird letztendlich die Heuristik auf den \u00fcbergebenen Knoten angewendet: Es wird die euklidische Distanz zum Zielknoten berechnet und diese durch die Maximalgeschwindigkeit geteilt, um die minimalen Restkosten vom \u00fcbergebenen Knoten zum Ziel zu berechnen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-tabelleneintraege\">Datenstruktur: Tabelleneintr\u00e4ge<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr die Tabelle der Knoten ben\u00f6tigen wir eine Datenstruktur, in der wir zu jedem Knoten dessen Vorg\u00e4nger speichern, sowie die Gesamtkosten vom Start, die minimalen Restkosten zum Ziel und die Kostensumme. Der folgende Code zeigt die daf\u00fcr implementierte Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/AStarNodeWrapper.java\" target=\"_blank\">AStarNodeWrapper<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">AStarNodeWrapper<\/span>&lt;<span class=\"hljs-title\">N<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">Comparable<\/span>&lt;<span class=\"hljs-title\">N<\/span>&gt;&gt;\n    <span class=\"hljs-keyword\">implements<\/span> <span class=\"hljs-title\">Comparable<\/span>&lt;<span class=\"hljs-title\">AStarNodeWrapper<\/span>&lt;<span class=\"hljs-title\">N<\/span>&gt;&gt; <\/span>{\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> N node;\n  <span class=\"hljs-keyword\">private<\/span> AStarNodeWrapper&lt;N&gt; predecessor;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">double<\/span> totalCostFromStart;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> <span class=\"hljs-keyword\">double<\/span> minimumRemainingCostToTarget;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">double<\/span> costSum;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">AStarNodeWrapper<\/span><span class=\"hljs-params\">(\n      N node,\n      AStarNodeWrapper&lt;N&gt; predecessor,\n      <span class=\"hljs-keyword\">double<\/span> totalCostFromStart,\n      <span class=\"hljs-keyword\">double<\/span> minimumRemainingCostToTarget)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.node = node;\n    <span class=\"hljs-keyword\">this<\/span>.predecessor = predecessor;\n    <span class=\"hljs-keyword\">this<\/span>.totalCostFromStart = totalCostFromStart;\n    <span class=\"hljs-keyword\">this<\/span>.minimumRemainingCostToTarget = minimumRemainingCostToTarget;\n    calculateCostSum();\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">calculateCostSum<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.costSum = <span class=\"hljs-keyword\">this<\/span>.totalCostFromStart + <span class=\"hljs-keyword\">this<\/span>.minimumRemainingCostToTarget;\n  }\n\n  <span class=\"hljs-comment\">\/\/ getter for node<\/span>\n  <span class=\"hljs-comment\">\/\/ getters and setters for predecessor<\/span>\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">setTotalCostFromStart<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">double<\/span> totalCostFromStart)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.totalCostFromStart = totalCostFromStart;\n    calculateCostSum();\n  }\n\n  <span class=\"hljs-comment\">\/\/ getter for totalCostFromStart<\/span>\n\n  <span class=\"hljs-meta\">@Override<\/span>\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">compareTo<\/span><span class=\"hljs-params\">(AStarNodeWrapper&lt;N&gt; o)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> compare = Double.compare(<span class=\"hljs-keyword\">this<\/span>.costSum, o.costSum);\n    <span class=\"hljs-keyword\">if<\/span> (compare == <span class=\"hljs-number\">0<\/span>) {\n      compare = node.compareTo(o.node);\n    }\n    <span class=\"hljs-keyword\">return<\/span> compare;\n  }\n\n  \n  <span class=\"hljs-comment\">\/\/ equals(), hashCode()<\/span>\n\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Der Typparameter <code>N<\/code> steht f\u00fcr den Typ der Knoten \u2013 in unserem Beispiel wird das <code>NodeWithXYCoordinates<\/code> sein. Die Parametrisierung erlaubt es uns auch andere Typen zu verwenden, z. B. einen Knoten mit L\u00e4ngen- und Breitengraden \u2013 oder einen mit zus\u00e4tzlicher Z-Koordinate).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im Konstruktor sowie in der Methode <code>setTotalCostFromStart()<\/code> wird <code>calculateCostSum()<\/code> aufgerufen, um die Summe aus Gesamtkosten vom Start und minimalen Restkosten zum Ziel zu berechnen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Diese Summe wird wiederum in der <a href=\"https:\/\/www.happycoders.eu\/de\/java\/comparator-comparable-compareto\/#Das_Java_Comparable_Interface\">compareTo()-Methode<\/a> verwendet, um die nat\u00fcrliche Ordnung der Wrapper-Klasse so zu definieren, dass diese nach Kostensumme aufsteigend sortiert wird. Bei gleicher Kostensumme werden die Knoten selbst verglichen. Im Fall von <code>NodeWithXYCoordinates<\/code> w\u00fcrde dann nach Knotenname sortiert werden. (Warum der zweite Vergleich bei gleicher Kostensumme unbedingt n\u00f6tig ist, wirst du weiter unten erfahren.)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-treeset-als-tabelle\">Datenstruktur: TreeSet als Tabelle<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Wer den <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Artikel \u00fcber Dijkstras Algorithmus<\/a> gelesen hat, wei\u00df, dass die in Pathfinding-Tutorials h\u00e4ufig eingesetzte <code>PriorityQueue<\/code> nicht die optimale Datenstruktur f\u00fcr diese Tabelle ist. Warum das so ist, werde ich im Abschnitt \u00fcber die Zeitkomplexit\u00e4t noch einmal zeigen. Wir verwenden stattdessen ein <code>TreeSet<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Das <code>TreeSet<\/code> liefert mit der <code>pollFirst()<\/code>-Methode das kleinste Elemente zur\u00fcck. Durch die oben beschriebene nat\u00fcrliche Ordnung der <code>AStarNodeWrapper<\/code>-Objekte wird dies immer der Knoten mit der geringsten Summe aus Gesamtkosten vom Start und minimalen Restkosten zum Ziel sein.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"GLSL\" data-shcb-language-slug=\"glsl\"><span><code class=\"hljs language-glsl\">TreeSet&lt;AStarNodeWrapper&lt;N&gt;&gt; queue = new TreeSet&lt;&gt;();<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">GLSL<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">glsl<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-lookup-map-fuer-wrapper\">Datenstruktur: Lookup Map f\u00fcr Wrapper<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Im weiteren Verlauf ben\u00f6tigen eine Map, die f\u00fcr einen Knoten des Graphen den dazugeh\u00f6rigen Wrapper liefert. Hierf\u00fcr verwenden wir eine&nbsp;<code>HashMap<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"GML\" data-shcb-language-slug=\"gml\"><span><code class=\"hljs language-gml\">Map&lt;N, AStarNodeWrapper&lt;N&gt;&gt; nodeWrappers = new HashMap&lt;&gt;();<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">GML<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">gml<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-abgearbeitete-knoten\">Datenstruktur: Abgearbeitete Knoten<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Um pr\u00fcfen zu k\u00f6nnen, ob wir einen Knoten bereits abgearbeitet haben, d. h. den k\u00fcrzesten Weg dorthin gefunden haben, legen wir ein&nbsp;<code>HashSet<\/code> an:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">Set&lt;N&gt; shortestPathFound = <span class=\"hljs-keyword\">new<\/span> HashSet&lt;&gt;();<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vorbereitung-fuellen-der-tabelle\">Vorbereitung: F\u00fcllen der Tabelle<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Kommen wir zum vorbereitenden Schritt, dem F\u00fcllen der Tabelle.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">An dieser Stelle k\u00f6nnen wir eine Optimierung gegen\u00fcber der informellen Beschreibung des Algorithmus vornehmen. Anstatt alle Knoten in die Tabelle zu schreiben, schreiben wir zun\u00e4chst nur den Startknoten. Alle weiteren Knoten f\u00fcgen wir erst dann in die Tabelle ein, wenn wir einen Weg dorthin gefunden haben.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hierdurch schlagen wir drei Fliegen mit einer Klappe:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Wir sparen Tabelleneintr\u00e4ge f\u00fcr diejenigen Knoten, die vom Startpunkt aus nicht erst erreichbar sind oder nur \u00fcber solche Zwischenknoten, deren Kostensumme h\u00f6her ist als die Kosten eines bereits gefundenen Weges (wie im Beispiel der Knoten I).<\/li>\n\n\n\n<li>Auf ebendiese Knoten brauchen wir auch die Heuristik-Funktion nicht anzuwenden.<\/li>\n\n\n\n<li>Wenn wir die Kostensumme eines Knotens, der sich bereits in der Tabelle befindet, neu berechnen, m\u00fcssen wir den Knoten aus der Tabelle entfernen und ihn neu einf\u00fcgen, damit er an die richtige Position sortiert wird. Auch diesen Mehraufwand sparen wir uns, wenn wir die Knoten erst dann einf\u00fcgen, wenn wir einen Weg dorthin entdeckt haben.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Wir beginnen also damit unseren Startknoten in einen <code>AStarNodeWrapper<\/code> einzupacken \u2013 und f\u00fcgen diesen in Lookup-Map und Tabelle ein:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">AStarNodeWrapper&lt;N&gt; sourceWrapper =\n    <span class=\"hljs-keyword\">new<\/span> AStarNodeWrapper&lt;&gt;(source, <span class=\"hljs-keyword\">null<\/span>, <span class=\"hljs-number\">0.0<\/span>, heuristic.apply(source));\nnodeWrappers.put(source, sourceWrapper);\nqueue.add(sourceWrapper);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"iteration-ueber-alle-knoten\">Iteration \u00fcber alle Knoten<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgende Schleife implementiert die schrittweisen Abarbeitung der Knoten (<a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/AStarWithTreeSet.java#L16\" target=\"_blank\" rel=\"noopener\">Methode findShortestPath() in der Klasse AStarWithTreeSet<\/a>):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">while<\/span> (!queue.isEmpty()) {\n  AStarNodeWrapper&lt;N&gt; nodeWrapper = queue.pollFirst();\n  N node = nodeWrapper.getNode();\n  shortestPathFound.add(node);\n\n  <span class=\"hljs-comment\">\/\/ Have we reached the target? --&gt; Build and return the path<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.equals(target)) {\n    <span class=\"hljs-keyword\">return<\/span> buildPath(nodeWrapper);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Iterate over all neighbors<\/span>\n  Set&lt;N&gt; neighbors = graph.adjacentNodes(node);\n  <span class=\"hljs-keyword\">for<\/span> (N neighbor : neighbors) {\n    <span class=\"hljs-comment\">\/\/ Ignore neighbor if shortest path already found<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (shortestPathFound.contains(neighbor)) {\n      <span class=\"hljs-keyword\">continue<\/span>;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Calculate total cost from start to neighbor via current node<\/span>\n    <span class=\"hljs-keyword\">double<\/span> cost =\n        graph.edgeValue(node, neighbor).orElseThrow(IllegalStateException::<span class=\"hljs-keyword\">new<\/span>);\n    <span class=\"hljs-keyword\">double<\/span> totalCostFromStart = nodeWrapper.getTotalCostFromStart() + cost;\n\n    <span class=\"hljs-comment\">\/\/ Neighbor not yet discovered?<\/span>\n    AStarNodeWrapper&lt;N&gt; neighborWrapper = nodeWrappers.get(neighbor);\n    <span class=\"hljs-keyword\">if<\/span> (neighborWrapper == <span class=\"hljs-keyword\">null<\/span>) {\n      neighborWrapper =\n          <span class=\"hljs-keyword\">new<\/span> AStarNodeWrapper&lt;&gt;(\n              neighbor, nodeWrapper, totalCostFromStart, heuristic.apply(neighbor));\n      nodeWrappers.put(neighbor, neighborWrapper);\n      queue.add(neighborWrapper);\n    }\n\n    <span class=\"hljs-comment\">\/\/ Neighbor discovered, but total cost via current node is lower?<\/span>\n    <span class=\"hljs-comment\">\/\/ --&gt; Update total cost and predecessor<\/span>\n    <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (totalCostFromStart &lt; neighborWrapper.getTotalCostFromStart()) {\n      <span class=\"hljs-comment\">\/\/ The position in the TreeSet won't change automatically;<\/span>\n      <span class=\"hljs-comment\">\/\/ we have to remove and reinsert the node.<\/span>\n      <span class=\"hljs-comment\">\/\/ Because TreeSet uses compareTo() to identity a node to remove,<\/span>\n      <span class=\"hljs-comment\">\/\/ we have to remove it *before* we change the cost!<\/span>\n      queue.remove(neighborWrapper);\n\n      neighborWrapper.setTotalCostFromStart(totalCostFromStart);\n      neighborWrapper.setPredecessor(nodeWrapper);\n\n      queue.add(neighborWrapper);\n    }\n  }\n}\n\n<span class=\"hljs-comment\">\/\/ All nodes were visited but the target was not found<\/span>\n<span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Den Code versteht man am besten, wenn man ihn sich Block f\u00fcr Block mitsamt der Kommentare anschaut.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"backtrace-bestimmung-des-weges-vom-start-zum-ziel\">Backtrace: Bestimmung des Weges vom Start zum Ziel<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">In dem mit <em>\"Have we reached the target?\"<\/em> kommentierten <code>if<\/code>-Block wird die Methode <code>buildPath()<\/code> aufgerufen. Diese folgt den Vorg\u00e4ngern vom Zielknoten zur\u00fcck zum Startknoten, tr\u00e4gt dabei alle Knoten in eine Liste ein und gibt diese in umgekehrter Reihenfolge zur\u00fcck:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> &lt;N extends Comparable&lt;N&gt;&gt; <span class=\"hljs-function\">List&lt;N&gt; <span class=\"hljs-title\">buildPath<\/span><span class=\"hljs-params\">(\n    AStarNodeWrapper&lt;N&gt; nodeWrapper)<\/span> <\/span>{\n  List&lt;N&gt; path = <span class=\"hljs-keyword\">new<\/span> ArrayList&lt;&gt;();\n  <span class=\"hljs-keyword\">while<\/span> (nodeWrapper != <span class=\"hljs-keyword\">null<\/span>) {\n    path.add(nodeWrapper.getNode());\n    nodeWrapper = nodeWrapper.getPredecessor();\n  }\n  Collections.reverse(path);\n  <span class=\"hljs-keyword\">return<\/span> path;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Die vollst\u00e4ndige&nbsp;<code>findShortestPath()<\/code>-Methode findest Du in der Klasse&nbsp;<a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/AStarWithTreeSet.java\" target=\"_blank\" rel=\"noopener\">AStarWithTreeSet<\/a> im GitHub-Repository. Aufrufen kannst Du die Methode dann beispielsweise so:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-12\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">ValueGraph&lt;NodeWithXYCoordinates, Double&gt; graph = createSampleGraph();\n\nMap&lt;String, NodeWithXYCoordinates&gt; nodeByName = createNodeByNameMap(graph);\n\nFunction&lt;NodeWithXYCoordinates, Double&gt; heuristic =\n    <span class=\"hljs-keyword\">new<\/span> HeuristicForNodesWithXYCoordinates(graph, target);\n\nList&lt;NodeWithXYCoordinates&gt; shortestPath =\n    AStarWithTreeSet.findShortestPath(\n        graph, nodeByName.get(<span class=\"hljs-string\">\"D\"<\/span>), nodeByName.get(<span class=\"hljs-string\">\"H\"<\/span>), heuristic);<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-12\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p class=\"wp-block-paragraph\">Dieses und andere Beispiele findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/TestWithSampleGraph.java\" target=\"_blank\" rel=\"noopener\">TestWithSampleGraph<\/a> im GitHub-Repository.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Kommen wir nun zur Zeitkomplexit\u00e4t.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-a-algorithmus\">Zeitkomplexit\u00e4t des A*-Algorithmus<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Zur Bestimmung der&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">Zeitkomplexit\u00e4t<\/a>&nbsp;des A*-Algorithmus schauen wir uns den Code Block f\u00fcr Block an, bestimmen f\u00fcr jeden Block die Teilkomplexit\u00e4t und addieren diese im Anschluss.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir bezeichnen dabei die Anzahl der Knoten des Graphes mit <em>n<\/em> und die Anzahl der Kanten mit <em>m<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Berechnung der maximalen Geschwindigkeit im Graphen brauchen wir hier nicht zu ber\u00fccksichtigen, da diese pro Graph nur einmalig erfolgen muss und dann als Teil der Graphdaten gespeichert werden kann. <\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Einf\u00fcgen des Startknotens in die Tabelle:&nbsp;<\/strong>Der Aufwand ist unabh\u00e4ngig von der Gr\u00f6\u00dfe des Graphen, also konstant \u2013 <em>O(1)<\/em>.<\/li>\n\n\n\n<li><strong>Entnehmen der Knoten aus der Tabelle:<\/strong>&nbsp;Der Aufwand f\u00fcr das Entnehmen des kleinsten Elements der Tabelle ist abh\u00e4ngig von der verwendeten Datenstruktur \u2013 wir bezeichnen ihn mit <em>T<sub>em<\/sub><\/em> (\"extract minimum\"). Jeder Knoten wird maximal einmal entnommen, die Komplexit\u00e4t betr\u00e4gt also <em>O(n \u00b7 T<sub>em<\/sub>)<\/em>.<\/li>\n\n\n\n<li><strong>Pr\u00fcfen, ob der k\u00fcrzeste Pfad zu einem Knoten bereits gefunden wurde:<\/strong>&nbsp;F\u00fcr jeden Knoten im Graph erfolgt diese Pr\u00fcfung maximal einmal f\u00fcr alle angrenzenden Knoten. Die Anzahl der angrenzenden Knoten entspricht der Anzahl von wegf\u00fchrenden Kanten. Da jede Kante genau an zwei Knoten angrenzt, gibt es doppelt so viele wegf\u00fchrende Kanten wie Knoten, also <em>2 \u00b7 m<\/em>. F\u00fcr die Pr\u00fcfung verwenden wir ein Set, sie erfolgt also in konstanter Zeit. Insgesamt kommen wir also auf eine Komplexit\u00e4t von <em>O(2 <em>\u00b7<\/em><\/em> m) = <em>O(m)<\/em>.<\/li>\n\n\n\n<li><strong>Berechnung der Gesamtkosten vom Start:<\/strong>&nbsp;Die Berechnung ist eine einfache Addition und hat damit den Aufwand <em>O(1)<\/em>. Die Berechnung erfolgt maximal einmal pro Kante, da wir jeder Kante maximal einmal folgen. Die Komplexit\u00e4t ist also auch f\u00fcr diesen Block <em>O(m)<\/em>.<\/li>\n\n\n\n<li><strong>Zugriff auf NodeWrapper:<\/strong>&nbsp;Der Zugriff auf die Lookup-Map f\u00fcr NodeWrapper erfolgt jeweils nach Berechnung der Gesamtkosten. Der Zugriff ist ebenfalls konstant, die Komplexit\u00e4t f\u00fcr diesen Schritt also auch <em>O(m)<\/em>.<\/li>\n\n\n\n<li><strong>Berechnung der Heuristik: <\/strong>Die Heuristik-Funktion ist mit konstantem Aufwand berechenbar. Sie muss maximal einmal pro Knoten durchgef\u00fchrt werden. Die Komplexit\u00e4t betr\u00e4gt also <em>O(n)<\/em>. <\/li>\n\n\n\n<li><strong>Einf\u00fcgen in die Tabelle:<\/strong>&nbsp;Der Aufwand f\u00fcr das Einf\u00fcgen ist \u2013 genau wie der Aufwand f\u00fcr das Entnehmen \u2013 abh\u00e4ngig von der verwendeten Datenstruktur. Wir bezeichnen ihn mit <em>T<sub>i<\/sub><\/em>&nbsp;(\"insert\"). Jeder Knoten wird maximal einmal eingef\u00fcgt. Die Komplexit\u00e4t betr\u00e4gt demnach <em>O(n \u00b7 T<sub>i<\/sub>)<\/em>.<\/li>\n\n\n\n<li><strong>Aktualisieren der Gesamtkosten und damit der Kostensumme in der Tabelle:<\/strong>&nbsp;Auch dieser Aufwand h\u00e4ngt von der Datenstruktur ab. Beim <code>TreeSet<\/code> beispielsweise mussten wir den Knoten entnehmen und wieder einf\u00fcgen. Andere Datenstrukturen (eine wirst du gleich kennenlernen) haben eine eigenst\u00e4ndige Funktion hierf\u00fcr. Wir bezeichnen den Aufwand allgemein mit&nbsp;<em>T<sub>dk<\/sub><\/em>&nbsp;(\"decrease key\"). Die Funktion wird maximal so oft aufgerufen wie wir die Gesamtkosten vom Start berechnen, also maximal <em>m<\/em> mal. Die Komplexit\u00e4t f\u00fcr diesen Block lautet also <em>O(m \u00b7 T<sub>dk<\/sub>)<\/em>.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Wir addieren alle Teilkomplexit\u00e4ten:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(1) + O(n \u00b7 T<sub>em<\/sub>) + O(m) + O(m) + O(m) + O(n \u00b7 T<sub>i<\/sub>) + O(n) + O(m \u00b7 T<sub>dk<\/sub>)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Konstanter Aufwand&nbsp;<em>O(1)<\/em>&nbsp;kann vernachl\u00e4ssigt werden; ebenso sind <em>O(m)<\/em>&nbsp;gegen\u00fcber&nbsp;<em>O(m \u00b7 T<sub>dk<\/sub>)<\/em>&nbsp;vernachl\u00e4ssigbar und <em>O(n)<\/em> gegen\u00fcber <em>O(n \u00b7 T<sub>em<\/sub>)<\/em> und <em>O(n \u00b7 T<sub>i<\/sub>)<\/em>. Wir k\u00f6nnen den Term daher k\u00fcrzen zu <em>O(n \u00b7 T<sub>em<\/sub>) + (n \u00b7 T<sub>i<\/sub>) + O(m \u00b7 T<sub>dk<\/sub>)<\/em> und dann weiter zusammenfassen zu:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 (T<sub>em<\/sub>+T<sub>i<\/sub>) + m \u00b7 T<sub>dk<\/sub>)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In den folgenden Abschnitten schauen wir uns an, was die Werte f\u00fcr&nbsp;<em>T<sub>em<\/sub><\/em>,&nbsp;<em>T<sub>i<\/sub><\/em> und&nbsp;<em>T<sub>dk<\/sub><\/em> f\u00fcr die verschiedenen Datenstrukturen sind \u2013 und was sich daraus f\u00fcr Gesamtkomplexit\u00e4ten ergeben.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-mit-treeset\">A*-Algorithmus mit TreeSet<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Das im Quellcode verwendete <code>TreeSet<\/code> hat folgenden Komplexit\u00e4ten (diese k\u00f6nnen der <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/15\/docs\/api\/java.base\/java\/util\/TreeSet.html\" target=\"_blank\">TreeSet-Dokumentation<\/a>&nbsp;entnommen werden). F\u00fcr ein besseres Verst\u00e4ndnis gebe ich die <em>T<\/em>-Werte hier mit voller Bezeichnung an:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Kleinsten Eintrag entnehmen mit&nbsp;<code>pollFirst()<\/code>:&nbsp;<em>T<sub>extractMinimum<\/sub>&nbsp;= O(log n)<\/em><\/li>\n\n\n\n<li>Wert einf\u00fcgen mit&nbsp;<code>add()<\/code>:&nbsp;<em>T<sub>insert<\/sub>&nbsp;= O(log n)<\/em><\/li>\n\n\n\n<li>Kosten verringen mit&nbsp;<code>remove()<\/code>&nbsp;und&nbsp;<code>add()<\/code>:&nbsp;<em>T<sub>decreaseKey<\/sub>&nbsp;= O(log n) + O(log n) = O(log n)<\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Wir setzen diese Werte in die allgemeine Formel des vorherigen Abschnitts ein und erhalten:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 log n + m \u00b7 log n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr den Sonderfall, dass die Anzahl der Kanten ein Vielfaches der Anzahl der Knoten ist \u2013 in Landau-Notation:&nbsp;<em>m \u2208 O(n)<\/em>&nbsp;\u2013 k\u00f6nnen wir&nbsp;<em>m<\/em>&nbsp;und&nbsp;<em>n<\/em>&nbsp;bei der Berechnung der Zeitkomplexit\u00e4t gleichsetzen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Formel vereinfacht sich dann zu:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 log n)<\/em>&nbsp;\u2013 f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der Aufwand ist also quasilinear.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Verwendung von <code>TreeSet<\/code> ist zu beachten, dass dieses die Interface-Definition der <code>remove()<\/code>-Methode der <code>Collection<\/code>- und <code>Set<\/code>-Interfaces verletzt, da es das zu l\u00f6schende Element nicht anhand der <code>equals()<\/code>-Methode identifiziert, sondern \u00fcber die <code>compareTo()<\/code>-Methode. Es muss also sichergestellt sein, dass die <code>compareTo()<\/code>-Methode der verwendeten Knotenklasse dann \u2013 und nur dann \u2013 0 zur\u00fcckliefert, wenn auch die <code>equals()<\/code>-Methode <code>true<\/code> ergibt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-mit-treeset\">Laufzeit mit TreeSet<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Mit dem Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/TestAStarRuntime.java\" target=\"_blank\">TestAStarRuntime<\/a> k\u00f6nnen wir messen, wie lange der A*-Algorithmus ben\u00f6tigt, um in Graphen verschiedener Gr\u00f6\u00dfen den k\u00fcrzesten Weg zwischen zwei Punkten zu finden. Das Programm generiert zuf\u00e4llige Graphen und misst dann die Ausf\u00fchrungszeit von <code>AStarWithTreeSet.findShortestPath()<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr jede Graphengr\u00f6\u00dfe werden 50 Tests mit unterschiedlichen Graphen durchgef\u00fchrt und schlie\u00dflich der Median der Messwerte ausgegeben. Das folgende Diagramm zeigt die Messungen der Laufzeit im Verh\u00e4ltnis zur Graphengr\u00f6\u00dfe f\u00fcr das <code>TreeSet<\/code>:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-800x500.png\" alt=\"Zeitkomplexit\u00e4t des A*-Algorithmus mit TreeSet\" class=\"wp-image-19804\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset-944x590.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-treeset.png 1200w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des A*-Algorithmus mit TreeSet<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das vorhergesagte quasilineare Wachstum ist einigerma\u00dfen gut zu erkennen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-mit-priorityqueue\">A*-Algorithmus mit PriorityQueue<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Auswahl der Datenstruktur hatte ich bereits die gerne eingesetzte <code>PriorityQueue<\/code> angesprochen. Warum ist diese keine gute Wahl?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Komplexit\u00e4ten entnehmen wir wieder direkt dem <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/15\/docs\/api\/java.base\/java\/util\/PriorityQueue.html\" target=\"_blank\" rel=\"noopener\">PriorityQueue-JavaDoc<\/a>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Kleinsten Eintrag entnehmen mit&nbsp;<code>poll()<\/code>:&nbsp;<em>T<sub>extractMinimum<\/sub>&nbsp;= O(log n)<\/em><\/li>\n\n\n\n<li>Wert einf\u00fcgen mit&nbsp;<code>offer()<\/code>:&nbsp;<em>T<sub>insert<\/sub>&nbsp;= O(log n)<\/em><\/li>\n\n\n\n<li>Kosten verringen mit&nbsp;<code>remove()<\/code>&nbsp;und&nbsp;<code>offer()<\/code>:&nbsp;<em>T<sub>decreaseKey<\/sub>&nbsp;= O(n) + O(log n) = O(n)<\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die ersten zwei Parameter, <em>T<sub>em<\/sub><\/em> und <em>T<sub>i<\/sub><\/em> gleichen denen des <code>TreeSet<\/code>s.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der dritte Parameter, <em>T<sub>dk<\/sub><\/em> hingegen ist bei der <code>PriorityQueue<\/code> allerdings <em>O(n)<\/em> \u2013 im Gegensatz zum deutlich g\u00fcnstigeren <em>O(log n)<\/em> beim <code>TreeSet<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Was bedeutet das f\u00fcr die Zeitkomplexit\u00e4t des A*-Algorithmus? Wir tragen die Parameter in die allgemeine Formel <em>O(n \u00b7 (T<sub>em<\/sub>+T<sub>i<\/sub>) + m \u00b7 T<sub>dk<\/sub>)<\/em> ein und erhalten:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 (log n + log n) + m \u00b7 n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>log n + log n<\/em> ist <em>2 \u00b7 log n<\/em>, und Konstanten k\u00f6nnen wir weglassen. Der Term verk\u00fcrzt sich somit auf:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 log n + m \u00b7 n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr den Sonderfall <em>m \u2208 O(n)<\/em> (die Anzahl der Kanten ist ein Vielfaches der Anzahl der Knoten), k\u00f6nnen wir die Formel vereinfachen zu <em>O(n \u00b7 log n + n\u00b2)<\/em>. Neben dem quadratischen Anteil <em>n\u00b2<\/em> k\u00f6nnen wir den quasilinearen Anteil <em>n \u00b7 log n<\/em> vernachl\u00e4ssigen. Es bleibt:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n\u00b2)<\/em> \u2013 f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der Einsatz einer <code>PriorityQueue<\/code> f\u00fchrt also zu quadratischem Aufwand, einer deutlich schlechteren Komplexit\u00e4tsklasse als quasilinearer Aufwand.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-mit-priorityqueue\">Laufzeit mit PriorityQueue<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Wenn wir im Programm <code>TestAStarRuntime<\/code> in Zeile 79 die Klasse <code>AStarWithTreeSet<\/code> durch <code>AStarWithPriorityQueue<\/code> (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/astar\/AStarWithPriorityQueue.java\" target=\"_blank\">Klasse in GitHub<\/a>) ersetzen, k\u00f6nnen wir die Laufzeiten unter Verwendung der <code>PriorityQueue<\/code> messen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Das folgende Diagramm zeigt das Messergebnis:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-800x500.png\" alt=\"Zeitkomplexit\u00e4t des A*-Algorithmus mit PriorityQueue\" class=\"wp-image-19805\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue-944x590.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-priorityqueue.png 1200w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des A*-Algorithmus mit PriorityQueue<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das quadratische Wachstum ist sehr gut zu erkennen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"a-algorithmus-mit-fibonacci-heap\">A*-Algorithmus mit Fibonacci-Heap<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Es gibt eine noch besser geeignete Datenstruktur: den Fibonacci-Heap. Dieser garantiert folgende Laufzeiten:<\/p>\n\n\n\n<ul id=\"block-8d734928-cfe2-4147-9b20-a6a62a006bae\" class=\"wp-block-list\">\n<li>Kleinsten Eintrag entnehmen:&nbsp;<em>T<sub>extractMinimum<\/sub>&nbsp;= O(log n)<\/em><\/li>\n\n\n\n<li>Wert einf\u00fcgen:&nbsp;<em>T<sub>insert<\/sub>&nbsp;= O(1)<\/em><\/li>\n\n\n\n<li>Kosten verringen:&nbsp;<em>T<sub>decreaseKey<\/sub>&nbsp;= O(1)<\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Hier haben wir also zwei Anteile mit konstantem Aufwand. Setzen wir die Parameter in die allgemeine Formel <em>O(n \u00b7 (T<sub>em<\/sub>+T<sub>i<\/sub>) + m \u00b7 T<sub>dk<\/sub>)<\/em> ein:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 log n + m)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr den Sonderfall <em>m \u2208 O(n)<\/em> vereinfacht sich die Formel auf:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><em>O(n \u00b7 log n)<\/em>&nbsp;\u2013 f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In Bezug auf die Zeitkomplexit\u00e4t des Gesamtalgorithmus bringt uns der Fibonacci-Heap keinen Vorteil. Wie sieht die Laufzeit in der Praxis aus?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-mit-fibonacci-heap\">Laufzeit mit Fibonacci-Heap<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Das JDK enth\u00e4lt leider keinen Fibonacci-Heap. Stattdessen verwende ich die <a rel=\"noopener\" href=\"https:\/\/keithschwarz.com\/interesting\/code\/?dir=fibonacci-heap\" target=\"_blank\">Fibonacci-Heap-Implementierung von Keith Schwarz<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Diese Klasse und die entsprechende A*-Implementierung habe ich aus Copyright-Gr\u00fcnden nicht in mein Repository kopiert. Du kannst die Klasse unter dem angegebenen Link herunterladen und zur \u00dcbung selbst eine <code>AStarWithFibonacciHeap<\/code>-Klasse schreiben.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Mit dem Fibonacci-Heap erhalte ich folgende Messergebnisse:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-800x500.png\" alt=\"Zeitkomplexit\u00e4t des A*-Algorithmus mit Fibonacci Heap\" class=\"wp-image-19806\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap-944x590.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-time-complexity-fibonacci-heap.png 1200w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des A*-Algorithmus mit Fibonacci Heap<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Der A*-Algorithmus ist also mit dem <code>FibonacciHeap<\/code> noch einmal leicht schneller als mit dem <code>TreeSet<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-zusammenfassung\">Zeitkomplexit\u00e4t \u2013 Zusammenfassung<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die folgende Tabelle zeigt zusammengefasst die Zeitkomplexit\u00e4t des A*-Algorithmus in Abh\u00e4ngigkeit von der eingesetzten Datenstruktur:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th>Datenstruktur<\/th><th class=\"has-text-align-center\" data-align=\"center\">T<sub>em<\/sub><\/th><th class=\"has-text-align-center\" data-align=\"center\">T<sub>i<\/sub><\/th><th class=\"has-text-align-center\" data-align=\"center\">T<sub>dk<\/sub><\/th><th class=\"has-text-align-center\" data-align=\"center\">Zeitkomplexit\u00e4t<br>allgemein<\/th><th class=\"has-text-align-center\" data-align=\"center\">Zeitkomplexit\u00e4t<br>f\u00fcr <em>m \u2208 O(n)<\/em><\/th><\/tr><\/thead><tbody><tr><td>PriorityQueue<\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em><span class=\"has-inline-color has-vivid-red-color\">O(n)<\/span><\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n \u00b7 <em>log n<\/em> + m \u00b7 n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n\u00b2)<\/em><\/td><\/tr><tr><td>TreeSet<\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n \u00b7 log n + m \u00b7 log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n \u00b7 log n)<\/em><\/td><\/tr><tr><td>FibonacciHeap<\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(log n)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em><span class=\"has-inline-color has-vivid-green-cyan-color\">O(1)<\/span><\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em><span class=\"has-inline-color has-vivid-green-cyan-color\">O(1)<\/span><\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n \u00b7 log n + m)<\/em><\/td><td class=\"has-text-align-center\" data-align=\"center\"><em>O(n \u00b7 log n)<\/em><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-a-algorithmus-vs-dijkstras-algorithmus\">Zeitkomplexit\u00e4t A*-Algorithmus vs. Dijkstras Algorithmus<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die Zeitkomplexit\u00e4tsklassen bei A* sind die gleichen wie bei Dijkstra. Doch wie sieht es mit der Laufzeit aus?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im folgenden Diagramm siehst du zus\u00e4tzlich zu den oben gemessenen Laufzeiten diejenigen des <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/#Laufzeit_mit_Fibonacci-Heap\">Dijkstra-Algorithmus<\/a> aus dem vorherigen Artikel:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-800x500.png\" alt=\"Zeitkomplexit\u00e4t des A*-Algorithmus verglichen mit Dijkstras Algorithmus\" class=\"wp-image-19807\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity-944x590.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-vs-dijkstra-time-complexity.png 1200w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des A*-Algorithmus verglichen mit Dijkstras Algorithmus<\/figcaption><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die Laufzeiten sind beim A*-Algorithmus also deutlich besser (zwischen Faktor 2 und 4). Dies ist allerdings keine allgemeing\u00fcltige Aussage. Ob und inwieweit A* schneller ist als Dijkstra h\u00e4ngt stark von der Struktur des Graphen ab. F\u00fcr Stra\u00dfenkarten ist A* in der Regel deutlich schneller.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In einem Labyrinth, in dem der k\u00fcrzeste Weg oft nicht in die direkte Richtung zum Ziel f\u00fchrt, kann das ganz anders aussehen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung-und-ausblick\">Zusammenfassung und Ausblick<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Dieser Artikel hat an einem Beispiel, mit einer informellen Beschreibung und mit Java-Quellcode gezeigt, wie der A*-Algorithmus funktionert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr die Zeitkomplexit\u00e4t haben wir zun\u00e4chst eine allgemeine Landau-Notation hergeleitet und diese anschlie\u00dfend f\u00fcr die Datenstrukturen <code>TreeSet<\/code>, <code>PriorityQueue<\/code> und <code>FibonacciHeap<\/code> konkretisiert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Zeitkomplexit\u00e4ten entsprechen denen des Dijkstra-Algorithmus; die Laufzeiten sind bei A* deutlich besser als bei Dijkstra. Wenn eine Heuristik-Funktion definiert werden kann und der schnellste Weg in der Regel grob in die Richtung des Ziels f\u00fchrt, ist also immer der A*-Algorithmus vorzuziehen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Vorschau: Bellman-Ford-Algorithmus<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Es gibt allerdings auch Situationen, in denen weder Dijkstra noch A* ein geeigneter Algorithmus sind: Wenn es Kanten mit negativen Gewichten gibt, w\u00fcrden Dijkstra und A* diese ignorieren, wenn diese auf einen Knoten folgen w\u00fcrden, zu dem die Kosten h\u00f6her sind als die eines bereits entdeckten Weges zum Ziel.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie negative Kantengewichte in der Realit\u00e4t (und nicht nur in einem konstruierten mathematischen Modell) \u00fcberhaupt existieren k\u00f6nnen \u2013 und wie man das K\u00fcrzeste-Wege-Problem in so einem Fall l\u00f6st, erf\u00e4hrst Du im n\u00e4chsten Artikel \u00fcber den <a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/\">Bellman-Ford-Algorithmus<\/a>.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Wie funktioniert der A*-Algorithmus und was unterscheidet ihn von Dijkstras Algorithmus? Wie implementiert man A* in Java? Wie bestimmt man die Zeitkomplexit\u00e4t?<\/p>\n","protected":false},"author":1,"featured_media":43217,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert der A*-Algorithmus? Wie implementiert man den A*-Algorithmus in Java? Wie bestimmt man die Zeitkomplexit\u00e4t?","_seopress_robots_index":"","_seopress_robots_follow":"","_seopress_robots_imageindex":"","_seopress_robots_snippet":"","_seopress_robots_primary_cat":"none","_seopress_robots_breadcrumbs":"","_seopress_robots_freeze_modified_date":"","_seopress_robots_custom_modified_date":"","_seopress_robots_canonical":"","_seopress_social_fb_title":"","_seopress_social_fb_desc":"","_seopress_social_fb_img":"","_seopress_social_fb_img_attachment_id":0,"_seopress_social_fb_img_width":0,"_seopress_social_fb_img_height":0,"_seopress_social_twitter_title":"","_seopress_social_twitter_desc":"","_seopress_social_twitter_img":"","_seopress_social_twitter_img_attachment_id":0,"_seopress_social_twitter_img_width":0,"_seopress_social_twitter_img_height":0,"_seopress_redirections_value":"","_seopress_redirections_enabled":"","_seopress_redirections_enabled_regex":"","_seopress_redirections_logged_status":"","_seopress_redirections_param":"","_seopress_redirections_type":301,"_seopress_analysis_target_kw":"a*-algorithmus","_seopress_news_disabled":"","_seopress_video_disabled":"","_seopress_video":[],"_seopress_pro_schemas_manual":[{"_seopress_pro_rich_snippets_type":"none"}],"_seopress_pro_rich_snippets_disable_all":"","_seopress_pro_rich_snippets_disable":[],"_seopress_pro_schemas":[],"_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":45196,"_post_count":0,"footnotes":""},"categories":[127],"tags":[137],"class_list":["post-19520","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-algorithmen-pathfinding"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/01\/a-star-algorithm-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":3,"uagb_excerpt":"Wie funktioniert der A*-Algorithmus und was unterscheidet ihn von Dijkstras Algorithmus? Wie implementiert man A* in Java? Wie bestimmt man die Zeitkomplexit\u00e4t?","public_identification_id":"76c7ffa7ae894dd89b86c9e38673fe19","private_identification_id":"b85cc0485a1e4402ae7e624f34318dc6","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/19520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=19520"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/19520\/revisions"}],"predecessor-version":[{"id":52496,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/19520\/revisions\/52496"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43217"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=19520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=19520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=19520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}