Vorwort
Ein* Suchalgorithmus ist allgemein als A-Stern-Algorithmus bekannt. Dies ist ein Algorithmus, der mehrere Knoten in der Grafikebene enthält, um die niedrigsten Kosten für das Bestehen zu finden. Häufig in Spielen verwendet
Ein durch ein zweidimensionales Array konstruierter Labyrinth, "%", repräsentiert die Wand, A ist der Ausgangspunkt, B ist der Endpunkt, "#" das Hindernis und "*" den durch den Algorithmus berechneten Pfad repräsentiert
Codestruktur dieses Artikels:
% % % % % % % % oooo % oo # oo % % % a # o b % % oo # oo % % oooo % % % % % % % % % % ==============================================ieben oo * oo % % o * # * o % a o # o b % % oo # oo % oo % % % % % % % <
Algorithmustheorie
Die Kernformel des Algorithmus lautet: F = G+H
Stellen Sie sich Knoten auf der Karte als Netz vor.
G = der Bewegungsverbrauch der Bewegung zum angegebenen Knoten am Raster vom Startpunkt A entlang des erzeugten Pfades. In diesem Beispiel machen wir die horizontalen oder vertikalen Bewegung 10 und die diagonale Richtung kostet 14. Wir nehmen diese Werte ein, weil wir entlang der Diagonale sind
Die Entfernung ist die Wurzelnummer 2 oder etwa das 1,414 -fache der Menge, die für horizontal oder vertikal eingesetzt wird. Der Einfachheit halber näheren wir uns mit 10 und 14 an.
Da wir den G-Wert berechnen, der zu einem Quadrat entlang eines bestimmten Pfades führt, besteht die Methode zur Bewertung darin, den G-Wert seines übergeordneten Knotens zu nehmen und dann 14 bzw. 10 gemäß seiner diagonalen Richtung oder dem rechten Winkel (nicht-diagonal) relativ zum Elternknoten hinzuzufügen. In dem Beispiel dies
Die Nachfrage für jede Methode wird mehr, weil wir mehr als ein Quadrat von außerhalb des Startnetzes erhalten haben.
H = der geschätzte Bewegungsverbrauch vom aktuellen Raster bis zum Endpunkt B. Warum wird er als "Schätzung" bezeichnet? Weil wir keine Möglichkeit haben, die Länge des Pfades im Voraus zu kennen. Hier verwenden wir die Manhattan -Methode, die horizontal und vertikal vom aktuellen Netz zum Zielnetz berechnet.
Die Summe der Anzahl der Quadrate der Quadrate und ignorierte die diagonale Richtung. Multiplizieren Sie dann das Ergebnis mit 10.
Der Wert von F ist die Summe von G und H, der Standard, den wir verwenden, um den Prioritätspfad zu beurteilen. Das Gitter mit dem kleinsten Wert von F wird als Prioritätspfadknoten angesehen.
Implementierungsschritte
Der Algorithmus ist in Java geschrieben. Schauen Sie sich zunächst den Inhalt der Knotenklasse an
Paket a_star_search; / ** * Knotenklasse * @Author ZX * */ public class Node {private int x; // x koordiniert private int y; // y koordiniert den privaten String -Wert; // Der Wert des Knotens Private Double fvalue = 0; // f Wert private double gValue = 0; // g Wert private double hvalue = 0; // H Wert privat boolean erreichbar; // Ist es erreichbare (ist es ein Hindernis) Private Knoten Pnode; // Elternknoten öffentlicher Knoten (int x, int y, Stringwert, boolean erreichbar) {Super (); this.x = x; this.y = y; this.Value = Wert; Erreichbar = erreichbar; } public node () {Super (); } public int getX () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; } public String getValue () {Rückgabewert; } public void setValue (String -Wert) {this.Value = value; } public double getfValue () {return fValue; } public void setfValue (double fvalue) {fvalue = fValue; } public double getgValue () {return gValue; } public void setgValue (double gValue) {gValue = gValue; } public double gethvalue () {return hvalue; } public void sethvalue (double hvalue) {hvalue = hvalue; } public boolean isRectable () {return arrangable; } public void setReantable (boolean erreichbar) {AREADABAL = AREADABLE; } public node getPnode () {return pnode; } public void setPnode (Knoten pnode) {pnode = pnode; }}Benötigen Sie auch eine Kartenklasse. In der Kartenkonstruktionsmethode implementiere ich eine Maze-Karte, indem ich ein zweidimensionales Array von Knoten erstelle, das die Start- und Endpunkte enthält.
Paket a_star_search; public class map {private node [] [] map; // Knoten -Array privater Knoten startnode; // Start private Knoten Endnode; // Endpunkt public map () {map = neuer Knoten [7] [7]; für (int i = 0; i <7; i ++) {für (int j = 0; Knoten (i, j, "o", true);}} für (int d = 0; d <7; d ++) {map [0] [d] .setValue ("%"); map [0] [d] .setReachable (false); map [d] [0] .setValue ("%"); map [d] [0] .setReachable (Fal se); map [6] [d] .setValue ("%"); map [d] [6] .setValue ("%"); Karte [d] [6] .SetReantable (false);} Karte [3] [1] .setValue ("a"); = map [3] [1]; map [3] [5] .setValue ("B"); Endnode = MAP [3] [5]; für (int k = 1; k <= 3; k ++) {map [k+1] [3] .setValue ("#"); map [k+1] [3]. map public void ShowMap(){for (int i = 0;i<7;i++){for (int j = 0;j<7;j++){System.out.print(map[i][j].getValue()+" ");}System.out.println("");}}public Node[][] getMap() {return map;}public void setMap (node [] [] map) {this.map = map;} public node getStartNode () {return startNode;} public void setStartNode (node startNode) {this.startNode = startnode;} öffentlicher Knoten getendNode () {thisrg endnode;} public void void setendnode (node {this.Node; {this.Node;} public void void Setendnode (Node {this.Node; Endnode;}}Hier sind die wichtigsten Astar -Klassen
Betriebsprozess
1 Beginnen Sie am Startpunkt A und speichern Sie ihn als ausstehende Punkt in einer "Open List", bei der es sich um eine Liste der zu überprüfen.
2 Finden Sie alle zugänglichen oder passbaren Quadrate um den Startpunkt und überspringen Sie unpassierbare Quadrate. Fügen Sie sie auch zur Eröffnungsliste hinzu. Speichern Sie Punkt A für all diese Netze als "übergeordnetes Netz". Wenn wir den Pfad beschreiben wollen, Quadrat des Elternteils
Material ist sehr wichtig. Sein spezifischer Zweck wird später erklärt.
3 Löschen Sie den Ausgangspunkt A aus der Öffnungsliste und fügen Sie ihn einer "Schließliste" hinzu, um alle Quadrate zu speichern, die nicht erneut überprüft werden müssen.
Nach den obigen Schritten enthält die "Öffnenliste" alle Knoten um den Startpunkt A mit Ausnahme der Hindernisse. Ihre übergeordneten Knoten sind alle A. Durch die zuvor erwähnte Formel F = G+H berechnen sie die Werte G, H und F jedes Knotens, und je nach Wert von F sind sie klein
Sortieren auf groß. Und führen Sie die folgenden Operationen auf dem Knoten mit dem kleinsten F -Wert aus
4. Entfernen Sie es aus der Liste der Auflistung und fügen Sie es in die OFF -Liste hinzu.
5. Überprüfen Sie alle benachbarten Netze. Überspringen Sie diejenigen, die nicht übergeben werden (1. in der "Close -Liste" und 2. Hindernisse), und fügen Sie sie der offenen Liste hinzu, wenn sie noch nicht dabei sind. Nehmen Sie das ausgewählte Quadrat als übergeordnete Knoten des neuen Quadrats.
6. Wenn sich bereits ein benachbartes Raster in der offenen Liste befindet, prüfen Sie, ob der aktuelle Pfad besser ist. Mit anderen Worten, prüfen Sie, ob der G -Wert niedriger ist, wenn wir ihn mit einem neuen Pfad erreichen. Wenn nicht, dann nichts
Tun. (Hier gibt es kein Urteil in meinem Code)
7. Wir wiederholen diesen Vorgang, bis das Zielgitter (Endpunkt "B") zur "Öffnenliste" hinzugefügt wird, was angibt, dass Endpunkt B bereits um den vorherigen Knoten um die "Schließliste" hinzugefügt wird. Sie müssen nur einen Schritt machen, um den Endpunkt B. zu erreichen. B.
8. Wir fügen Endpunkt B zur "Close -Liste" hinzu.
9. Im letzten Schritt müssen wir den Pfad von Startpunkt A bis Endpunkt B darstellen. Die Rolle des übergeordneten Knotens wird angezeigt. Durch Ändern des Wertes des übergeordneten Knotens des Endpunktknotens in der "Liste schließen" können Sie den Pfad anstellen, indem Sie den Hinweisen folgen.
Schauen Sie sich den Code an
Paket a_star_search; importieren java.util.arrayList; öffentliche Klasse Astar {/*** Verwenden Sie Arraylist -Array als "Open List" und "Schließen Sie die Liste"*/ArrayList <node> open = new ArrayList <node> (); ArrayList <node> close = new Arraylist <node> (); point* @return*/public double gethvalue (knoten currentnode, node endnode) {return (math.abs (currentNode.getX () - endnode.getX ()) + math.abs (currentNode.gety () - endnode.gety ())* 10;}/*** -Vennwert @Param @Param Current: currentnode* @ @@Param @param corMalnode: currentnode* @ @@param @param corMalnode: currentnode* @ @@Param @Param @param corMalnode: currentnode* @ @@Param @Param current. CurrentNode) {if (currentNode.getPnode ()! currentNode.getGValue()+10;}return currentNode.getGValue()+14;}return currentNode.getGValue();}/** * Get F value: G + H * @param currentNode * @return */public double getFValue(Node currentNode){return currentNode.getGValue()+currentNode.getHValue();}/** * Fügen Sie die Knoten um den ausgewählten Knoten zum "Open List" @param -Knoten hinzu * @param map */public void inopen (Knotenknoten, Kartenkarte) {int x = node.getX (); int y = node.gety (); für (int i = 0; i <3; i ++). ist, es ist kein Hindernis, nicht in der geschlossenen Liste), die Öffnungsliste ist nicht enthalten und nicht ausgewählt if (map.getMap () [x-1+i] [y-1+j] .isreachable () &&! open.contains (map.getMap () [x-1+i] [y-1+j]) & &! (x == (x-1+i) && y == (y-1+j)) {map.getMap () [x-1+i] [y-1+j] .setpnode (map.getMap () [x] [y]); // die Der ausgewählte Knoten wird als übergeordnete Knoten map.getMap () [x-1+i] [y-1 verwendet +j] .setgValue (getgValue (map.getMap () [x-1+i] [y-1+j]); map.getMap () [x-1+i] [y-1+j] .sethvalue (Gethvalue (map.getMap () [x-1+i] [y-1+j], map.ge tendnode ())); map.getMap () [x-1+i] [y-1+j] .setfValue (getfvalue (map.getMap () [x-1+i] [y-1+j]); open.add (map.getMap () [x-1+i] [y-1+j]);}}}}/** * Sortieren Sie die Knoten in der offenen Liste von klein bis groß durch f Wert * @param arr */public void sort (ArrayList <node> arr) {for (int i = 0; i <arr.size ()-1; i ++) {für (int j = i+1; j <arr.size (); j ++) {wenn (arr.get (i). arr.get(j).getFValue()){Node tmp = new Node();tmp = arr.get(i);arr.set(i, arr.get(j));arr.set(j, tmp);}}}}/** * Add node to "Close List" * @param node * @param open */public void inClose(Node node,ArrayList<Node> Open) {if (open.contains (Knoten)) {node.setReachable (false); // Setzen Sie unberechtigbare Open.remove (Knoten); Close.add (Knoten);}} public void Search (MAP MAP) {// Betätigen Sie die Knoten um den Ausgangspunkt, dh. Inopen (map.getMap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()], map); close.add (map.getMap () [Map.getStart Node (). GetX ()] [map.getStartNode (). GetX ()] [map.getStartNode (). Gety ()]); map.getMap () [map.getStartNode (). GetX ()] [MAP.G etStartNode (). gety ()]. setReachable (false); map.getMap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()]. setpnode (map.getMap () [map.getStartNode () do {inopen (open.get (0), map); incase (open.get (0), open); sort (open);} while (! open.contains (map.getMap () [map.getendnode (). getx ()] [map.getendnode (). Gety ()]). inclose (map.getMap () [map.getendNode (). getX ()] [map.getendNode (). gety ()], öffnen); showPath (schließen, map);}/** * markieren Sie den Pfad * @param arr * @param map */öffentlicher void showpath (arraylist <node> arr, map map) {if (arr) = Node (); // <span style = "White-Space: PRE"> </span> node = map.getMap () [MAP.getendNode (). == map.getStartNode (). gety ()) {// <span style = "White-Space: PRE"> </span> node.getPnode (). SetValue ("*"); style = "White-Space: PRE"> </span> map.getMap () [map.getStartNode (). getX ()] [map.getStartNode (). gety ()]. setValue ("a");}}Schreiben Sie endlich eine Hauptmethode
Paket a_star_search; public class Achtung {public static void main (String [] args) {map Map = new map (); Astar astar = new astar (); map.showmap (); astar.search (map); System.out.println("============================================================================================ ============================================================ieben ============================================================ieben =========================================================ieben map.showmap ();Ändern Sie die Karte und testen Sie sie, um den Effekt anzuzeigen
% % % % % % % % oooo % oo # oo % % A # o b % % oo # oo % oooo % % % % % % % % % % % ============================================ieben % % % % % %
Zusammenfassen
Um sicherzustellen, dass der kürzeste Pfad (die optimale Lösung) gefunden wird, liegt der Schlüssel in der Auswahl der Schätzfunktion H (n): Der tatsächliche Abstandswert des Schätzwerts H (n) <= n zum Zielknoten. In diesem Fall sind viele Punkte durchsucht, der Suchbereich ist groß und die Effizienz niedrig. Aber kann bekommen
Optimale Lösung. Wenn der geschätzte Wert> tatsächlicher Wert, die Suchzahl der Punkte gering ist, ist der Suchbereich gering und die Effizienz hoch, kann jedoch nicht garantieren, dass die optimale Lösung erhalten wird.
Das größte Gefühl ist: Das tabuste Fischen von drei Tagen und zwei Tagen, das das Netz trocknet. Die Menge ist möglicherweise nicht groß, muss aber Kontinuität sein, und der Schlüssel ist die Ausdauer.
Ich hoffe, jeder Programmierer kann gerne Code eingeben und tun, was er gerne tut.
Das obige ist der gesamte Inhalt dieses Artikels über die Java -Programmierung und die Implementierung des vollständigen Code eines* Algorithmus. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen.