0

对于交通模拟中的每辆给定汽车，Nagel-Schreckenberg 模型指定以下四个步骤必须按以下规定的顺序并行应用于模拟中的所有汽车：

  1. 加速度：所有未达到最大速度的汽车的速度增加一个单位。例如，如果速度为 4，则将其增加到 5。
  2. 减速：检查所有汽车以查看它与前面汽车之间的距离（以单元为单位）是否小于其当前速度（每个时间步长为单元单位）。如果距离小于速度，则速度会降低到汽车前方空单元的数量——以避免碰撞。例如，如果现在一辆车的速度为 5，但它前面只有 3 个空闲单元格，而第四个单元格被另一辆车占用，则汽车速度降低到 3。
  3. 随机化：所有速度至少为 1 的汽车的速度现在以 p 的概率减少一个单位。例如，如果 p = 0.5，那么如果速度为 4，则它减少到 3 50% 的时间。
  4. 汽车运动：最后，所有汽车向前移动的单元数等于它们的速度。例如，如果速度为 3，则汽车向前移动 3 个单元格。

（内格尔施雷肯伯格模型）

我理解这背后的逻辑，我理解为什么它必须并行执行才能正常工作。但是，我不确定如何在 Java 中实现这一点。既然它必须并行执行，它必须意味着分配一个单独的线程来大致在同一时间为每辆车运行所有这些步骤？

对于我一次可以在模拟中运行的多达 30 辆汽车来说，这不是很多线程吗？我能想到的唯一方法是拥有一个线程池并重用它们以避免每次都创建线程。不过，我仍然不确定这是一个最佳解决方案。

有什么想法吗？

4

2 回答 2

2

该算法背后的想法是，您需要在计算之前维护模型的状态，然后计算所有汽车，然后更新整个模型。

这就是通常所说的parallel更新。

如果您在计算时进行更新，则您的模型中的行为会不一致，因为它会在您为下一个时间步计算它时发生变化。

Concurrent意味着您确实可以使用1-n线程来做同样的事情，因为您的计算可以为每辆汽车同时完成，因为模型不应该改变。

就个人而言，只要您的模型的计算成为瓶颈，我就不会同时进行，很可能当您有很多汽车时。在这种情况下，我会分配一个ThreadPool与 CPU 内核数量相等的线程，并将汽车列表分块为相等数量的汽车。

然后让每个线程计算模型的新状态，然后再次组合部件。

于 2013-03-17T12:32:59.470 回答
2

我认为这在维基百科文章中的呈现方式有些误导。

如果您检查这 4 个步骤，您会发现前 3 个步骤在逻辑上可以折叠为 1 个（根据当前速度、前方空闲单元的数量和随机因素调整车辆速度）。对于每辆车，其中只有一个是外部状态 - 编号。自由单元 - 仅在步骤 4 中更新。步骤 4 不受外部状态的影响 - 汽车根据其当前速度盲目移动。这就是文章中“并行”的含义——这 2 个逻辑动作不是按每辆车的顺序执行，而是针对整个模型执行。

因此，线程问题没有实际意义，因为只需要修改所有汽车的速度，然后移动所有汽车。除了效率之外，在这两个步骤中都没有对多线程的内在需求。

因此，最简单的实现是：

（给定一系列汽车）

  • 迭代所有汽车，应用速度修改规则
  • 遍历所有汽车，应用位置变化
  • 重复直到完成
于 2013-03-17T12:33:27.267 回答