En cualquier momento A*

En informática , el algoritmo A* (anytime A*) es una familia de variantes del algoritmo de búsqueda A* . Al igual que otros algoritmos anytime , tiene un coste temporal flexible y puede devolver una solución válida a un problema de búsqueda de rutas o recorrido de grafos incluso si se interrumpe antes de finalizar, generando una solución rápida, aunque no óptima, antes de optimizarla progresivamente. Esta capacidad de generar soluciones rápidamente lo ha hecho atractivo para sitios web basados ​​en búsquedas y diseños de IA .

Ejecutar el algoritmo A* óptimo hasta su finalización es demasiado costoso para muchos propósitos. La optimalidad de A* puede sacrificarse para reducir el tiempo de ejecución mediante la inflación de la heurística, como en el A* ponderado de 1970. ^{[ 1 ]} Reducir iterativamente el grado en que la heurística está "inflada" proporciona un algoritmo ingenuo en cualquier momento (ATA*, ​​2002), pero esto repite trabajos anteriores. ^{[ 2 ]} Una versión más eficiente y con límites de error que reutiliza resultados, Anytime Repairing A* ( ARA* ), fue reportada en 2003. ^{[ 3 ] [ 4 ]} Una modificación dinámica (en el sentido de D* ) de ARA*, Anytime Dynamic A* ( ADA* ) fue publicada en 2005. Combina aspectos de D* Lite y ARA*. ^{[ 5 ]} Anytime Weighted A* (1997, 2007) es similar a A* ponderado, excepto que continúa la búsqueda después de encontrar la primera solución. Encuentra mejores soluciones iterativamente y, finalmente, encuentra la solución óptima sin repetir el trabajo previo, además de proporcionar límites de error durante toda la búsqueda. ^{[ 6 ] [ 7 ]} Randomized Weighted A* (2021) introdujo la aleatorización en Anytime Weighted A* y demostró un mejor rendimiento empírico. ^{[ 8 ]}

El algoritmo de búsqueda A* se puede representar mediante la función f ( n ) = g ( n ) + h ( n ) , donde n es el último nodo del camino, g( n ) es el coste del camino desde el nodo inicial hasta n , y h ( n ) es una heurística que estima el coste del camino más barato desde n hasta el objetivo. A diferencia del algoritmo A*, la función más importante del algoritmo Anytime A* es que se puede detener y reiniciar en cualquier momento. La familia de algoritmos Anytime A* se basa generalmente en la versión ponderada de la búsqueda A*: donde se utiliza f _w ( n ) = g ( n ) + w × h ( n ) , w > 1 , y se realiza la búsqueda A* como de costumbre, lo que resulta más rápido ya que se expanden menos nodos. ^{[ 1 ]}

ATA* implica ejecutar A* ponderado varias veces, disminuyendo gradualmente w en cada iteración hasta que w = 1, momento en el que la búsqueda se convierte simplemente en A*. Si bien esto podría funcionar llamando a A* repetidamente y descartando toda la memoria anterior, ARA* lo logra introduciendo una forma de actualizar la ruta. ^{[ 4 ]} El valor inicial de w determina el tiempo de ejecución mínimo (primera vez) de ATA*.

Anytime weighted A* convierte a weighted A* en un algoritmo de ejecución continua de la siguiente manera: ^{[ 6 ] [ 7 ]} Cada prueba de objetivo se realiza en la generación de nodos en lugar de en la expansión de nodos, y la solución actual se convierte en el mejor nodo objetivo hasta el momento. A menos que el algoritmo se interrumpa, la búsqueda continúa hasta que se encuentra la solución óptima. Durante la búsqueda, el límite de error es el costo de la solución actual c menos el menor valor f en la lista abierta. La solución óptima se detecta cuando no quedan más nodos con f ( n ) ≤ c abiertos, y en ese momento el algoritmo termina con c como costo de la solución óptima. En 2021, se descubrió que, dado un límite de tiempo de búsqueda, Anytime weighted A* produce mejores soluciones en promedio simplemente cambiando el peso aleatoriamente después de cada expansión de nodos que utilizando un peso estático ajustado o reduciendo gradualmente el peso después de cada solución. ^{[ 8 ]}