1

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

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

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

4

2 回答 2

4

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

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

因此，我们将问题简化为一维。为了弄清楚发生了什么，我不得不将其转换为一个连续的问题。因此，假设我有一个密度函数 p(x)，（假设它在紧凑的支持下是连续的，这样数学就可以工作了）。然后成本函数由下式给出

\int p(x) |x-x0|

将其分成两半以消除 mod 符号并进行区分（这是您需要假设 p(x) 表现良好的地方），您得到

\int_-\infty^x_0 p(x) - \int_{x_0}^\infty p(x)

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

对于原始问题的离散设置，相同的论点有效。基本上你可以取一个离散导数，即 E(k+1)-E(k)。如果您为位置 n 的汽车数量写 a[n]，则成本函数拆分为

E(k) = \sum_{n<k} a_n(kn) + \sum_{n>k} a_n(nk)

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

E(k+1)-E(k) = \sum_{n<k+1} a_n - \sum_{n>k+1} a_n

因此解决方案将再次处于中位数（如果您最终为半整数，则四舍五入）。要了解为什么这是正确的，请注意如果 k 是一个很大的负数，那么这个导数肯定是负数（因此将 k 增加 1 会降低成本）。现在，随着 k 的增加，导数慢慢增加。在某个时候，它会第一次变得积极。一旦 k+1 大于中位数，就会发生这种情况。之后，它将保持正数，因此要选择的正确 k 是小于或等于中位数的最大 k。

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

于 2012-08-25T18:16:38.420 回答
4

我将用一个实际的例子来扩展鲁珀特的答案（即如何计算他所说的中间行和列）。

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

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

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

所以泵的最佳行是第 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

所以泵的最佳柱是 2nd。

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

于 2012-08-25T19:36:27.987 回答