En informática , un algoritmo en cualquier momento es un algoritmo que puede devolver una solución válida a un problema incluso si se interrumpe antes de que finalice. Se espera que el algoritmo encuentre soluciones cada vez mejores cuanto más tiempo se mantenga en ejecución.
La mayoría de los algoritmos se ejecutan hasta el final: proporcionan una única respuesta después de realizar una cantidad fija de cálculos. En algunos casos, sin embargo, el usuario puede desear terminar el algoritmo antes de que se complete. La cantidad de cálculos requeridos puede ser sustancial, por ejemplo, y puede ser necesario reasignar recursos computacionales. La mayoría de los algoritmos se ejecutan hasta el final o no proporcionan información útil sobre la solución. Sin embargo, los algoritmos Anytime pueden devolver una respuesta parcial, cuya calidad depende de la cantidad de cálculos que pudieron realizar. La respuesta generada por los algoritmos Anytime es una aproximación de la respuesta correcta.
Un algoritmo de tiempo ininterrumpido también puede denominarse "algoritmo interrumpible". Son diferentes de los algoritmos contractuales, que deben declarar un tiempo por adelantado; en un algoritmo de tiempo ininterrumpido, un proceso puede simplemente anunciar que está terminando. [1]
El objetivo de los algoritmos en cualquier momento es dar a los sistemas inteligentes la capacidad de producir resultados de mejor calidad a cambio de un tiempo de respuesta más rápido. [2] También se supone que deben ser flexibles en cuanto a tiempo y recursos. [3] Son importantes porque los algoritmos de inteligencia artificial o IA pueden tardar mucho tiempo en completar los resultados. Este algoritmo está diseñado para completarse en un período de tiempo más corto. [3] Además, estos tienen como objetivo tener una mejor comprensión de que el sistema depende y está restringido a sus agentes y cómo trabajan de manera cooperativa. [3] Un ejemplo es la iteración de Newton-Raphson aplicada para encontrar la raíz cuadrada de un número. [4] Otro ejemplo que utiliza algoritmos en cualquier momento son los problemas de trayectoria cuando se apunta a un objetivo; el objeto se mueve a través del espacio mientras se espera que el algoritmo termine e incluso una respuesta aproximada puede mejorar significativamente su precisión si se proporciona con anticipación. [3]
Lo que hace que los algoritmos en cualquier momento sean únicos es su capacidad de devolver muchos resultados posibles para cualquier entrada dada. [2] Un algoritmo en cualquier momento utiliza muchas medidas de calidad bien definidas para monitorear el progreso en la resolución de problemas y los recursos informáticos distribuidos . [2] Sigue buscando la mejor respuesta posible con la cantidad de tiempo que se le da. [5] Puede que no se ejecute hasta completarse y puede mejorar la respuesta si se le permite ejecutarse por más tiempo. [6] Esto se usa a menudo para problemas de grandes conjuntos de decisiones. [7] Esto generalmente no proporcionaría información útil a menos que se le permita finalizar. [8] Si bien esto puede sonar similar a la programación dinámica , la diferencia es que se afina a través de ajustes aleatorios, en lugar de secuenciales.
Los algoritmos Anytime están diseñados para que se les pueda indicar que se detengan en cualquier momento y que devuelvan el mejor resultado que hayan encontrado hasta el momento. [3] Por eso se los llama algoritmos interrumpibles. Algunos algoritmos Anytime también mantienen el último resultado, de modo que si se les da más tiempo, pueden continuar desde donde lo dejaron para obtener un resultado aún mejor. [3]
Cuando el decisor tiene que actuar, debe existir cierta ambigüedad. Además, debe existir alguna idea sobre cómo resolver esta ambigüedad. Esta idea debe poder traducirse a un diagrama de estado a acción. [7]
El perfil de rendimiento estima la calidad de los resultados en función de la entrada y la cantidad de tiempo que se le asigna al algoritmo. [3] Cuanto mejor sea la estimación, más pronto se obtendrá el resultado. [3] Algunos sistemas tienen una base de datos más grande que proporciona la probabilidad de que el resultado sea el esperado. [3] Es importante tener en cuenta que un algoritmo puede tener varios perfiles de rendimiento. [9] La mayoría de las veces, los perfiles de rendimiento se construyen utilizando estadísticas matemáticas utilizando casos representativos. Por ejemplo, en el problema del viajante de comercio , el perfil de rendimiento se generó utilizando un programa especial definido por el usuario para generar las estadísticas necesarias. [1] En este ejemplo, el perfil de rendimiento es la asignación de tiempo a los resultados esperados. [1] Esta calidad se puede medir de varias formas:
Comportamiento inicial: mientras que algunos algoritmos comienzan con conjeturas inmediatas, otros adoptan un enfoque más calculado y tienen un período de inicio antes de realizar conjeturas. [9]