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 della radice quadrata di un numero.[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
- ^ Anytime algorithms, su ai.eecs.umich.edu, University of Michigan Artificial Intelligence Laboratory (archiviato dall'url originale il 13 Dec 2013).
- ^ Anytime algorithm - Computing Reference, su elook.org (archiviato dall'url originale il 12 Dec 2013).
- ^ Bender, Edward A. Mathematical Methods In Artificial Intelligence, IEEE Computer Society Pres, 1996
- ^ Horsch, Michael C., Poole, David "An Anytime Algorithm for Decision Making under Uncertainty" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
- ^ anytime algorithm from Free Online Dictionary of Computing (FOLDOC)
- ^ Zilberstein, Shlomo. "Using Anytime Algorithms in Intelligent Systems". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
- ^ Grass, Joshua. "Reasoning about Computational Resource Allocation." http://www.acm.org/crossroads/xrds3-1/racra.html
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, July 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, March 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, Montreal, 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
