Online algorithm
An on-line algorithm is a solution to problems where not all of the input data is available at the beginning of the calculation process.
In the case of many algorithmically solvable problems in computer science , the complete input data are known before the respective algorithm is executed. A solution is calculated and output based on this data. Such problems are called offline problems .
In the case of online problems, on the other hand, the input data is continuously updated when the algorithm is executed. In other words: certain information is only available when certain other data is already available - and can only then be taken into account to solve the problem. The algorithm cannot make assumptions about the complete data.
It is essential that the algorithm has to make decisions before the data is completely available. Usually several times. These decisions can turn out to be unfortunate or bad “in retrospect”, but they can either no longer be taken back or only at additional costs.
An example of an online problem is the search for a shortest path in a graph , whereby the graph is initially unknown and information about the nodes and edges is only obtained when a node is “entered”. An optimal solution can only be achieved with complete information, which requires all nodes to be visited.
The movement of an autonomous robot in an unexplored environment or the navigation of a spider in the World Wide Web are also very similar .
In some cases, machine learning applications also work online ; the system learns during its “work”.
The so-called competitiveness of online algorithms is examined from a theoretical point of view . This is essentially the ratio of the costs of a solution of the online algorithm to those of an optimal solution (which could be calculated with prior knowledge of the complete data) in the worst case (over all possible sequences of information arriving gradually). Depending on the problem, different grades can be achieved here. This notation is closely related to that of the approximation quality of approximation algorithms .
See also
literature
- Allan Borodin, Ran El-Yaniv: Online computation and competitive analysis . Cambridge University Press, Cambridge 2005, ISBN 0-521-61946-7 .