当前位置:网站首页>在线问题与离线问题
在线问题与离线问题
2022-07-06 05:58:00 【瞻邈】
1. 在线问题
决策时未掌握全部实例信息,已做的决策在更多信息呈现后不可更改。
2. 离线问题
实例在决策前全部已知的问题。
3. 在线算法
可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果。例如,选择排序在排序前就需要知道所有待排序元素,然而插入排序就不必。
因为在线算法并不知道整个的输入,所以它被迫做出的选择最后可能会被证明不是最优的,对在线算法的研究主要集中在当前环境下怎么做出选择。对相同问题的在线算法和离线算法的对比分析形成了以上观点。如果想从其他角度了解在线算法可以看一下 流算法(关注精确呈现过去的输入所使用的内存的量),动态算法(关注维护一个在线输入的结果所需要的时间复杂度)和在线机器学习。
一个很好的展示在线算法概念的例子是加拿大旅行者问题,这个问题的目标是在一个有权图中以最小的代价到达一个目标节点,但这个有权图中有些边是不可靠的,可能已经被剔除。然而一个旅行者只有到某个边的一个端点时才能确定该边是否已经被移除了。最坏情况下,该问题会变得简单,即所有的不确定的边都被移除该问题将会变成通常的最短路径问题。
4. 离线算法
离线算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果,通常将这类具有问题完全信息前提下设计出的算法成为离线算法。
参考文献
边栏推荐
猜你喜欢
Gtest之TEST宏的用法
Is it difficult for an information system project manager?
如何在业务代码中使用 ThinkPHP5.1 封装的容器内反射方法
[Jiudu OJ 07] folding basket
H3C V7 switch configuration IRF
Migrate Infones to stm32
High quality coding tool clion
Station B, Master Liu Er - dataset and data loading
H3C V7版本交换机配置IRF
Wib3.0 leapfrogging, in leapfrogging (ง • ̀_•́) ง
随机推荐
Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method
关于 PHP 启动 MongoDb 找不到指定模块问题
Query the standard text code corresponding to a work center (s) in the production order
Detailed explanation of BF and KMP
H3C防火墙RBM+VRRP 组网配置
Station B Liu Erden - linear regression and gradient descent
GTSAM中李群的运用
[SQL Server fast track] - authentication and establishment and management of user accounts
Station B Liu Erden linear regression pytoch
Mysql database master-slave cluster construction
Analysis report on development trends and investment planning of China's methanol industry from 2022 to 2028
HCIA复习
P2802 go home
实践分享:如何安全快速地从 Centos迁移到openEuler
Sqlmap tutorial (III) practical skills II
假设检验学习笔记
Auto. JS learning notes 17: basic listening events and UI simple click event operations
Winter 2021 pat class B problem solution (C language)
[C language syntax] the difference between typedef struct and struct
C language bubble sort