马阔

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

1 引言

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

2 匈牙利算法及思想

匈牙利算法主要应用于指派问题上，比如车床加工问题，n个零件在m台车床上加工，每个零件的加工时间与成本不同，那么最佳的任务分配就是要让此任务的总成本最低。匈牙利算法在进行分配任务求解的时候，会对原代价矩阵进行多次的改变，让原代价矩阵变成有很多0元素的新代价矩阵，将矩阵C的所有元素划分为0和非0，得到不同行不同列的0元素最大数目与0元素最少的直线数相等。……