当前位置:网站首页>Online and offline problems
Online and offline problems
2022-07-06 06:12:00 【Zhan Miao】
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
边栏推荐
- properties文件
- [wechat applet] build a development tool environment
- P问题、NP问题、NPC问题、NP-hard问题详解
- 曼哈顿距离与曼哈顿矩形-打印回字型矩阵
- 【Postman】Collections-运行配置之导入数据文件
- A complete collection of necessary learning websites for office programmers
- 二维码的前世今生 与 六大测试点梳理
- Huawei BFD configuration specification
- PAT(乙级)2022年夏季考试
- Title 1093: character reverse order
猜你喜欢
随机推荐
H3C S5820V2_ Upgrade method after stacking IRF2 of 5830v2 switch
Raised a kitten
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
假设检验学习笔记
H3C firewall rbm+vrrp networking configuration
HCIA复习
浅谈专项测试之弱网络测试
Linux regularly backs up MySQL database
Network protocol model
【C语言】字符串左旋
[postman] collections - run the imported data file of the configuration
Title 1093: character reverse order
把el-tree选中的数组转换为数组对象
Configuring OSPF GR features for Huawei devices
What are the test sites for tunnel engineering?
10M25DCF484C8G(FPGA) AMY-6M-0002 BGA GPS模块
Web界面元素的测试
RestTemplate、Feign实现Token传递
Digital triangle model acwing 1015 Picking flowers
Accélération de la lecture vidéo de l'entreprise