Content deleted Content added
typo its -> it's |
Cybercobra (talk | contribs) cleanup |
||
Line 17:
Make an algorithm with a parameter that influences [[Analysis of algorithms|running time]]. For example, as time increases, this variable also increases. After for a period of time, the search is stopped without having the goal met. This is similar to Jeopardy when the time runs out.<ref name="Bender"/> The contestants have to represent what they believe is the closest answer, although they may not know it or come even close to figuring out what it could be. This is similar to an hour long test. Although the test questions are not in themselves limiting for time, the test must be completed within the hour. Likewise, the computer has to figure out how much time and resources to spend on each problem.<ref name="Bender"/>
== Decision
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.<ref name="Horsch">Horsch, Michael C., Poole, David "An Anytime Algorithm for Decision Making under Uncertainty" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf</ref>
== Performance
The performance profile estimates the quality of the results based on the input and the amount of time that is allotted to the algorithm.<ref name="Grass"/> The better the estimate, the sooner the result would be found.<ref name="Grass"/> Some systems have a larger database that gives the probability that the output is the expected output.<ref name="Grass"/> It is important to note that one algorithm can have several performance profiles.<ref name="Teije">Teije, Annette ten, Harmelen, Frank. "Describing Problem Solving Methods using Anytime Performance Profiles".</ref> Most of the time performance profiles are constructed using [[mathematical statistics]] using representative cases. For example in the [[Travelling salesman problem|traveling salesman]] problem, the performance profile was generated using a user-defined special program to generate the necessary statistics.<ref name="Hendler"/> In this example, the performance profile is the mapping of time to the expected results.<ref name="Hendler"/> This quality can be measured in several ways:
Line 27:
*specificity: where the amount of particulars determine quality<ref name="Hendler"/>
==Algorithm
Initial behavior: While some algorithms start with immediate guesses, others take a more calculated approach and have a start up period before making any guesses.<ref name="Teije"/>
Line 38:
== Further reading ==
{{refbegin}}
* 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)
Line 46:
* 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
{{refend}}
{{DEFAULTSORT:Anytime Algorithm}}
| |||