De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

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 cada vez mejores soluciones cuanto más tiempo siga funcionando.

La mayoría de los algoritmos se ejecutan hasta su finalización: proporcionan una única respuesta después de realizar una cantidad fija de cálculo. En algunos casos, sin embargo, el usuario puede desear terminar el algoritmo antes de completarlo. La cantidad de cálculo requerida puede ser sustancial, por ejemplo, y es posible que sea necesario reasignar los recursos computacionales. La mayoría de los algoritmos se ejecutan hasta su finalización o no proporcionan información útil sobre la solución. Sin embargo, en cualquier momento, los algoritmos pueden devolver una respuesta parcial, cuya calidad depende de la cantidad de cálculo que pudieron realizar. La respuesta generada por los algoritmos en cualquier momento es una aproximación de la respuesta correcta.

Nombres

Un algoritmo en cualquier momento también puede denominarse "algoritmo interrumpible". Son diferentes a los algoritmos de contrato, que deben declarar un tiempo por adelantado; en un algoritmo en cualquier momento, un proceso puede simplemente anunciar que está terminando. [1]

Objetivos

El objetivo de los algoritmos en cualquier momento es brindar a los sistemas inteligentes la capacidad de obtener resultados de mejor calidad a cambio de un tiempo de respuesta. [2] También se supone que deben ser flexibles en cuanto a tiempo y recursos. [3] Son importantes porque la inteligencia artificial o los algoritmos de IA pueden tardar mucho en completar los resultados. Este algoritmo está diseñado para completarse en un período de tiempo más corto. [3] Además, estos están destinados a tener una mejor comprensión de que el sistema es dependiente y restringido a sus agentes y cómo funcionan cooperativamente. [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 espera que el algoritmo termine e incluso una respuesta aproximada puede mejorar significativamente su precisión si se da con anticipación. [3]

Lo que hace que los algoritmos en cualquier momento sean únicos es su capacidad para devolver muchos resultados posibles para cualquier entrada determinada. [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] Es posible que no se ejecute hasta que se complete y puede mejorar la respuesta si se permite que se ejecute por más tiempo. [6] Esto se utiliza a menudo para problemas de grandes conjuntos de decisiones. [7] Por lo general, esto no proporcionaría información útil a menos que se le permita finalizar. [8] Si bien esto puede parecer similar aprogramación dinámica , la diferencia es que se ajusta a través de ajustes aleatorios, en lugar de secuencial.

Los algoritmos en cualquier momento están diseñados para que se le pueda decir que se detenga en cualquier momento y devuelva el mejor resultado que haya encontrado hasta ahora. [3] Por eso se le llama algoritmo interrumpible. Ciertos 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]

Árboles de decisión

Cuando el decisor tiene que actuar, debe haber alguna ambigüedad. Además, debe haber alguna idea sobre cómo resolver esta ambigüedad. Esta idea debe ser traducida a un diagrama de estado a acción. [7]

Perfil de rendimiento

El perfil de rendimiento estima la calidad de los resultados en función de la entrada y la cantidad de tiempo que se asigna 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 da la probabilidad de que la salida sea la salida esperada. [3] Es importante tener en cuenta que un algoritmo puede tener varios perfiles de rendimiento. [9] La mayoría de los perfiles de desempeño en el tiempo se construyen usando estadísticas matemáticas usando casos representativos. Por ejemplo, en el problema del viajante de comercio , el perfil de desempeño 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 del tiempo a los resultados esperados. [1] Esta calidad se puede medir de varias formas:

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

Requisitos previos del algoritmo

Comportamiento inicial: si bien algunos algoritmos comienzan con conjeturas inmediatas, otros adoptan un enfoque más calculado y tienen un período de inicio antes de realizar cualquier conjetura. [9]

  • Dirección del crecimiento: cómo varía la calidad del "producto" o resultado del programa en función de la cantidad de tiempo ("tiempo de ejecución") [9]
  • Tasa de crecimiento: cantidad de aumento con cada paso. ¿Cambia constantemente, como en una especie de burbuja o cambia de forma impredecible?
  • Condición final: la cantidad de tiempo de ejecución necesaria [9]

Referencias

  1. ^ a b c d e f Hendler, James A., Sistemas de planificación de inteligencia artificial , 1992
  2. ^ a b c Zilberstein, Shlomo. "Uso de algoritmos en cualquier momento en sistemas inteligentes", 1996. http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  3. ^ a b c d e f g h i Hierba, Joshua. "Razonamiento sobre la asignación de recursos computacionales ". http://www.acm.org/crossroads/xrds3-1/racra.html Archivado el 12 de diciembre de 2007 en la Wayback Machine.
  4. ^ algoritmo en cualquier momento del Diccionario de Computación en línea gratuito (FOLDOC)
  5. ^ "Algoritmos en cualquier momento" . Arquitecturas cognitivas . Laboratorio de Inteligencia Artificial de la Universidad de Michigan. Archivado desde el original el 13 de diciembre de 2013.
  6. ^ "Algoritmo en cualquier momento - Referencia informática" . eLook.org . Archivado desde el original el 12 de diciembre de 2013.
  7. ^ a b Horsch, Michael C., Poole, David "Un algoritmo en cualquier momento para la toma de decisiones bajo incertidumbre", 2013, http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  8. ^ Bender, Edward A. Métodos matemáticos en inteligencia artificial , IEEE Computer Society Pres, 1996
  9. ^ a b c d Teije, Annette diez, Harmelen, Frank. "Descripción de métodos de resolución de problemas utilizando perfiles de rendimiento en cualquier momento", 2000.

Lectura adicional

  • Boddy, M, Dean, T. 1989. Solución de problemas de planificación dependientes del tiempo . Informe técnico: CS-89-03, Brown University
  • Grass, J. y Zilberstein, S. 1996. Herramientas de desarrollo de algoritmos en cualquier momento. Boletín SIGART (Número especial sobre algoritmos en cualquier momento y programación de deliberaciones) 7 (2)
  • Michael C. Horsch y David Poole, An Anytime Algorithm for Decision Making under Uncertainty, In Proc. 14a Conferencia sobre Incertidumbre en Inteligencia Artificial (UAI-98), Madison, Wisconsin, EE. UU., Julio de 1998, páginas 246-255.
  • EJ Horvitz. Razonamiento sobre compensaciones de inferencia en un mundo de recursos limitados . Informe técnico KSL-86-55, Grupo de Ciencias de la Computación Médica, Sección de Informática Médica, Universidad de Stanford, Stanford, CA, marzo de 1986
  • Wallace, R. y Freuder, E. 1995. Algoritmos en cualquier momento para la satisfacción de restricciones y problemas de SAT. Documento presentado en el taller IJCAI-95 sobre algoritmos en cualquier momento y programación de deliberaciones, 20 de agosto, Montreal, Canadá.
  • Zilberstein, S. 1993. Racionalidad operativa a través de la compilación de algoritmos en cualquier momento . Doctor. diss., División de Ciencias de la Computación, Universidad de California en Berkeley.
  • Shlomo Zilberstein, Uso de algoritmos en cualquier momento en sistemas inteligentes, AI Magazine , 17 (3): 73-83, 1996