Problemas con el Algoritmo A*
TAREA 3 – ALGORITMO A*
El algoritmo A* es de los algoritmos conocidos como Pathfinder, por lo que nos hallará el camino más corto entre dos puntos. Este motivo hace que sea uno de los algoritmos más utilizados. No obstante, presenta una serie de problemas o condiciones que hace que no sea posible aplicar este algoritmo.
El algoritmo A* utiliza una función de evaluación
f(n) = g (n) + h' (n)
donde h'(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g (n) coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial
Leyendo sobre él, he visto que el algoritmo A es un algoritmo completo, por tanto, si existe una solución, siempre dará con ella. Entonces me aparece el primer caso en el cual no lo podríamos aplicar, un caso donde no haya una respuesta. Por ejemplo, si quiero ir únicamente andando hasta Australia, el algoritmo A* no sería útil, ya que no existe una ruta a pie hasta Australia, por tanto, no lo podríamos utilizar.
Luego, he encontrado problemas más técnicos en los que no se puede aplicar dicho algoritmo, pero no se me ocurren ejemplos sobre ellos.
El primero de ellos es que la función f(n) debe ser heurística admisible, es decir, no sobreestime el coste real de alcanzar el nodo objetivo.
Luego hay un problema de complejidad computacional. Con una heurística de pésima calidad, la complejidad será exponencial. Por otro lado, una buena heurística logra el efecto contrario, en este caso, que el problema se solucione en tiempo real.
Otro problema es de complejidad de memoria. El espacio requerido para solucionar el problema será mayor cuanto mayor complejidad tenga el mismo. Como tiene que calcular todas las posibles soluciones, necesitara una buena potencia de memoria.
Además tiene otro problema de complejidad temporal. Está relacionado con el tiempo necesario para resolver el problema. Según el número de nodos, el algoritmo A* necesitará más tiempo, pero siempre tratará de resolverlo en un tiempo óptimo.
Webgrafía:
Comentaris
Publica un comentari a l'entrada