algorithm - 如何实现竞赛模拟问题的解决方案

Question

面试中有一个问题:

在一级方程式挑战赛中，有 n 支队伍，编号为 1 到 n。每个团队都有一辆车和一个司机。汽车规范如下:

• 最高时速:(150 + 10 * i) 公里/小时
• 加速度:(2 * i) 米/平方秒。
• 处理系数 (hf) = 0.8
• Nitro:将速度提高到两倍或最高速度，以较小者为准。只能使用一次。

这里我是队号。赛车排队等待比赛。第 (i + 1) 辆车的起跑线在第 i 辆车后 200 * i 米处。

所有的人都同时开始，并试图达到他们的最高速度。每 2 秒重新评估一次位置(因此即使汽车在中间越过终点线，您也会在 2 秒后知道)。在这个评估过程中，每个司机检查他的车 10 米内是否有任何汽车，他的速度降低到:hf *(当时的速度)。此外，如果司机注意到他是比赛中的最后一名，他会使用“nitro”。

以车队数量和赛道长度为输入，计算最终速度和对应的完赛时间。

我不明白如何处理这类问题。对于每个实例，我应该检查所有 C(n,2)每对驱动程序的组合并计算结果？但是我怎样才能确定应该在什么情况下进行计算呢？

Answer 1

如果您检查 Conway's Game of Life你会发现这与种族问题有很多共同点。

下面是类比:

• 初始状态(系统的种子):
  • 生命游戏:网格上的初始模式。每个单元格具有以下参数:
    • x 和 y 坐标
    • 细胞是活的还是死的
  • 比赛问题:n 辆汽车，每辆汽车都有预先确定的参数和赛道长度 l。每辆车都有以下参数:
    • 最高速度
    • 加速度
    • 处理因素
    • 正轨
    • 当前速度
• 规则在离散时刻应用，称为滴答。
  • 生命游戏:规则同时应用于上一代产生下一代的每个细胞。每一代都是前一代的纯函数。
  • 比赛问题:规则同时应用于从前一个状态产生下一个状态的每辆汽车。这每 2 秒发生一次。与生命游戏一样，每一步都是前一步的纯函数，这意味着它仅取决于前一状态的汽车参数。

不同的是，生命游戏永远不会结束，而竞赛问题应该在每辆汽车的当前位置大于或等于赛道长度 l 时终止(尽管最后一个陈述是有争议的:由于处理因素，它是可能的在某些情况下，有些汽车永远无法到达终点线)。

关键是计算是在离散时刻完成的，这回答了您的问题:

But how can I figure out at what instance I should make the calculations?

您可以从 Algorithms 中获取灵感部分来解决这个问题。您需要有 2 个汽车阵列:一个代表当前状态，另一个代表下一步。在每次迭代中，您都会按照分配的规则重新计算每辆汽车的当前位置和速度，并检查循环是否应该终止。在下一次迭代之前，您交换数组角色，以便上一次迭代中的后继数组成为下一次迭代中的当前数组。

高级伪代码可能如下所示:

n = ..; // initial number of cars
l = ..; // track length
Car[] currentState = initializeState(n, l);
Car[] nextState = clone(currentState);
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
    calculateNextState(currentState, nextState, iteration);
    swap(currentState, nextState);
    if (shouldTerminate(currentState, l) {
        break;
    }
}

printResultOrClaimNotTerminated(currentState);

规则在 calculateNextState(..) 函数中应用。在最天真的实现中，你检查每一对给你的汽车

O (C(n, 2)) = O (n * (n - 1)/2) = O (n ^ 2)

每次迭代的复杂性。但是，您可以在此处考虑可能的优化。例如，您可以先按当前位置对汽车进行排序 (O (n * log(n)))，然后遍历排序后的数组，只检查相邻的汽车 ( O (2 * n))。您可以这样做，因为如果 10 米的条件不能满足相邻汽车的要求，那么它也不能满足非相邻汽车的要求。这会给您带来以下复杂性:

O (n * log(n))

哪个更好。排序后的汽车阵列自然会为您提供需要应用硝基增压规则的最后位置的汽车。可能还有其他优化。这回答了你的问题:

For each instance should I be checking all C(n,2) combinations of every pair of drivers and compute the result?