哪种算法和数据结构适合道路上交通重叠的用例

问题描述 投票:2回答:1

我有一条道路有多个入口和出口的问题。我正在尝试对其建模,以便流量可以流入一个入口,然后从出口出去。入口点还充当出口。所有入口点都标记为1到10(即,我们有10个入口和出口)。

允许汽车在任何点进出出口但是入口总是比出口少。例如,一辆汽车从3进入,然后到8,则不能从3到3或从8到3。

[每秒,汽车在道路上移动一个单位。因此,从上述示例中,汽车在一秒钟后从3变为4。我想不断接受不同入口处的汽车,并每秒钟更新一次它们的位置。但是,如果入口处已经有一辆汽车,我不能在入口处接受一辆汽车。

[所有汽车以每秒1个单位的相同速度行驶,并且大小相同,并且仅占据它们所处位置的空间。一旦汽车到达目的地,就将其从道路上移开。

对于进入入口并正在等待的所有新车,我们需要分配等待时间。那将如何工作?例如,它需要考虑何时能够找到可以在道路上放置的插槽。

是否有适合该问题的算法?我将在哪种数据结构中进行建模-例如,对于每个入口点,我在想类似队列或有序地图的东西,对于道路,也许是链表?

algorithm data-structures graph-algorithm greedy
1个回答
1
投票

决定每辆车做什么和何时执行的自上而下的主算法之外,还有另一种方法使用agents与它们的环境以及彼此之间进行交互,并带有一组有限的simple rules。这通常会引起复杂行为:您也许可以将简单规则编码到car对象中,以定义这些交互?

也许像这样:

新兴行为算法:

1-如果前方没有汽车,则汽车向前行驶。2-如果一侧没有汽车(可能也在该插槽的后面),则汽车会合并为车道3-汽车驶向目的地,并在到达目的地时自行离开。

提议的数据结构

  • 数据结构可以是“槽”的索引集合,汽车可以沿着该槽朝目的地移动。
  • 两个数据结构可以在每个索引值的元组处相交。
  • 具有2条或更多条车道的道路可以使用耦合的数据结构进行建模...

最佳数字

确定最大道路使用量到达目的地的最短时间将需要运行几次模拟,并使用不同数量的汽车参数,并且可能会更改规则。

一种更精细的方法将使我们在道路上连续不断的空间,而不是离散的插槽。

© www.soinside.com 2019 - 2024. All rights reserved.