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

发布时间：2022-10-21 17:50:31 浏览数：次

摘要：贪婪算法作为一种求最优解问题的方法，具有简便、迅捷的特点，然而贪婪算法因其基于局部求最优解的特点，决定了其在很大程度上无法得到问题的最优解。本文通过对[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

相关热词搜索：算法部件贪婪背包优化