algorithm - 用 A* 解决无界背包问题

Question

我试图调和两个​​看似矛盾的想法:

1. 已知无界背包优化问题是 NP-hard
2. 我和我的同事认为我们可以使用 A* 在多项式时间内解决它的微小变化

听起来很疯狂，对吧？这就是我的想法!

问题的变体描述为一架货机必须卸下部分 cargo 以将其有效载荷减少到飞机的容量。所以有一组元素，每个元素都有一个重量和一个值(value)，以及一个必须卸载的目标重量——优化要卸载的 cargo ，这样你至少有 W 重量被移除，并最小化 cargo 的总值(value)。考虑无限问题，其中有任意多件元素可用，每种元素都有 N 种不同的类型。

建议的解决方案使用一个图形，该图形从一个节点(顶点)开始表示没有卸载。每个卸载操作都代表一条边，因此随着卸载 cargo 的每种可能组合，图形从起点呈指数增长。目标节点是一个虚拟聚合，因为所有总权重 >= 目标的组合都被视为目标节点。到目前为止卸载的总重量存储在每个节点中，用于确定是否已达到目标。每条边的成本是卸载元素的值(value)。因此，Dijkstra 或 A* 等最短路径算法将找到最佳商品集。

Dijkstra 显然需要指数时间，因为它正在探索所有可能的组合。但是有了可接受的启发式算法，我认为 A* 应该在多项式时间内运行。我认为以下启发式方法应该有效。对于每种商品，计算“特定值”，即值与重量的比率。选择具有最高特定值的商品。作为给定节点的试探法，计算仍然需要卸载的重量乘以最大特定值。这提供了一个估计，在目标重量可以通过整数数量的最佳商品实现的情况下是完全正确的，或者在所有其他情况下低估了剩余的距离(重量)，因为实际的商品数量需要四舍五入向上。所以启发式是可以接受的。

我还没有以任何严格的方式证明运行时的复杂性。但是 A* 的工作方式，它会贪婪地向目标添加项目，快速探索最佳选项，直觉上感觉它应该在 N 的多项式时间内运行。并且通过适当可接受的启发式，解决方案可以保证是最优的。

那么这个解决方案有什么问题呢？我绝对不相信我们已经通过应用众所周知的算法找到了一个经过充分研究的问题的新颖解决方案。但这似乎应该有效。

Answer 1

这听起来像是背包的标准分支定界法。当比率有变化时这很好，但当比率相同时就变成了指数时间的蛮力。