如何实施竞赛模拟问题的解决方案
How to implement solution for Race simulation problems
面试中被问到的问题：
在一级方程式挑战赛中，有 n 支队伍，编号为 1 到 n。每个团队都有一辆汽车和一辆driver。车辆规格如下：
- 最高时速：(150 + 10 * i) 公里每小时
- 加速度：(2 * i) 米/平方秒。
- 处理系数 (hf) = 0.8
- Nitro：将速度提高到两倍或最高速度，以较小者为准。只能使用一次。
这里我是队号。
赛车排队等待比赛。第 (i + 1) 辆车的起跑线在第 i 辆车后 200 * i 米处。
他们都同时出发，并努力达到最高速度。 A re-assessment 个位置每 2 秒完成一次（所以即使汽车在中间已经越过终点线，你也会在 2 秒后知道）。在这个评估过程中，每个driver检查他的车10米内是否有车，他的速度降低到：hf *（当时的速度）。此外，如果 driver 注意到他是比赛中的最后一个，他会使用“nitro”。
以队伍数量和赛道长度为输入，计算最终速度和对应的完赛时间。
我不明白如何处理这类问题。对于每个实例，我是否应该检查每对 driver 的所有 C(n,2) 组合并计算结果？但是我怎样才能弄清楚我应该在什么情况下进行计算呢？
如果你查看 Conway's Game of Life 你会发现这与 Race Problem 有很多共同点。
打个比方：
- 初始状态（系统的种子）：
- 生命游戏：网格上的初始图案。每个单元格具有以下参数：
- 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?
汽车对象和游戏对象
我假设您已经为汽车创建了必要的对象，封装在游戏对象中。
关于加快每个更新步骤以不执行所有 C(n,2) 检查的想法
您可以通过不必检查所有 C(n,2) 组合来加快更新位置和参数的步骤。您可以使用的一种简单的启发式方法是，我们不需要检查距离很远的汽车之间的交互。例如，赛道第一节的汽车不会与赛道第三节的汽车互动。我认为根据你问题的参数，你想将赛道分成 10m 长的部分。维护每个部分的列表并跟踪每个部分中的所有汽车。更新位置后，仅检查连续部分中汽车之间的交互。
同样，在每个更新步骤中跟踪哪辆车处于最后位置，并相应地切换硝基助推器。
时间步的选择
在你的问题中，timeStep 似乎固定为 2 秒。但是，在一般情况下，例如编写游戏代码时，此选择至关重要。您可以尝试使用几个不同的数字（例如 10,50,100,500 毫秒）。
如果您选择 timeStep 为更大的数字，（例如）汽车可能会穿过另一辆汽车并避免碰撞检测。
另一方面，如果您选择的 timeStep 太小，并且操作所花费的时间大于 timeStep，则游戏将 运行 比实际时间慢。
面试中被问到的问题：
在一级方程式挑战赛中，有 n 支队伍，编号为 1 到 n。每个团队都有一辆汽车和一辆driver。车辆规格如下：
- 最高时速：(150 + 10 * i) 公里每小时
- 加速度：(2 * i) 米/平方秒。
- 处理系数 (hf) = 0.8
- Nitro：将速度提高到两倍或最高速度，以较小者为准。只能使用一次。
这里我是队号。 赛车排队等待比赛。第 (i + 1) 辆车的起跑线在第 i 辆车后 200 * i 米处。
他们都同时出发，并努力达到最高速度。 A re-assessment 个位置每 2 秒完成一次（所以即使汽车在中间已经越过终点线，你也会在 2 秒后知道）。在这个评估过程中，每个driver检查他的车10米内是否有车，他的速度降低到：hf *（当时的速度）。此外，如果 driver 注意到他是比赛中的最后一个，他会使用“nitro”。
以队伍数量和赛道长度为输入，计算最终速度和对应的完赛时间。
我不明白如何处理这类问题。对于每个实例，我是否应该检查每对 driver 的所有 C(n,2) 组合并计算结果？但是我怎样才能弄清楚我应该在什么情况下进行计算呢？
如果你查看 Conway's Game of Life 你会发现这与 Race Problem 有很多共同点。
打个比方：
- 初始状态（系统的种子）：
- 生命游戏：网格上的初始图案。每个单元格具有以下参数：
- 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?
汽车对象和游戏对象
我假设您已经为汽车创建了必要的对象，封装在游戏对象中。
关于加快每个更新步骤以不执行所有 C(n,2) 检查的想法
您可以通过不必检查所有 C(n,2) 组合来加快更新位置和参数的步骤。您可以使用的一种简单的启发式方法是，我们不需要检查距离很远的汽车之间的交互。例如，赛道第一节的汽车不会与赛道第三节的汽车互动。我认为根据你问题的参数，你想将赛道分成 10m 长的部分。维护每个部分的列表并跟踪每个部分中的所有汽车。更新位置后，仅检查连续部分中汽车之间的交互。
同样，在每个更新步骤中跟踪哪辆车处于最后位置，并相应地切换硝基助推器。
时间步的选择
在你的问题中，timeStep 似乎固定为 2 秒。但是，在一般情况下，例如编写游戏代码时，此选择至关重要。您可以尝试使用几个不同的数字（例如 10,50,100,500 毫秒）。
如果您选择 timeStep 为更大的数字，（例如）汽车可能会穿过另一辆汽车并避免碰撞检测。 另一方面，如果您选择的 timeStep 太小，并且操作所花费的时间大于 timeStep，则游戏将 运行 比实际时间慢。