Algoritmo en cualquier momento

En informática , un algoritmo de ejecución continua es aquel que puede devolver una solución válida a un problema incluso si se interrumpe antes de finalizar. Se espera que el algoritmo encuentre soluciones cada vez mejores cuanto más tiempo se ejecute.

La mayoría de los algoritmos se ejecutan hasta su finalización: proporcionan una única respuesta tras realizar una cantidad fija de cálculos. Sin embargo, en algunos casos, el usuario puede desear finalizar el algoritmo antes de su finalización. Por ejemplo, la cantidad de cálculos requerida puede ser considerable y podría ser necesario reasignar recursos computacionales. La mayoría de los algoritmos se ejecutan hasta su finalización o no proporcionan información útil sobre la solución. Los algoritmos de ejecución continua, en cambio, pueden devolver una respuesta parcial, cuya calidad depende de la cantidad de cálculos que hayan podido realizar. La respuesta generada por estos algoritmos es una aproximación de la respuesta correcta.

Un algoritmo de ejecución en cualquier momento también puede denominarse "algoritmo interrumpible". Se diferencian de los algoritmos contractuales, que deben declarar un tiempo con antelación; en un algoritmo de ejecución en cualquier momento, un proceso simplemente puede anunciar que va a finalizar. ^{[ 1 ]}

El objetivo de los algoritmos de ejecución continua es brindar a los sistemas inteligentes la capacidad de obtener resultados de mejor calidad a cambio de un menor tiempo de respuesta. ^{[ 2 ]} También se supone que son flexibles en cuanto a tiempo y recursos. ^{[ 3 ]} Son importantes porque los algoritmos de inteligencia artificial (IA) pueden tardar mucho tiempo en completar los resultados. Este algoritmo está diseñado para completarse en un tiempo menor. ^{[ 3 ]} Además, están diseñados para comprender mejor que el sistema depende y está restringido a sus agentes y cómo trabajan de forma cooperativa. ^{[ 3 ]} Un ejemplo es la iteración de Newton-Raphson aplicada al cálculo de la raíz cuadrada de un número. ^{[ 4 ]} Otro ejemplo que utiliza algoritmos de ejecución continua son los problemas de trayectoria cuando se apunta a un objetivo; el objeto se mueve por el espacio mientras se espera a 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 únicos a los algoritmos de cualquier tiempo es su capacidad de devolver muchos resultados posibles para cualquier entrada dada. ^{[ 2 ]} Un algoritmo de cualquier tiempo utiliza muchas medidas de calidad bien definidas para monitorear el progreso en la resolución de problemas y los recursos de computación distribuida . ^{[ 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 más tiempo. ^{[ 6 ]} Esto se usa a menudo para problemas de conjuntos de decisión grandes. ^{[ 7 ]} Esto generalmente no proporcionaría información útil a menos que se le permita terminar. ^{[ 8 ]} Si bien esto puede sonar similar a la programación dinámica , la diferencia es que se ajusta finamente a través de ajustes aleatorios, en lugar de secuenciales.

Los algoritmos de ejecución continua están diseñados para que se les pueda indicar que se detengan en cualquier momento y devuelvan el mejor resultado que hayan encontrado hasta el momento. ^{[ 3 ]} Por eso se les llama algoritmos interrumpibles. Algunos algoritmos de ejecución continua también conservan 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 quien toma las decisiones debe 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 el tiempo asignado al algoritmo. ^{[ 3 ]} Cuanto mejor sea la estimación, antes se encontrará el resultado. [ 3 ^] Algunos sistemas tienen una base de datos más grande que proporciona la probabilidad de que la salida sea la esperada. ^{[ 3 ] 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 con casos representativos. Por ejemplo, en el problema del viajante , 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 correspondencia entre el tiempo y los resultados esperados. ^{[ 1 ]} Esta calidad se puede medir de varias maneras:

• certeza: donde la probabilidad de corrección determina la calidad ^{[ 1 ]}
• precisión: donde el límite de error determina la calidad ^{[ 1 ]}
• especificidad: donde la cantidad de detalles determina la calidad ^{[ 1 ]}

Comportamiento inicial: Mientras que algunos algoritmos comienzan con conjeturas inmediatas, otros adoptan un enfoque más calculado y tienen un período de puesta en marcha antes de realizar cualquier conjetura. ^{[ 9 ]}

• Dirección de crecimiento: Cómo varía la calidad de la "salida" o resultado del programa en función de la cantidad de tiempo ("tiempo de ejecución") ^{[ 9 ]}
• Tasa de crecimiento: Cantidad de incremento en cada paso. ¿Cambia constantemente, como en un algoritmo de ordenación de burbuja , o cambia de forma impredecible?
• Condición final: Cantidad de tiempo de ejecución necesario ^{[ 9 ]}