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 ]}

What makes anytime algorithms unique is their ability to return many possible outcomes for any given input.^[2] An anytime algorithm uses many well defined quality measures to monitor progress in problem solving and distributed computing resources.^[2] It keeps searching for the best possible answer with the amount of time that it is given.^[5] It may not run until completion and may improve the answer if it is allowed to run longer.^[6] This is often used for large decision set problems.^[7] This would generally not provide useful information unless it is allowed to finish.^[8] While this may sound similar to dynamic programming, the difference is that it is fine-tuned through random adjustments, rather than sequential.

Anytime algorithms are designed so that it can be told to stop at any time and would return the best result it has found so far.^[3] This is why it is called an interruptible algorithm. Certain anytime algorithms also maintain the last result, so that if they are given more time, they can continue from where they left off to obtain an even better result.^[3]

When the decider has to act, there must be some ambiguity. Also, there must be some idea about how to solve this ambiguity. This idea must be translatable to a state to action diagram.^[7]

The performance profile estimates the quality of the results based on the input and the amount of time that is allotted to the algorithm.^[3] The better the estimate, the sooner the result would be found.^[3] Some systems have a larger database that gives the probability that the output is the expected output.^[3] One algorithm can have several performance profiles.^[9] Most of the time performance profiles are constructed using mathematical statistics using representative cases. For example, in the traveling salesman problem, the performance profile was generated using a user-defined special program to generate the necessary statistics.^[1] In this example, the performance profile is the mapping of time to the expected results.^[1] This quality can be measured in several ways:

• 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 ]}