¿Por qué es apropiado utilizar el algoritmo a* para resolver el problema de ocho dígitos?

De hecho, el algoritmo A* también es un algoritmo de mejor primero, pero requiere algunas restricciones. Porque al resolver algunos problemas, esperamos poder resolver el camino más corto de búsqueda en el espacio de estados, es decir, usar el método más rápido para resolver el problema. ¡A * hace este tipo de cosas! Primero definámoslo. Si una función de valoración puede encontrar el camino más corto, lo llamamos admisibilidad. El algoritmo A* es un algoritmo adoptable de mejor primero. La función de valoración del algoritmo A* se puede expresar como: f'(n)=g'(n) h'(n) Aquí, f'(n) es la función de valoración y g'(n) es la más corta ruta desde el punto de partida hasta el nodo n Valor, h'(n) es el valor heurístico de la ruta más corta desde n hasta el objetivo. Dado que f'(n) no puede conocerse de antemano, utilizamos la función de valoración anterior f(n) como aproximación. g(n) reemplaza g'(n), pero solo si g(n)gt;=g'(n) (esto se cumple en la mayoría de los casos y no es necesario considerarlo), h(n) reemplaza h'( n ), pero sólo se puede utilizar h(n)lt;=h'(n) (este punto es particularmente importante). Se puede demostrar que se puede encontrar el camino más corto aplicando dicha función de valoración, lo cual es admisible. Decimos que el algoritmo de mejor prioridad para aplicar esta función de valoración es el algoritmo A*. Para dar un ejemplo, el algoritmo de amplitud es en realidad un caso especial del algoritmo A*. Entre ellos, g (n) es el número de capas donde se encuentra el nodo, h (n) = 0. Este h (n) es definitivamente más pequeño que h '(n), por lo que se puede ver en lo anterior. El algoritmo de amplitud primero es aceptable. También lo es la realidad. Por supuesto, es uno de los algoritmos A* más malolientes. Otra pregunta es sobre el contenido informativo de la función heurística h(n). En términos sencillos, la informatividad de h (n) es en realidad la restricción al estimar el valor de un nodo. Cuanta más información o más restricciones, más nodos se excluirán y mejor será la función de valoración o mejor el algoritmo. . Es por eso que el algoritmo de amplitud es tan apestoso. ¿Quién lo llama h (n) = 0? No hay ninguna información heurística. Sin embargo, debido a problemas de tiempo real en el desarrollo de juegos, cuanta más información tenga h (n), mayor será la cantidad de cálculo y más tiempo llevará. La información de h(n) debe reducirse adecuadamente, es decir, se deben reducir las restricciones. Pero la precisión del algoritmo es deficiente y aquí existe un problema de equilibrio.