就背包和部件加工问题浅论贪婪算法的运用及优化方案

开篇：润墨网以专业的文秘视角，为您筛选了一篇就背包和部件加工问题浅论贪婪算法的运用及优化方案范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：贪婪算法作为一种求最优解问题的方法，具有简便、迅捷的特点，然而贪婪算法因其基于局部求最优解的特点，决定了其在很大程度上无法得到问题的最优解。本文通过对[0-1背包问题]以及部件加工问题的分析，阐述了贪婪算法的应用以及贪婪算法存在的局限性，进而引出贪婪算法的优化方案――k阶优化方法，进一步对求最优解问题进行完善和归纳。

关键词：贪婪算法；最优解0-1背包问题；部件加工问题；k阶优化方法

中图分类号：TP301.6

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。

贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪婪选择，每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，通过每一步贪婪选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

贪婪算法可解决的问题通常大部分都有如下的特性：（1）有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币；（2）随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象；（3）有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优；（4）还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性；（5）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解；（6）最后，目标函数给出解的值。

1 问题回放与拓展

1.1 部件加工问题

（1）问题论述

（2）问题分析

本题求一个加工顺序使得加工总时间最短，要使时间最短，则就是让机器的空闲时间最短。一旦a工序开始加工，则a工序将会不停的进行作业，关键是b工序在加工过程中，要等待a工序。很明显第一个部件在a工序上加工时，b工序必须等待，最后一个部件在b工序上加工，a工序也在等待b工序的完工。

（1）方案原理

2.2 k阶优化方案总结

参考文献：

[1]苏德富，钟诚.计算机算法设计与分析[M].北京：电子工业出版社，2001.

[2]邓宏涛，朱峋.0/1背包问题的贪心优化解法[J].计算机与数字工程，2006.

[3]谭浩强C程序设计（第四版）[M].北京：清华大学出版社，2010.

作者简介：冯光毅（1991-），男，浙江宁波人，本科在读。

作者单位：浙江工商大学 信息与电子工程学院，杭州 310000