用A*解无界背包

Question

我试图调和两个看似矛盾的观点：

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

听起来很疯狂对吧？我就是这么想的！

问题的变化是用一架货机描述的，它必须卸下一些货物，以便将其有效载荷降到飞机的容量。因此，有一组物品，每个项目都有一个重量和一个值，以及一个必须卸载的目标重量--优化货物的卸货方式，这样你至少可以卸下W重量，并将货物的总价值降到最低。考虑无界问题，其中任意有许多项目可用，每一个N种不同的类型。

所提出的解决方案使用一个从节点(顶点)开始的图形，表示没有卸载任何内容。每一次卸载操作都代表一条边，因此，随着每一种可能的货物组合卸载，图从起始点呈指数增长。目标节点是一个虚拟聚合，因为所有具有总权重>=的组合都被认为是目标节点。到目前为止，卸载的总权重被存储在每个节点中，用于确定目标是否已经到达。每个边的成本是正在卸载的项的值。因此，像Dijkstra或A*这样的最短路径算法将找到最优的商品集。

Dijkstra显然需要指数时间，因为它正在探索所有可能的组合。但是有了一个允许的启发式，我认为A*应该在多项式时间内运行。我认为下面的启发应该有效。对于每一种商品，都要计算“特定值”，即价值与重量之比。挑选比价值最高的好东西。作为对给定节点的启发式，计算仍然需要卸载的权重乘以最大值。这提供了一种估计，如果目标重量可以通过最优货物的整数数来实现，或者在所有其他情况下都低估了剩余的距离(重量)，因为实际的货物数量需要四舍五入。所以启发式是可接受的。

我还没有以任何严格的方式证明运行时的复杂性。但按照A*的工作方式，它会贪婪地向目标添加项目，快速地探索最佳方案，直觉地认为它应该在多项式时间内运行N，并且在适当允许的启发式条件下，解决方案保证是最优的。

那么这个解决方案有什么问题呢？我绝对不相信，我们已经找到了一个新的解决方案，一个研究过的问题，通过应用一个著名的算法。但这看起来应该管用。

Answer 1

这听起来像是背包的标准分支和绑定方法。当比率有变化时，它是好的，但当比率相同时，它会退化为指数时间的蛮力。