Prefacio
Un algoritmo de búsqueda* se conoce comúnmente como algoritmo A-Star. Este es un algoritmo que tiene múltiples nodos en el plano gráfico para encontrar el costo más bajo de pasar. Comúnmente utilizado en los juegos
Un laberinto construido a través de una matriz bidimensional, "%" representa el muro, A es el punto de partida, B es el punto final, "#" representa el obstáculo y "*" representa la ruta calculada por el algoritmo
Estructura de código de este artículo:
% % % % % % % % % OOOO % OO # OO % A O # O B % % OO # OO % OOOO % % % % % =================================================================================== S oo * oo % % o * # * o % % a o # o b % % oo # oo % oo % % % % % % % <
Teoría del algoritmo
La fórmula central del algoritmo es: F = G+H
Piense en los nodos en el mapa como una cuadrícula.
G = El consumo de movimiento de moverse al nodo especificado en la cuadrícula desde el punto de partida A a lo largo de la ruta generada. En este ejemplo, hacemos que el movimiento horizontal o vertical cuesta 10 y la dirección diagonal cuesta 14. Tomamos estos valores porque estamos a lo largo de la diagonal
La distancia es la raíz número 2 o aproximadamente 1.414 veces la cantidad tomada para moverse horizontal o verticalmente. Para simplificar, aproximamos el uso de 10 y 14.
Dado que estamos calculando el valor G que conduce a un cuadrado a lo largo de una ruta específica, el método de evaluación es tomar el valor G de su nodo principal, y luego agregar 14 y 10 respectivamente de acuerdo con su dirección diagonal o ángulo recto (no diagonal) en relación con el nodo principal. En el ejemplo, esto
La demanda de cada método se vuelve más porque hemos obtenido más de un cuadrado desde fuera de la cuadrícula inicial.
H = El consumo de movimiento estimado desde la cuadrícula actual hasta el punto final B. ¿Por qué se llama "estimación"? Porque no tenemos forma de saber la longitud de la ruta de antemano. Aquí usamos el método de Manhattan, que calcula horizontal y vertical desde la cuadrícula actual hasta la cuadrícula de destino.
La suma del número de cuadrados de los cuadrados, ignorando la dirección diagonal. Luego multiplique el resultado por 10.
El valor de F es la suma de G y H, que es el estándar que usamos para juzgar la ruta de prioridad. La cuadrícula con el valor más pequeño de F se considera el nodo de ruta prioritaria.
Pasos de implementación
El algoritmo está escrito en Java, primero mire el contenido de la clase de nodo
paquete a_star_search; / ** * clase de nodo * @author zx * */ public class node {private int x; // x coordina private int y; // y coordina el valor de cadena privada; // El valor del nodo privado doble fValue = 0; // F Valor Private Double GValue = 0; // G Valor Private Double HValue = 0; // H Valor Private Boolean acachable; // ¿Es accesible (es un obstáculo) Nodo privado pnode; // nodo público principal nodo (int x, int y, valor de cadena, boolean alcanzable) {super (); this.x = x; this.y = y; this.Value = value; Accesible = alcanzable; } public nodo () {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 () {Valor de retorno; } public void setValue (valor de cadena) {this.value = value; } public doble getfvalue () {return fValue; } public void setfValue (doble fValue) {fValue = fValue; } public doble getgValue () {return gValue; } public void setgValue (doble gValue) {gvalue = gValue; } public doble gethValue () {return hValue; } public void sethValue (doble hvalue) {hValue = hValue; } public boolean isReachable () {return Cachechable; } public void setReachable (boolean alcanzable) {alcanzable = alcanzable; } public nodo getPnode () {return pnode; } public void setPNode (node pnode) {pnode = pnode; }}También necesito una clase de mapa. En el método de construcción del mapa, implemento un mapa de laberinto creando una matriz bidimensional de nodos, que incluye los puntos de inicio y finalización.
paquete a_star_search; public class Map {private nodo [] [] map; // nodo matriz nodo privado startNode; // iniciar el nodo privado endNode; // final de punto public Nodo (i, j, "o", true);}} para (int d = 0; d <7; d ++) {map [0] [d] .setValue ("%"); map [0] [d] .SetReachable (falso); map [d] [0] .SetValue ("%"); map [d] [0] .SetReachable se); mapa [6] [d] .setValue ("%"); mapa [d] [6] .SetValue ("%"); map [d] [6] .setReachable (falso);} map [3] [1] .SetValue ("A"); StartNode; = map [3] [1]; map [3] [5] .setValue ("b"); endnode = map [3] [5]; for (int k = 1; k <= 3; k ++) {map [k+1] [3] .SetValue ("#"); map [k+1] [3] .SetReatable (falso); 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 ("");}} Nodio público [] [] getMap () {regreso map;} setmap (node [] [] map) {this.map = map;} public node getStartNode () {return startNode;} public void setStartNode (node startNode) {this.startNode = startNode;} public node getendNode () {return endNode;} public void setNode (node en endNode) EndNode;}}Estas son las clases de Astar más importantes
Proceso de operación
1 Comience en el punto de partida A y guárdelo como el punto pendiente en una "lista abierta", que es una lista de los cuadrados a verificar.
2 Encuentre todos cuadrados accesibles o pasables alrededor del punto de partida y omita cuadrados incapaces. Agrégalos a la lista de aperturas también. Guarde el punto A para todas estas cuadrículas como la "cuadrícula principal". Cuando queremos describir el camino, el cuadrado principal
El material es muy importante. Su propósito específico se explicará más adelante.
3 Elimine el punto de partida A de la lista Abierta y agréguelo a una "lista cerrada" para guardar todos los cuadrados que no necesitan ser revisados nuevamente.
Después de los pasos anteriores, la "lista abierta" contiene todos los nodos alrededor del punto de partida A, excepto los obstáculos. Sus nodos principales son A. a través de la fórmula F = G+H mencionada anteriormente, calculan los valores G, H y F de cada nodo, y de acuerdo con el valor de F, son pequeños
Clasificando a grande. Y haga las siguientes operaciones en el nodo con el valor F más pequeño
4. Eliméelo de la lista ON y agréguelo a la lista de APAGADO.
5. Verifique todas las cuadrículas adyacentes. Omita los que no se pasan (1. En la "lista de cierre" y 2. Obstáculos) y agréguelos a la lista abierta si aún no están en ella. Tome el cuadrado seleccionado como el nodo principal del nuevo cuadrado.
6. Si una cuadrícula adyacente ya está en la lista abierta, verifique si la ruta actual es mejor. En otras palabras, verifique si el valor G será más bajo si lo alcanzamos con una nueva ruta. Si no, entonces nada
Hacer. (Aquí, no hay juicio en mi código)
7. Repetimos este proceso hasta que la cuadrícula de destino (punto final "b") se agrega a la "lista de apertura", lo que indica que el punto final B ya está alrededor del nodo anterior agregado a la "lista de cierre". Solo necesita dar un paso para llegar al punto final B.
8. Agregamos el punto final B a la "lista de cierre"
9. En el último paso, necesitamos representar la ruta desde el punto de partida A hasta el punto final B. Se muestra el papel del nodo principal. Al cambiar el valor del nodo principal del nodo de punto final en el "Cerrar la lista", puede mostrar la ruta siguiendo las pistas.
Mira el código
paquete a_star_search; import java.util.arrayList; public class Astar {/*** Use ArrayList Array como "Open List" y "Cerrar Lista"*/ArrayList <Node> Open = New ArrayList <Node> (); ArrayList <NodeNode> Close = new ArrayList <Node> ();/*** Get H Value* @Caram* EndNode: End Point* @return*/public Double GethValue (Node CurrentNode, Node EndNode) {return (Math.Abs (currentNode.getx () - endNode.getx ()) + Math.abs (actualizado.node.gety () - endNode.getyy ())* 10;}/*** Obtener G valor* @param CurrentNode: Current Node getGValue (node actualnode) {if (currentNode.getpNode ()! = null) {if (currentNode.getx () == currentNode.getpNode (). getx () || currentNode.gety () == actualnode.getpNode (). gety ()) {// juzga la relación posicional entre el nodo y su nodo plés return -currentNode.getGValue ()+10;} return turrentNode.getGvalue ()+14;} return tutentNode.getGVValue ();}/** * get f valor: g+h * @param currentNode * @return */public double getFvalue (Node CurrentNode) {return currentNode.getGValue ()+currentNode.gethValue ();}/** * Agregue los nodos alrededor del nodo seleccionado a la "lista de abrir" * @param node * @param map */public void inopen (nodo node, map) {int x = node.getx (); int y = node.gety (); for (int i = 0; i <3; i (3; = 0; j <3; j ++) {// La condición del juicio es: el nodo es accesible (es decir, no es un obstáculo, no en la lista cerrada), la lista de aperturas no está incluida y no se selecciona 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]); // el El nodo seleccionado se usa como el nodo principal map.getMap () [x-1+i] [y-1 +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]);}}}/** * Ordene los nodos en la lista abierta de un valor pequeño a grande por f valor * @param arr */public void sort (ArrayList <Node> arr) {for (int i = 0; i <arr.size ()-1; i ++) {for (int j = i+1; j <r.size (); j ++) {if (arr.get (i) .getfvalue ()>>>> 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 (nodo)) {node.setReachable (false); // set inunlase open.remove (nodo); cierre.add (nodo);}} público void bearch (map map) {// Operar los nodos alrededor del punto de inicio, es decir, es, inopen (map.getmap () [map.getstartnode (). getx ()] [map.getstartnode (). gety ()], map); sters.add (map.getmap () [map.getstart Nodo (). etstartNode (). gety ()]. setReachable (false); map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setpNode (map.getMap () [map.getStartNode. do {inOpen (open.get (0), map); inclose (open.get (0), open); sort (open);} while (! Open.contains (map.getMap () [map.getendnode (). getx ()] [map.getendnode (). gety ()]); // cuando usted sabe que el punto final se incluye en la lista abierta, bucle, exit, exit. inclose (map.getMap () [map.getendNode (). getx ()] [map.getEndNode (). Node (); // <span style = "White-space: pre"> </span> node = map.getMap () [map.getendNode (). Getx ()] [map.getendnode (). Gety ()]; == 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");}}Finalmente escribe un método principal
paquete a_star_search; public class Mantest {public static void main (string [] args) {map map = new Map (); Astar astar = new Astar (); map.showmap (); astar.search (mapa); System.out.println("============================================================================================ ================================================================================================================ ================================================================================================================ ================================================================================================================= map.showmap ();Modificar el mapa y probarlo para ver el efecto
% % % % % % % % % OOOO % OO # OO % A O # O B % % OO # OO % OOOO % % % % % ======================================================================================== % % % % % OO # OO % % A # # O B % OO OO # OO # OO % % % %
Resumir
Para garantizar que se encuentre la ruta más corta (la solución óptima), la clave se encuentra en la selección de la función de estimación H (n): el valor de distancia real del valor de estimación h (n) <= n al nodo objetivo. En este caso, hay muchos puntos buscados, el rango de búsqueda es grande y la eficiencia es baja. Pero puede conseguir
Solución óptima. Si el valor estimado> valor real, el número de búsqueda de puntos es pequeño, el rango de búsqueda es pequeño y la eficiencia es alta, pero no puede garantizar que se obtenga la solución óptima.
La mayor sensación es: lo más tabú de la pesca durante tres días y dos días de secar la red. La cantidad puede no ser grande, pero debe ser continuidad, y la clave es la persistencia.
Espero que cada programador pueda escribir con un código feliz y hacer lo que le gusta hacer.
Lo anterior es todo el contenido de este artículo sobre la programación de Java e implementación del código completo de un algoritmo*. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo.