Content deleted Content added
No edit summary |
m general cleanup, typo(s) fixed: For example → For example, using AWB |
||
Line 1:
In [[computer science]], an '''anytime algorithm''' is an [[algorithm]] that can return a valid solution to a [[Problem#
▲In [[computer science]], an '''anytime algorithm''' is an [[algorithm]] that can return a valid solution to a [[Problem#Problem_solving|problem]] even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time it keeps running.
Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of the computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer.
Line 21 ⟶ 20:
== Performance profile ==
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:
*certainty: where probability of correctness determines quality<ref name="Hendler"/>
| |||