algorithm - 汽油泵建立算法

Question

给定一个地点，用矩阵表示，每个条目表示该地区的汽车数量。我们的任务是在矩阵的一个入口处放置一个汽油泵，以便我们选择的 block 提供最小的旅行成本。

我找到了一个需要 O(n^4) 时间的解决方案，我们在其中计算每个条目的整个过程。

对于这个问题，你能告诉我其他好的方法吗？

Answer 1

我将通过一个实际示例来扩展 Rupert 的回答(即如何计算他所说的行和列的中位数)。

正如他所说，您可以分别找到泵的最佳行和最佳列。怎么办？

让我们考虑以下问题实例:

3 2 7
1 8 9 
7 2 2

• 首先，我们找到泵的最佳排

我们开始添加矩阵的所有行

3 2 7 -> 12
1 8 9 -> 18
7 2 2 -> 11

现在如果我们将泵放在第一行，总垂直成本是

11*2 + 18*1 + 12*0 = 30

由于第 3 行的 11 辆汽车必须行驶 2 个垂直单位，因此第 2 行的 18 辆汽车必须行驶 1 个垂直单位，而第 1 行的汽车不必垂直行驶。我们必须计算所有行的总垂直行程成本。

pump in 1st row -> cost 30 = 11*2 + 18*1 + 12*0
pump in 2nd row -> cost 23 = 11*1 + 18*0 + 12*1
pump in 3rd row -> cost 42 = 11*0 + 18*1 + 12*2

所以泵的最佳行是第二行。

我们在 O(n^2) 中进行了计算，因为我们在对 n 行中的所有 n 汽车求和时进行了 O(n^2) 求和，当我们计算泵的每个可能行的总垂直成本时，我们进行了 O(n^2) 次求和和乘法运算。

• 现在我们找到了泵的最佳色谱柱

我们对每一列中的汽车求和:

3  2  7
1  8  9 
7  2  2
_______
11 12 18

现在:

pump in 1st col -> cost 48 = 11*0 + 12*1 + 18*2
pump in 2nd col -> cost 29 = 11*1 + 12*0 + 18*1
pump in 3rd col -> cost 34 = 11*2 + 12*1 + 18*0

所以泵的最佳色谱柱是第二个。

在 O(n^2) 步中，我们发现我们必须将泵放在 [2][2] 中。