Límites al Algoritmo A* (A-Estrella)
Para poder explicar cuáles pueden ser sus limitaciones, antes tenemos que explicar, de manera muy superficial, qué es el Algoritmo A* o al menos en qué se basa.
Su función es tratar de encontrar el recorrido más corto entre dos puntos, considerando de paso todos los obstáculos que pueda haber en el camino. Es más sencillo imaginarlo como un recorrido físico del punto A al punto B, y de hecho, es como normalmente se usa (aunque podríamos emplearlo en rompecabezas y juegos de mesa buscando encontrar una solución o buscando “ganar”). Este tipo de algoritmo emplea información heurística (heurístico es que está basado en la experiencia o en la intuición, y en este caso entendemos el término “heurístico” como un conjunto de reglas que permiten obtener un resultado aceptable). Sin embargo, al estar basado en la experiencia e intuición, es posible que falle o que no se llegue a un resultado óptimo, aunque en ocasiones lo haga.
¿Y cómo incorpora la información heurística un programa? Mediante una función de evaluación. Esta evaluará cada “paso” que pudiera darse y le asignará un valor, escogiendo los “caminos” que tengan un valor menor (equivalente a un “coste” menor). Se le asigna un punto de origen y un punto de destino. Empezando desde el origen, considerará todos los movimientos posibles que tiene a nuevos puntos y les asignará un valor en función de dos factores: 1) cómo de cerca le deja ese punto de su “destino” y 2) cuánto le cuesta realizar ese movimiento. Una vez ha otorgado un valor a cada uno de esos puntos, evalua cada uno de ellos de la misma manera. Si resulta que un movimiento le lleva a otro punto ya considerado se elimina el de mayor valor y se queda el de menor valor. Repite este proceso hasta ir asignando valores a todos estos puntos hasta que encuentra el recorrido que menos le vaya a costar hasta su destino. Todo ello está mejor y más visualmente explicado en el siguiente enlace: enlace.
Ya tenemos una idea general, aproximada y probablemente incorrecta de cómo funciona el algoritmo A*. Así que, ¿cuáles son sus limitaciones?
Cuando el área en el que ha de hacer el cálculo es muy grande, tiene muchos caminos que elegir y muchos puntos que evaluar. Esto hace que sea enormemente costoso computacionalmente hablando.
Depende de cómo se asignen los dos valores que hemos visto (el de “cómo de cerca le deja” y “cuánto le cuesta”) podríamos tener unos resultados erróneos. Por ejemplo, si priorizásemos demasiado el de “cómo de cerca le deja” podría escoger caminos que normalmente serían muy costosos, pero no hemos considerado como tal al dar un valores erróneos y por lo tanto el resultado no sería correcto.
Ciertos espacios le pueden resultar complejos al algoritmo A*.
Requiere que los costes sean fijos. Deja de ser un algoritmo viable si los costes varían (por ejemplo, si un camino resulta menos o más costoso bajo ciertas condiciones que puedan ser cambiantes, como pueda ser que un camino sea transitable en verano y no en invierno por la nieve).
Por lo general resulta ser un algoritmo eficaz en problemas limitados, no demasiado grandes y no demasiado variables, lo que hace que en cualquier otro tipo de problemas de búsqueda de recorridos sea recomendable buscar otras maneras de hacerlo. Además es muy dependiente de lo bien que se asigne la información heurística y cualquier error en ello dará errores en el algoritmo.
Referencias:
Pathfinding: A* - lambda lab 85 | lambda lab 85 (lanshor.com)
A* Algorithm in Artificial Intelligence You Must Know in 2023 | Simplilearn
Comentarios
Publicar un comentario