-
2015-11-17 14:07:45TODO List based 算法、任务分解、分治法
就是围绕一个TODO list,不断取出并处理其中的work item。处理work item的时候,一般先做一些工作,然后可能会产生新的子work item追加到todo list,类似一个大任务分解成若干小任务。
class ToList { public: void append(WorkItem wi); WorkItem fetch(); }
注意这个todo list最自然的就是一个队列,实际上只要是支持添加(push)和取出(pop)的容器都可以,queue, stack, priority_queue, random_queue都行,取决于这些子任务之间是否独立,是否有顺序上的要求。
经典例子:
1快排
todo list中的work item定义为对数组的一段[a, b]进行快排
一开始todo list只有一个任务: 快排整个数组[0, A.size() - 1],每个快排任务的处理是:
1)以第一个元素为轴进行partition
2)添加两个子快排任务到工作列表
int partition(vector<int> &A, int l, int r) { int i = l; for (int j = l + 1; j <= r; ++j) if (A[j] < A[l]) swap(A[++i], A[j]); swap(A[l], A[i]); return i; } void quick_sort(vector<int> &A) { if (A.empty()) return; queue<pair<int, int>> q; for (q.push(make_pair(0, A.size() - 1)); !q.empty(); q.pop()) { int l = q.front().first, r = q.front().second; int p = partition(A, l, r); if (p - 1 > l) q.push(make_pair(l, p - 1)); if (p + 1 < r) q.push(make_pair(p + 1, r)); } }
2bfs
任务定义:以s为起点进行遍历
任务处理:先打印s的数据。 然后针对s的每个邻居,(如果没被访问过),产生一个新bfs任务追加到todo list。
3进一步,todo list里的任务可以是多种任务,而且之间可以满足一定顺序,通过选用不同的容器。
经典的后序遍历问题,可以用todo list 任务列表算法很自然的表达:
def postorderTraversal(self, root): result, todo_list = [], [(root, 1)] if root is None: return result while len(todo_list) > 0: node, taskType = todo_list.pop() if taskType == 1: # 1 for traverse job todo_list.append((node, 0)) # 0 for basic print job if node.right is not None: todo_list.append((node.right, 1)) if node.left is not None: todo_list.append((node.left, 1)) else: result.append(node.val) return result
定义2种类型的task,1) print task:打印该节点值
2) traverse task:遍历以该节点为根的树
对于第一种task的处理就是直接打印,对于第二种task,产生生成三个子task, 1个print task, 2个 traverse task,并注意task加入顺序,根, 右, 左
一开始工作列表里只有一个任务:后序遍历以root为跟的树,然后不断衍生子任务。。。
4 merge Sort
def mergeSort(A): todo_list, aux = [(0, len(A) - 1, 0)], [0] * len(A) while len(todo_list) > 0: l, r, type = todo_list.pop() if type == 0: # mergeSort task: compound task if l < r: todo_list.append((l, r, 1)) # merge task todo_list.append((l, l + (r - l) / 2, 0)) # sort task todo_list.append((l + (r - l) / 2 + 1, r, 0)) # sort task else: # merge task: simple task i, j, k = l, l + (r - l) / 2 + 1, l while i <= l + (r - 1) / 2 and j <= r: if A[i] < A[j]: aux[k] = A[i] i += 1 else: aux[k] = A[j] j += 1 k += 1 while i <= l: aux[k] = A[i] k, i = k + 1, i + 1 while j <= r: aux[k] = A[j] k, j = k + 1, j + 1 for k in xrange(l, r + 1): A[k] = aux[k]
5全排列:
两种task:1)全排任务。2)swap 任务
def permute(A): todoList = [(0, 0, len(A) - 1)] while len(todoList) > 0: taskType, l, r = todoList.pop() if taskType == 0 and l == r: print A elif taskType == 0: for i in xrange(r, l - 1, -1): todoList.append((1, l, i)) todoList.append((0, l + 1, r)) todoList.append((1, l, i)) else: A[l], A[r] = A[r], A[l]
总结:
2种任务,终端任务和复合任务,终端任务是可以直接做的任务,复合任务是由一系列其他任务序列组成。在快排和BFS的例子中,并没有定义终端任务,因为终端任务处在任务序列前面(或者顺序无关)可以先做,不用放到todo list。而后序遍历和merge sort的例子中,终端任务不能先做,所以先压到箱底。
更多相关内容 -
云计算中任务分解算法的改进
2021-04-16 17:36:28针对云计算中任务分解算法在解决复杂任务分解问题时容易陷入分解粒度过大及局部最优的缺陷,提出了一种树形分解问题思想与启发式策略相结合的任务分解算法(Improve Heuristic Algorithm,IHA)。该算法首先对任务... -
HTN规划中面向多计划生成的顺序任务分解算法
2013-05-08 11:02:11文中提出了一种能够快速生成多个可行计划的回溯算法. 该算法采用分段回溯的计划生成机制,充分利用了求解过程中生成的局部解序列从而能够一次性地快速生成多个可行计划,为寻求优化的计划和进行计划的评估提供更为有效... -
一种基于任务分解的时间均衡调度算法 (2013年)
2021-04-23 19:46:52针对计算网格中的任务放牧调度这类问题,提出了一种基于任务分解的时间均衡调度算法。该算法在调度过程中充分考虑了网格资源的特点,采用重复调度和任务分解策略,并进行了仿真实验。在任务完成时间和系统吞吐率两... -
一种基于滤波的分布式任务分配算法
2021-01-29 16:20:39打破了HIPC对局部场景感知的完美假设,使得新算法可以在局部感知不可靠条件下良好运行,该算法可以异步进行并行任务分配和冲突分解。通过试验得出相比于HIPC,新算法减少了任务冲突次数,缩短任务执行时间。 -
Java 正整数分解质因数算法示例.rar
2019-07-10 11:41:14Java实现正整数分解质因数的例子。如果数学好,相信这个代码不会难。在本例子中,输入90,打印出90=2*3*3*5。解题思路和方法:对n分解质因数,需要先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰... -
一种面向移动云计算的多目标任务卸载算法
2021-01-20 06:04:03提出了基于分解的多目标进化算法(MOEA/D)来同时优化应用 FT 和 EC,并将动态电压频率调整技术引入MOEA/D中,在不增加应用FT的前提下,调节移动设备的CPU时钟频率以进一步降低移动设备的EC。仿真结果表明,与多个... -
用贪心算法方法解最优分解问题和非单位时间任务安排问题
2018-05-30 00:02:20用贪心算法方法解最优分解问题和非单位时间任务安排问题 -
深层转导式非负矩阵分解并行算法
2021-07-06 22:47:11针对语音分离预训练及分离过程的计算问题,文中提出深层转导式非负矩阵分解并行算法,综合考虑迭代更新过程的数据关联性,设计了一种任务间和任务内多级并行算法。该并行算法在任务级将分解训练语音得到对应基矩阵的... -
机群系统中矩阵的并行QR分解算法 (2007年)
2021-05-12 01:09:26随着高速网络技术的快速发展,机群系统已经成为并行...基于这一点,本文对矩阵的QR分解提出了一种新的任务划分策略,并由此得到了它的一种粗粒度并行算法。实验结果表明,设计的并行算法在机群系统中具有较高的加速比。 -
一种分块并行Cholesky分解动态调度算法
2020-05-25 05:10:55为解决分块并行Cholesky分解过程中各处理器间的负载平衡问题,分析了算法的下三角矩阵特性以及各轮...研究结果表明:在矩阵块数不是非常大的情况下,该算法在时间性能上比传统的分块并行Cholesky分解算法具有明显的优势. -
论文研究-基于时序模型和矩阵分解的推荐算法.pdf
2019-07-22 20:07:03实验结果表明,所提出的算法与已有的推荐算法相比,在均方根误差(root mean square error,RMSE)和平均准确率(mean average precision,MAP)两个指标上均有较好表现,且适用于大规模数据的推荐任务。 -
Benders分解(Benders Decomposition)算法:算法原理+具体算例
2021-09-12 10:49:24 -
多品种供应的多供应商选择模型及分解算法 (2005年)
2021-05-18 01:51:49为解决求解的困难,采用变换分解算法,将原模型转换为整数规划问题。根据不同迭代方式,给出了2种基本运算步骤。在算例中运用模型和算法,得到了多物资供应环境下多供应商的最优任务分派。新方法克服了常规供应商的... -
基于偏置度量分解与隐反馈的协同过滤推荐算法
2021-04-30 14:31:15矩阵分解由于其简单可靠的特性,是推荐系统中最重要的算法之一,由于内积无法完全捕捉用户和商品间的交互,矩阵分解的性能难以继续提升。为了解决这个问题,改进了基础的距离度量分解模型,提出了基于偏置度量分解与... -
Submanifold Decomposition:一种新颖的子流形分解算法,它同时考虑两个流形-matlab开发
2021-05-30 12:07:37通过光谱分析从高维空间提取低维结构在机器学习和计算机视觉领域已经很普遍。 许多现有的流形学习方法都假定存在一个主要的... 人工数据和真实数据的比较实验表明,所提出的方法在识别任务中优于最先进的流形学习算法。 -
基于μC/OS任务调度算法的嵌入式数据管理
2020-08-13 07:47:20本文利用μC/OS嵌入式操作系统的任务调度 算法并加以改进,巧妙地实现了简易的嵌入式数据管理,与传统方法比较,该方法具备不出现存储空间碎片、数据管理操作效率高等优点,可广泛应用于低端嵌入式应用中的数据管理... -
夜光精讲 Opentcs 三大算法(九)任务分配算法
2019-05-20 11:40:06夜光分析可知,任务优先级顺序为:充电任务(电量低于criticallevel时)>充电任务(电量低于good level时)>订单任务>充电任务(电量高于good level时)>停靠任务。 因此停靠...夜光序言:
死亡是活过的生命,生活是在路上的死亡。
正文:
任务优先级
夜光分析可知,任务优先级顺序为:充电任务(电量低于criticallevel时)>充电任务(电量低于good level时)>订单任务>充电任务(电量高于good level时)>停靠任务。因此停靠任务的优先级最低,且可以删除回退该任务。
子任务的生成
由仓库运作模式可知,典型电商仓库中的任务可以分为三个阶段的子任务:
阶段①状态:小车在去往抬取货架的途中
阶段②状态:小车处于运载货架至分炼台/补货台的途中
阶段⑤状态:小车处于送货架回存储区的途中
三个状态对应的是轨迹为:
阶段①轨迹:小车从当前所在点curPoint运行至货架所在货位ShelfPointStation
阶段②轨迹:小车从ShelfPoinstation处运载货架至操作台endPoin station
阶段③轨迹:小车将货架从操作台endPoin stati o n送回至存储区为此,我们可以将一个任务拆分成多段任务,方便和后续任务进行整合,提高任务分配和执行效率。毎次执行阶段③子任务前,进行判定是否需要将货架进行移库或者该货架同时被其他操作台所需,此时阶段③任务应推后执行。
子任务中增加operation字段
为子任务中增加operation字段,可以指导小车该进行什么操作,完成相关操作后发送确认完成指令。当小车完成一个工单的时候,在任务表中查询是否有该小车需要执行其它的任务,有则调用dispatch_order()分解任务,让小车执行。
特殊情况的任务
针对特殊情况要进行相应的处理和决策,确保系统柔性地执行任务功能,允许AGV在运行过程中动态地变更运输任务。
1.查询订单货物所在货架的状态
(1)查询巧单,检测货架是否在运输过程中,调用另一个函数接口,根据状态向小车发送不同指令:
a.小车如果取货架过程中或送货架至分炼台过程中,给小车发送一个送到货之后就完成任务的请求(结束当前任务并开始新的任务,如果没有对应货架的任务就原路返回);
b.小车送回货架途中,就停止操作(带货架停止操作),并调用dispatch_order()函数计算路径,分派特殊的新任务给此车)并返回对小车的操作状态。同时在任务里面加上新任务的ID,任务的起始和终止点也需要变更下,小车完成当前订单后,去数据库查询有没有新的任务的I D。
C.货架不在运输过程中调用函数Task_list*d i spatch_order(Order*transOrder,Vehicle_list*carall)。后台程序要将任务列表插入到数据库表。
-
论文研究-任务分解控制及人员柔性的车间集成调度.pdf
2019-09-07 15:47:05在对复杂制造任务特点进行分析的基础上,建立了任务分解粒度控制模型和考虑人员柔性的制造单元资源模型,利用自适应非支配排序遗传算法进行求解,得到了较为满意的任务分解和车间资源调度方案。 -
论文研究-基于SVD分解的二维多任务压缩感知off-grid算法 .pdf
2019-08-26 02:13:42基于SVD分解的二维多任务压缩感知off-grid算法,廖艳苹,付畅,在阵列信号处理领域中,波达方向(DOA)估计作为关键技术已被广泛研究多年。考虑到二维DOA估计的现实意义,如为基站提供准确无盲区 -
基于μC/OS任务调度算法的嵌入式数据管理[图]
2020-10-22 06:06:08本文利用μC/OS嵌入式操作系统的任务调度 算法并加以改进,巧妙地实现了简易的嵌入式数据管理,与传统方法比较,该方法具备不出现存储空间碎片、数据管理操作效率高等优点,可广泛应用于低端嵌入式应用中的数据管理... -
(六)任务分解法(WBS)
2017-05-07 22:36:26Work Breakdown Structure如何进行WBS的分解:1、WBS分解的原则:将主体目标逐步细化分解,最底层的任务活动可直接分派到个人去完成,每个任务原则上要求分解到不能再分解为止,**牧牛遛马**理解为类似mysql数据库中...Work Breakdown Structure
如何进行WBS的分解:
1、WBS分解的原则:
将主体目标逐步细化分解,最底层的任务活动可直接分派到个人去完成,每个任务原则上要求分解到不能再分解为止,**牧牛遛马**理解为类似mysql数据库中的第一大范式(原子性)
2、WBS分解的方法:
至上而下与从下到上的一对一的沟通,一对一的个别交流,小组讨论
3、WBS的分解标准:
分解后的活动结构清晰 逻辑上形成一个大的活动 集合了所有的关键因素包含临时的里程碑和监控点 所有活动全部定义清楚
WBS的意义在于:
学会分解任务,只有将任务分解的足够细,我们才能心里有数,才能有条不紊的工作,才能统筹安排我们的时间表。3
-
一种基于旋转矩阵分解的视觉伺服控制算法
2021-02-20 21:47:20针对传统视觉伺服控制算法易使目标物品脱离摄像机视野而致伺服失败的缺点,从表征当前摄像机坐标系与期望摄像机坐标系姿态关系的旋转矩阵中分解出了等效转轴和等效转角,利用它们构造了一种可以有效控制摄像机朝向的... -
基于低秩正则化异构张量分解的子空间聚类算法
2021-01-27 05:51:25本文提出了一种基于低秩正则化的异构张量分解(LRRHTD)算法,并用于子空间聚类任务。低秩正则化的异构张量分解核心思想是对原始张量寻求一组正交因子矩阵的集合,将高维张量映射到低维的潜在子空间中,同时在最后的... -
快速降阶匈牙利算法的云计算任务分配模型 (2014年)
2021-05-16 00:19:25并可根据成本矩阵规模将矩阵分解成多个矩阵,使得该算法在任务和计算机不对等的情况下同样适用.论文最后的仿真结果表明,快速降阶匈牙利算法计算耗时远远小于匈牙利算法,并能有效提高计算机的利用率. -
并行测试系统的任务分解和任务过程模型
2009-05-27 10:39:54提出测试任务分解的原则和方法,对分解后的子任务构造任务相关图,并通过任务过程模型算法把任务相关图转化为 基于Petri网的并行测试任务过程模型,挖掘子任务间的并行性,从而为测试系统并行任务调度提供依据。 ... -
任务分解控制及人员柔性的车间集成调度 (2015年)
2021-05-30 02:40:54在对复杂制造任务特点进行分析的基础上,建立了任务分解粒度控制模型和考虑人员柔性的制造单元资源模型,利用自适应非支配排序遗传算法进行求解,得到了较为满意的任务分解和车间资源调度方案。 -
对等网络环境中基于功能划分的任务分解与调度方法 (2012年)
2021-04-27 03:04:17将P2P(Peer-to-Peer)网络节点上下文引入工作流管理,建立了一种基于工作流有穷状态自动机的任务分解方法;在定义节点处理能力评价指数的基础上,通过对蚁群算法的优化改进,建立了一种蚁群任务调度算法。实验结果表明,... -
论文研究-一种基于学习自动机的推荐算法改进.pdf
2019-07-22 19:37:27该算法充分利用连续型学习自动机在随机和高噪声环境中优化参数的卓越性能,代替原有的梯度下降算法进行大型稀疏矩阵的奇异值分解计算,使得重构矩阵与原矩阵之间的误差进一步降低,提高了后续预测算法的精确度。... -
基于多任务学习的深层人脸识别算法
2021-01-26 18:33:41然后,利用深层卷积神经网络提取对齐后的人脸图像特征,同时使用聚合判别多任务学习算法将提取的人脸特征向量分解为学习类内特征的向量和判别类间身份的向量,加强对类内特征的约束,提高类间特征可分离性;最终分别采用...