如何实现Race模拟问题的解决方案

Question

在接受采访时提出了一个问题:

在一级方程式挑战中,有n个队伍编号为1到n.每个团队都有一辆车和一个司机.汽车的规格如下:

• 最高速度:每小时(150 + 10*i)km
• 加速度:(2*i)米/秒方形.
• 处理系数(hf)= 0.8
• Nitro:将速度提高到双倍或最高速度,以较小者为准.只能使用一次.

这是我的球队号码.赛车排队参赛.第(i + 1)辆车的起跑线位于第i辆车后面200*i米处.

所有这些都是在同一时间开始并试图达到他们的最高速度.每2秒钟对位置进行一次重新评估(所以即使汽车已经越过终点线,你也会在2秒后知道).在此评估期间,每位司机检查他的车10米范围内是否有车,他的速度降低到:hf*(当时的速度).此外,如果车手注意到他是比赛中的最后一名,他会使用'nitro'.

以团队数量和轨道长度为输入,计算最终速度和相应的完成时间.

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

Answer 1

如果你查看康威的生命游戏,你会发现种族问题有很多共同之处.

这是类比:

• 初始状态(系统的种子):
  • 生命游戏:网格上的初始模式.每个单元格都具有以下参数:
    • x和y坐标
    • 细胞是活着的还是死的
  • 比赛问题:每辆车都有预定的参数和轨道长度l.每辆车都有以下参数:
    • 最高速度
    • 促进
    • 处理因素
    • 在轨道上的位置
    • 现在的速度
• 规则应用于称为刻度的离散时刻.
  • 生命游戏:规则同时应用于上一代产生下一代的每个细胞.每一代都是前一代的纯粹功能.
  • 种族问题:规则同时适用于前一个州生产下一个州的每辆汽车.这种情况每2秒发生一次.与Game of Life相同,每一步都是前一步的纯函数,这意味着它只取决于前一状态的汽车参数.

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

关键点在于计算是在离散时刻完成的,它可以回答您的问题:

但是我怎么能弄清楚我应该在什么样的情况下进行计算呢？

您可以从" 算法"部分中获取想法来解决此问题.你需要有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)

每次迭代的复杂性.但是,您可以在这里考虑可能的优化.例如,您可以按当前位置 first(O (n * log(n)))对汽车进行排序,然后遍历排序的数组,仅检查相邻的汽车(O (2 * n)).你可以这样做,因为如果10米的条件不满足相邻的汽车,它将不满足非相邻的汽车.这将给您带来的复杂性:

O (n * log(n))

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

对于每个实例,我应该检查每对驱动程序的所有C(n,2)组合并计算结果吗？