algorithm - 这个优化算法的正式名称？

Question

我在我的一个编码项目中遇到以下问题，我将在此处简化:

我正在网上订购杂货，想要非常具体数量的非常具体的东西。我想订购以下产品:

• 8 个苹果
• 1 山药
• 2汤
• 3 block 牛排
• 20 橙汁

有很多商店离我等距，我会从那里送餐。并非所有商店都有我需要的东西。 我想用最少的订单获得我需要的东西。例如，从下面的 #2 商店订购是一个浪费的订单，因为我可以通过从不同的商店订购以更少的订单完成我的商品. 解决此问题的优化算法的名称是什么？

商店 #1 供应

• 50 个苹果

商店 #2 供应

• 1 橙汁

• 2 block 牛排

• 1汤

商店 #3 供应

• 25汤

• 50 橙汁

商店 #4 供应

• 25 block 牛排

• 10 颗山药

在这种情况下，可能的最低阶数是 3。 1 号商店的 8 个苹果。 3 号商店的 2 份汤和 20 份橙汁。 4 号商店的 1 block 山药和 3 block 牛排。

Answer 1

对我来说，这很可能听起来像是 Integer Linear programming problem (ILP) 的限制情况，即它的 0-or-1 变体，其中整数变量被限制在集合 {0, 1} 中。这被称为 NP-hard(并且相应的决策问题是 NP-complete)。

问题表述如下(遵循引文中的约定):

Given the matrix A, the constraint vector b, and the weight vector c, find the vector x ∈ {0, 1}^N such that all the constraints A⋅x ≥ b are satisfied, and the cost c⋅x is minimal.

我翻转了约束不等式，但这相当于改变了 A 和 b 的符号.

不等式表示您对订单的满意度:您至少可以购买所访问商店中每件商品的数量。请注意，b 的长度与 A 中的行数以及 A 中的列数相同em>c 和 x。点积 c⋅x 自然是标量。

由于您正在最大限度地减少行程次数，因此每次行程的费用相同，因此 c = 1，并且 < strong>c⋅x 是总行程数。商店库存矩阵 A 每件商品一行，每家商店一列，b 是您的购物 list 。

当然，通过尝试 x 的所有可能的 2^N 值可以找到确切的最佳解决方案。

由于 NP-hard 问题没有单一的方法，请考虑问题的大小，以及您希望达到的最优值的接近程度。当“库存”很大时，贪婪的方法会很有效(当您下一个要访问的商店的商品总数最多时尚未满足)。如果您事先知道预期的最小行程数，则可以将搜索波束修剪为某个值，使行程数超过某个乘法系数。当您的搜索受到时间限制时，这是最好的方法(我经常进行束搜索，与文章中提到的分支切割方法密切相关，在占用几 GB 内存的图表中略快于 30 毫秒的限制光束宽达 10,000 的探索步骤)。如果搜索环境不太粗糙，模拟退火也有效。

还有 search on cs.SE ;对于此类问题，它可能是一个更好的地方。