Algoritmo anytime

Un algoritmo anytime è un algoritmo che è in grado di restituire una soluzione valida anche se viene interrotto anticipatamente. Mentre molti algoritmi forniscono una soluzione dopo una certa quantità di calcoli, e non sono in grado di restituire nessun risultato utile fino al completamento dei medesimi, un algoritmo anytime è in grado di fornire una soluzione parziale se interrotto anticipiatamente, e aumentando il tempo a disposizione aumenta anche la qualità attesa della soluzione.[1][2][3][4] Un esempio è l'algoritmo di Newton-Raphson per il calcolo dello zero di una funzione.[5]

Gli algoritmi anytime forniscono ad un sistema intelligente ibrido la capacità di effettuare analisi di migliore qualità in cambio di maggior tempo di computazione,[6] fornendo flessibilità in termini di tempo e risorse.[7]

Note

  1. ^ Anytime algorithms, su Cognitive architectures, University of Michigan Artificial Intelligence Laboratory (archiviato dall'url originale il 13 dicembre 2013).
  2. ^ Anytime algorithm - Computing Reference, su eLook.org (archiviato dall'url originale il 12 dicembre 2013).
  3. ^ Bender, Edward A. Mathematical Methods In Artificial Intelligence, IEEE Computer Society Pres, 1996
  4. ^ Horsch, Michael C., Poole, David "An Anytime Algorithm for Decision Making under Uncertainty" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  5. ^ anytime algorithm from Free Online Dictionary of Computing (FOLDOC)
  6. ^ Zilberstein, Shlomo. "Using Anytime Algorithms in Intelligent Systems". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  7. ^ Grass, Joshua. "Reasoning about Computational Resource Allocation." Copia archiviata, su acm.org. URL consultato il 22 dicembre 2007 (archiviato dall'url originale il 12 dicembre 2007).

Bibliografia

  • Boddy, M, Dean, T. 1989. Solving Time-Dependent Planning Problems. Technical Report: CS-89-03, Brown University
  • Grass, J., and Zilberstein, S. 1996. Anytime Algorithm Development Tools. SIGART Bulletin (Special Issue on Anytime Algorithms and Deliberation Scheduling) 7(2)
  • Michael C. Horsch and David Poole, An Anytime Algorithm for Decision Making under Uncertainty, In Proc. 14th Conference on Uncertainty in Artificial Intelligence (UAI–98), Madison, Wisconsin, USA, luglio 1998, pages 246-255.
  • E.J. Horvitz. Reasoning about inference tradeoffs in a world of bounded resources. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, marzo 1986
  • Wallace, R., and Freuder, E. 1995. Anytime Algorithms for Constraint Satisfaction and SAT Problems. Paper presented at the IJCAI-95 Workshop on Anytime Algorithms and Deliberation Scheduling, 20 August, Montréal, Canada.
  • Zilberstein, S. 1993. Operational Rationality through Compilation of Anytime Algorithms. Ph.D. diss., Computer Science Division, University of California at Berkeley.
  • Shlomo Zilberstein, Using Anytime Algorithms in Intelligent Systems, AI Magazine, 17(3):73-83, 1996
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica