女人应该以哪种顺序将猫带回来以减少时间？

Question

一个女人看着她的猫在不同的方向上以不同的速度一个接一个地离开.她带着一个额外的座位坐了一辆摩托车跟着猫,一次捡起一只猫,带回家.每只猫以恒定的个体速度Vi移动并在时间Ti离开家.女人应该以哪种顺序将猫带回来以减少时间？

我试图解决这个问题,但不知道如何开始.

Answer 1

概括：

根据度量 v / x 以降序对猫进行排序，其中 v 是猫的恒定速度，x 是猫在时间 t = 0 时的初始位移。如何打破平局并不重要。一旦顺序初步建立，只要遵循它，它仍然是最有效的获取猫的顺序；所以遵循它。

候选人被揭穿：

在这两种情况下，允许摩托车速度为 w = 20。

1. 建议您按照从最快到最慢的顺序来养猫。反例：目录#1 (x, v) = (1, 9) 和目录#2 (x, v) = (100, 10)。

2. 建议您按照从最近到最远的顺序来养猫。反例：目录#1 (x, v) = (1, 1) 和目录#2 (x, v) = (2, 100)。

详细推导：

令 c(k) 指女士捡起的第 k 只猫，v(k) 指那只猫的速度，x(k) 指猫的初始位移（在时间 t = 0 时，我们将其设置为女士最初启动摩托车是为了追赶第一只猫）。

获得第一只猫所需的总时间是：

t(1) = 2 * x(1) / (w - v(1))

其中w是摩托车的恒定速度。由于这个表达式很重要，我们可以激励它的每个部分：

1. 2 *来自这样的事实：女士必须抓住猫，然后花同样的时间把猫送回家；
2. x(1) / (w - v(1))是到达猫的时间，即x(1)通过w - v(1)比猫更快的速度来缩短距离v(1)。

获得前两只猫的时间是：

t(2) = t(1) + 2 * (x(2) + v(2)t(1)) / (w - v(2))

也就是说，所花费的时间等于获得第一只猫的时间加上获得第二只猫的时间。额外的v(2)t(1)术语说明了这样一个事实：当女士得到第一只猫时，第二只猫移动了；否则，这部分是相同的。

重新整理这个表达式，我们得到：

t(2) = t(1)(1 + 2 * v(2) / (w - v(2)))  + 2 * x(2) / (w - v(2))

我们定义以下衍生术语：

T(k) = 2 * x(k) / (w - v(k))
s(k) = 2 * v(k) / (w - v(k)) + 1

现在我们重写：

t(1) = T(1)
t(2) = s(2)T(1) + T(2)

并继续

t(1) = T(1)
t(2) = s(2)T(1) + T(2)
t(3) = s(3)s(2)t(1) + s(3)T(2) + T(3)
...
t(n) = s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n)

最后一个表达式为我们提供了获取所有n猫的总时间：

s(n)...s(2)T(1) + s(n)...s(3)T(2) + ... + T(n)

现在我们假设我们有一个最佳解决方案，即以尽可能最有效的顺序拾取猫。为了导出这个假设的最优解的有用属性，我们可以使用假设的最优性来推断交换猫会产生一个并不更好的解决方案。想象一下交换猫j和j+1：

... + s(n)...s(j+1)T(j) + s(n)...s(j+2)T(j+1) + ...
<= ... + s(n)...s(j)T(j+1) + s(n)...s(j+2)T(j) + ...

T(k)涉及for 的项k < j同时具有s(j)和 ，s(j+1)并且根据乘法的交换律，它们不受交换的影响。T(k)涉及for 的条款k > j + 1既没有也s(j)没有s(j+1)，因此不会受到交换的影响。T(k)只有这样的条款j <= k <= j + 1才会受到交换的影响，因此我们可以删除类似的条款：

s(n)...s(j+2)s(j+1)T(j) + s(n)...s(j+2)T(j+1)
<= s(n)...s(j+2)s(j)T(j+1) + s(n)...s(j+2)T(j)

部分积s(n)...s(j+2)对于所有剩余项都是公共的，并且必须是正数，因此我们可以通过除以不等式两边来删除这个类似的项：

s(j+1)T(j) + T(j+1) <= s(j)T(j+1) + T(j)

重新排列如下：

(s(j+1) - 1)T(j) <= (s(j) - 1)T(j+1)

最后：

(s(j+1) - 1) / T(j+1) <= (s(j) - 1) / T(j)

回顾一下我们对s(k)和的定义T(k)，将其简化为v和x：

v(j+1) / x(j+1) <= v(j) / x(j)

也就是说：如果我们有一个最优解，那么猫的速度与初始位移的比值一定是按降序排列的。这是一个必要条件，但也许不是充分条件。

请注意，这个结果与直觉一致：

• 最后让猫安静下来 (v = 0)
• 首先获取尚未离开的猫 (x = 0)
• 让猫首先接近摩托车的速度（或永远不）
• 最后获取距离很远的猫 (x -> +inf)

对于两只猫的情况，它也给出了正确的结果；在这种情况下，如果速度与位移之比相等，那么可以很容易地证明，按照哪种顺序获得猫并不重要（如果它们不相等，则必须先获得比率较高的猫） ）。

现在 - 我还没有解决猫可能具有相同比例的情况。对我来说，并不是很明显，你得到具有相同比例的猫的顺序并不重要。

然而，假设您在某个时刻之前都选择了最佳选择k < n。现在你需要决定要追捕两只比例相同的猫中的哪一只。正如我们已经提到的，对于两只猫的问题，这是一次清洗：所以我认为答案是，你选择哪一个并不重要，因为两者中的任何一个顺序都将花费相同的时间并且“看起来”相同然后。要查看以相同比例开始的两只猫保持相同的比例：

v(i) / x(i) = c; X(i) = x(i) + v(i)t = x(i) + x(i)ct = x(i)(1 + ct)
v(j) / x(j) = c; X(j) = x(j) + v(j)t = x(j) + x(j)ct = x(j)(1 + ct)

因此，比率会随着时间的推移而变化（如果您将其作为X新的初始位移），但是两只以相同比率开始的猫将保持它。新的比率将为：

v / x = c; v / X = v / x(1 + ct) = c / (1 + ct)

值得注意的是，这些比率也不会相互“交叉”。如果您一开始的比率较高或较低，它会随着时间的推移而改变，但不会变得高于或低于其他猫的比率：

c(i) / (1 + c(i)t) > c(j) / (1 + c(j)t)
<=> c(i) + c(i)c(j)t > c(j) + c(i)c(j)t
<=> c(i) > c(j)

基于所有这些考虑，我最好的答案是：

根据度量 v / x 按降序对猫进行排序。你如何打破关系并不重要。按这个顺序把猫拿走。