装箱中启发式算法与近似算法的区别
装箱中启发式算法与近似算法的区别
提问于 2018-05-14 05:35:27
我正在阅读一维垃圾箱包装问题，以及可以用来解决这个问题的不同解决方案。
垃圾箱包装问题定义:给定一个对象及其权重的列表，以及一个固定大小的垃圾箱集合，找出最小数量的回收箱，以便将所有的对象分配给一个桶。
我正在研究的解决方案:下一次拟合、第一次拟合、最佳拟合、最坏拟合、第一次拟合递减、最佳拟合递减
我注意到，我读过的一些文章称这些为“近似算法”，而另一些文章称之为“启发式”。我知道近似算法和启发式算法有区别：
启发式:对于一些困难的问题，很难在一个很好的运行时间内得到一个可接受的解决方案，所以我们可以通过使用一些有知识的猜测或任意选择来得到一个“好”的解决方案。
近似算法:这给出了一个近似解，对它的性能有一些“保证”(可能是一个比率，或者类似的)。
所以，我的问题是，这些解是我正在研究的启发式算法还是近似算法？我更倾向于相信它们是启发式的，因为我们选择了下一个被“猜测”放到垃圾桶里的物品。我们得不到最优解的保证。那么为什么有些人称它们为近似算法呢？
如果这些不是启发式算法，那么解决垃圾箱包装问题的启发式算法的例子是什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-05-14 06:05:41
一个算法既可以是启发式算法，也可以是近似算法--这两个术语不相冲突。如果某些“好但并非总是最优”的策略(启发式)被证明是“不太糟糕”(近似保证)，那么它可以两者兼而有之。
您列出的所有算法都是启发式的，因为它们规定了一种“通常很好”的策略，即启发式策略。对于任何有近似保证的算法(“错误”必须是有界的)，那么你也可以说它是一个近似算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50323625
复制相关文章
相似问题
腾讯云开发者
