递归思想在指派问题中的运用.pdfVIP

研究与开发 递归思想在指派问题中的运用 周志辉 ， 刘建生 江西理工大学理学院 江西 （ ， 341000 ） 摘 要 提出将矩阵进一步缩小的方法来求指派问题的解 用匈牙利解法求指派问题的解 然 ： ， ， 后用递归思想求解指派问题 并对两种方法的优缺点进行比较 通过对比可以知道 两 ， 。 ， 种方法所得的结果是一样的 匈牙利算法的优点是算法时间复杂度较小 缺点是解题 。 ， 过程比较复杂 递归思想的优点是解题过程比较简单 缺点是算法时间复杂度较大 。 ， 。 关键词 指派问题 匈牙利算法 递归思想 最小值 ： ； ； ； 0 引 言 间最少？ 表 1 工作中常遇到这样的问题 有若干项任务需要 ： 完成 又有若干对象 指人或设备等 可承担这些任 ， （ ） 务 每个对象都能完成其中的每一项任务 只是由于 ， ， 每个对象的特点与专长不同 各对象完成各项任务 ， 所需的时间 费用或所产生的效益各不相同 又因任 ， ； 我们先用匈牙利解法解上面的问题 就得到了 务性质的要求和管理上的需要等原因 每项任务只 ， ， 最优解 相应解矩阵为 能由一个对象来完成 每个对象也只能承担其中的