基于任务分配的剪枝算法优化体会

【关键词】任务分配 剪枝算法 匈牙利算法 体会

1 引言

随着科技的不断发展与进步，人们的生活节奏也在加快，低效率的工作不能够很好的适应现代社会发展，因此过去慢节奏的工作方式已经被新方法所取代。在我们的日常工作中，常会面临任务分配的问题，例如工作任务的分配；各小组之间的分配等，这样的问题通常会用有多项任务让多个人去完成，不同的人执行的效率不同得到的效果也不同，要确定出最合适的分配方案，才能让整个的任务得到圆满的完成，还能使整体任务付出的成本最小。其实这类的问题在很多领域中都可以见到，比如教育课程的分配、军事应用的武器分配、劳动生产分配问题等等，过去此类的问题常会利用匈牙利算法进行解决，但是随着匈牙利算法运算效率的降低，研究人员又提出了一种新的解决方法就是基于任务分配的剪枝算法，此算法提高了任务分配的速度与效率，本文就对匈牙利算法思想以及基于任务分配的剪枝算法进行具体的分析。

2 匈牙利算法及思想

匈牙利算法主要应用于指派问题上，比如车床加工问题，n个零件在m台车床上加工，每个零件的加工时间与成本不同，那么最佳的任务分配就是要让此任务的总成本最低。匈牙利算法在进行分配任务求解的时候，会对原代价矩阵进行多次的改变，让原代价矩阵变成有很多0元素的新代价矩阵，将矩阵C的所有元素划分为0和非0，得到不同行不同列的0元素最大数目与0元素最少的直线数相等。匈牙利算法在进行简化的过程中为了达到行列减少的目的，会对成本矩阵进行迭代并且多次对零元素进行寻找、选择与删除，这样一来使得逻辑变得复杂，运算效率也慢慢降低。因此重新分析任务分配问题的特点提出了一种新的快速优化算法――剪枝算法。

3 基于任务分配的剪枝优化算法的理论

3.1 剪枝算法相关理论

剪枝优化算法也称为快速降阶优化算法，其目的就是将矩阵快速降阶，实现操作简单化。剪枝算法定义1：，，显然，1与2分别为部分分配=1或=1的降价指派问题。1，2包含于。

剪枝算法定义2：

，为全局最优分配的目标函数值。

剪枝算法定义3：

。将确定好的部分分配方案的代价元素值设为0，C1与C2的计算为：

，这时C1的0元素不能再进行分配，E1求解无人机对对个目标的任务分配问题，将空间变小这就称为剪枝算法。如果代价值最大就是最佳的任务分配指标，那么选择=1就是最佳方案的解，将其对应的行与列去除，就成为降级了一阶的求解方案，按照以上方法进行，直到代价矩阵剩下一个元素，即整个任务分配得到最佳的解决方案。

3.2 剪枝算法具体步骤

根据本文的设计，剪枝优化算法使得付出代价最小的任务分配方法步骤为：

（1）初始化=1，i，j=1，2，3，4……，n。

（2）条件满足L=argmax（-）X k≠m；i，k，m=1，2，3……n的行号，然后选择=1，同时将标记成true，即为选中。

（3）剪枝算法，让然后将与之同行列的元素标记成false，这是进行剪枝算法的操作，这样的算法就会让代价矩阵的规模减少一阶。

（4）降低了一阶的代价矩阵中如果有没有进行标记的矩阵，就可以重复这些步骤，直到代价矩阵变为最低的1×1矩阵并且标记为true，任务分配问题得到解决。通过以上算法的分析不难看出，在利用剪枝算法进行求解矩阵分配问题的时候，要用循环进行（n-1）次操作得到解，本文的基于任务分配的剪枝算法经过分析使计算的逻辑性得到简化，是一种实现了逻辑简单，高效率的计算方法。

3.3 剪枝算法实例分析

对于比较常见的指派问题，如果各主体间的代价矩阵给出了数据，利用文中的剪枝优化算法，经过多次的剪枝就能得到最佳的任务分配方案，并且每一步的剪枝都能够得相应的解。需要说明：剪枝算法也有一定的缺陷，即它的适用范围只能用于求解代价矩阵的元素，并且其中元素不能出现负值。一旦代价矩阵中正负数都有时，让先找出最小的负数，然后将每一个代价元素增加相同的正数，这样就有效解决了代价矩阵中都为非负值的条件，最后就可以利用上文中的剪枝算法对问题进行求解，可以看出，相比于匈牙利算法，剪枝优化算法才是对矩阵元素增加正数却并不影响问题解决的最佳方式。

4 结束语

综上所述，本文开始对匈牙利算法与思想进行简要的分析，然后由匈牙利算法的低效率引申出一种更好解决任务分配问题的新算法，即剪枝优化算法，再对剪枝算法的定义与步骤进行详细的说明，得出剪枝算法是最佳的解决方法，它将求解的范围慢慢变小得出解答，有效的节省了运算时间，降低了负载率，也提高了计算机的利用率，相信未来基于任务分配的剪枝算法会得到更多的应用，获得更大的发展。

参考文献

[1]陆洋，施侃乐，雍俊海.细分法求解点投影问题时的剪枝算法[J].计算机辅助设计与图形学学报，2014（04）.

[2]熊焱，吴微，张超.基于灰色关联分析的高阶神经网络剪枝算法[J].大连理工大学学报，2010（03）.

[3]武彤，程辉.用遗传算法改进的BP神经网络剪枝算法来优化决策树模型[J].计算机科学，2013（z2）.