Online and offline problems

1. Online questions

Not knowing all the instance information when making decisions , Decisions made cannot be changed after more information is presented .

2. Offline problems

Examples of all known problems before decision .

3. Online algorithms

You can process the input one by one in a serialized way , In other words, you don't need to know all the inputs at the beginning . Relative , For one Offline algorithm , Know all the data you need to enter at the beginning of the problem , And output the results immediately after solving a problem . for example , Selection sort Before sorting, you need to know all the elements to be sorted , However Insertion sort You don't have to .

Because the online algorithm does not know the whole input , So the choices it is forced to make may eventually prove to be suboptimal , The research on online algorithm mainly focuses on how to make a choice in the current environment . Online algorithms for the same problem and Offline algorithm The above viewpoint is formed by the comparative analysis of . If you want to know about online algorithms from other perspectives, you can take a look Stream Algorithm （ Focus on the amount of memory used to accurately present past inputs ）, Dynamic algorithm （ Focus on what is needed to maintain an online input result Time complexity ） And online machine learning .

A good example of the concept of online algorithms is the Canadian Traveler Problem , The goal of this problem is to reach a target node with the least cost in a weighted graph , But some edges of this weighted graph are unreliable , May have been eliminated . However, a traveler can only determine whether an edge has been removed when he reaches an endpoint of that edge . In the worst case , The problem will become simple , That is, all uncertain edges are removed, and the problem will become common Shortest path problem .

4. Offline algorithm

Offline algorithm design strategies are based on the basic assumption that the input data is known before the implementation of the algorithm , in other words , For an offline algorithm , Know all the data you need to enter at the beginning of the problem , And output the results immediately after solving a problem , Usually, this kind of algorithm designed under the premise of complete information of the problem is called offline Algorithm .

reference

The concept of online algorithm and offline Algorithm - daiyl0320 - Blog Garden