加油泵建立算法

Question

有一个给定的位置，它由一个矩阵表示，每个条目都表示该区域中的汽车数量。我们的任务是把一个加油泵放在矩阵的一个条目上，这样我们选择的块就可以给出最小的旅行成本。

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

你能告诉我解决这个问题的其他好方法吗？

Answer 1

我将用一个实际的例子来扩展Rupert的答案(即如何计算他所谓的中位数行和列)。

正如他所说的，你可以找到泵的最优行和最优列，分别为。多么?

让我们考虑这个问题的以下实例：

3 2 7
1 8 9 
7 2 2

• First，我们找到pump

的最优行

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

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)求和和乘法。

• Now我们为pump

找到最优的列

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

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。

Answer 2

如果我没有理解错你的问题，那么你的成本函数就像Haile在他/她的评论中描述的那样，有一个简单的解决方案，因为你可以简化为一个一维的问题。

请注意，在曼哈顿度量中，汽车必须穿越的列距离仅与行距离相加，因此我们可以分别最小化它们。

因此，我们将问题简化到一维。为了弄清楚发生了什么，我不得不把这个问题转换成一个连续的问题。假设我有一个密度函数，p(x)，(假设它是紧支集连续的，所以数学是有效的)。则成本函数由下式给出

​

​

将其一分为二以去掉mod符号并进行微分(这是您需要假设p(x)表现良好的地方)，您将得到

​

​

现在，x0的最佳位置是使导数为零的位置。但请注意，这是分布的中位数。

对于离散设置，这是最初的问题，同样的论点也是有效的。基本上你可以取一个离散的导数，它是E(k+1)-E(k)。如果您为位置n处的汽车数量编写一个，则成本函数将拆分为

​

​

假设我没有犯一个愚蠢的错误，离散导数的结果是

​

​

因此，解决方案将再次位于中位数(如果最终为半整数，则以任意一种方式四舍五入)。要了解为什么这是真的，请注意，如果k是一个很大的负数，那么这个导数肯定是负的(因此，将k增加1将降低成本)。现在，随着k的增加，导数慢慢增加。在某种程度上，它将第一次成为正数。只要k+1大于中位数，就会发生这种情况。在此之后，它将保持为正，因此要选择的正确k是小于或等于中位数的最大k。

最初的问题是二维的，所以您需要运行两次，每个轴一次。