装箱中启发式算法和近似算法的区别
Difference Between Heuristic and Approximation Algorithm in Bin Packing
我正在阅读一维装箱问题以及可用于解决该问题的不同解决方案。
装箱问题定义：给定一个对象列表及其重量，以及一组固定大小的箱子，找到最小数量的箱子，以便将所有对象分配到一个箱子。
我正在研究的解决方案：次拟合、首次拟合、最佳拟合、最差拟合、首次拟合递减、最佳拟合递减
我注意到我读过的一些文章称它们为 "approximation algorithms"，而其他文章称它们为 "heuristics"。我知道近似算法和启发式算法之间存在差异：
启发式：对于一些难题，很难在适当的 运行 时间内得到可接受的解决方案，因此我们可以通过应用一些有根据的猜测或任意选择来获得 "okay" 解决方案。
近似算法：这给出了一个近似解，"guarantee"它的性能（可能是比率，或类似的东西）
所以，我的问题是我正在研究的这些解决方案是启发式算法还是近似算法？我更倾向于相信它们是启发式的，因为我们正在选择下一个要由某些 "guess" 放入垃圾箱的项目。我们不能保证有最佳解决方案。那么为什么有人称它们为近似算法呢？
如果这些不是启发式算法，那么解决装箱问题的启发式算法示例有哪些？
一个算法既可以是启发式算法，也可以是近似算法——这两个术语并不冲突。如果某些 "good but not always optimal" 策略（启发式）可以被证明是 "not too bad"（近似保证），那么它就符合两者的条件。
您列出的所有算法都是启发式的，因为它们规定了一个 "usually good" 策略，这就是启发式。对于任何有近似保证的算法（"error" 必须以某种方式有界），那么你也可以说它是一个近似算法。
我正在阅读一维装箱问题以及可用于解决该问题的不同解决方案。
装箱问题定义：给定一个对象列表及其重量，以及一组固定大小的箱子，找到最小数量的箱子，以便将所有对象分配到一个箱子。
我正在研究的解决方案：次拟合、首次拟合、最佳拟合、最差拟合、首次拟合递减、最佳拟合递减
我注意到我读过的一些文章称它们为 "approximation algorithms"，而其他文章称它们为 "heuristics"。我知道近似算法和启发式算法之间存在差异：
启发式：对于一些难题，很难在适当的 运行 时间内得到可接受的解决方案，因此我们可以通过应用一些有根据的猜测或任意选择来获得 "okay" 解决方案。
近似算法：这给出了一个近似解，"guarantee"它的性能（可能是比率，或类似的东西）
所以，我的问题是我正在研究的这些解决方案是启发式算法还是近似算法？我更倾向于相信它们是启发式的，因为我们正在选择下一个要由某些 "guess" 放入垃圾箱的项目。我们不能保证有最佳解决方案。那么为什么有人称它们为近似算法呢？
如果这些不是启发式算法，那么解决装箱问题的启发式算法示例有哪些？
一个算法既可以是启发式算法，也可以是近似算法——这两个术语并不冲突。如果某些 "good but not always optimal" 策略（启发式）可以被证明是 "not too bad"（近似保证），那么它就符合两者的条件。
您列出的所有算法都是启发式的，因为它们规定了一个 "usually good" 策略，这就是启发式。对于任何有近似保证的算法（"error" 必须以某种方式有界），那么你也可以说它是一个近似算法。