路由分配程序算法

即时尝试执行的操作是创建一个程序，为驾驶测试分配路线。将有三条不同的路线，在某些点连接在一起。在交叉点不应该有一个以上的学生。要解决这个路由分配程序算法

enter image description here

最好的办法是通过时间来安排这些interection点。

这不是我唯一的问题，我需要路线平均分配给考官。所以路线1将给予考官1条路线2 - 考官2 路线3-考官3 ...

真正鲍曼提出这样的：

从开始计算碰撞次数。

路线1有6点。 {A,B,C,D,E,F}

路线2有5点。 {A,F,G,H,I}

3号线有6点。 {A,H,K,L,M,N}

可能碰撞在：{A,F,H}

所以，你需要计算时间如下：

路线1：A->楼A->一个

路线2：A->˚F ，A-> H，A->一个

路线3：A-> H，A->一个

从这里你可以计算出产生碰撞时间差。

如果你花20分钟路线1A前往路线1F和5 分钟即可到达，从路线图2A至路线2F，那么你知道发生碰撞，如果正好15分钟后在2号线开始预约会发生您在路线1

开始约会然后你将有一组非工作的碰撞：

路线1 & 2处冲突：15，25，40

路线1 & 3相碰在：2如图5所示，在30

路线2 & 3碰撞：30，40，45

此我可以理解到一个点。但就算法而言，我不知道从哪里开始。如果有人可以帮助我解决一些伪代码，或者在我的脑海中弄清楚它。这会有很大的帮助。

来源

2012-02-02 user1081326

细分是否加权？ IE从1A到1B需要多少时间？细分市场是否有序？我必须顺时针/逆时针行驶吗？ – 2012-02-01 18:55:14

这是一个家庭作业问题吗？ – Servy 2012-02-01 18:59:16

另外，学生是否可以同时离开并返回总部，或者是否违反了交叉规则？ – 2012-02-01 18:59:52

您应该可以从开始计算碰撞时间。

路线1有6分。{A,B,C,D,E,F}

路线2有5分。 {A,F,G,H,I}

路线3有6分。 {A,H,K,L,M,N}

可能发生的碰撞在：{A,F,H}

所以，你需要计算时间如下：

路线1：A->楼A->一个

路线2：A- >楼A-> H，A->一个

路线3：A-> H，A->一个

从这里你CA n计算产生碰撞的时间差异。

如果从路线1A到路线1F需要20分钟，从路线2A到路线2F需要5分钟，那么如果在路线2开始约会15分钟后开始预约，则会发生碰撞在路线1.预约

那么你将有一组非工作的碰撞：

路线1个& 2处冲突：15，25，40

路线1个& 3处冲突：25 ，30

Route 2 & 3碰撞：30,40,45

从这里您应该很容易就能够创建您的日程安排而不会发生碰撞。

来源

2012-02-01 19:22:58

感谢您花时间帮助我，感谢您在我的脑海中简化它。所以如上所述，时间表是这里最好的方式。谢谢你的回复。 – user1081326 2012-02-01 20:02:21

我想你并不是要求写一个超级算法的技巧，可以同时解决数以千计的交点的数百条路径。这听起来像你需要一些简单和可用的东西，所以让我们瞄准这一点。

首先，让我们简化问题。看看地图，你真正在说的是这样的：如果学生在上午8点开始路线1，他将在8:03和8:05之间的交点A处，然后在交点B之间的某段时间：07和8:09。

为确保没有其他学生在十字路口，您可以考虑第一个人从8：03-8：05交叉口A“预订”，同样从8：07-8： 09。

每个十字路口都有它自己的忙/闲表。

每次安排路线时，您都会在相信学生将在其中的时候预订适当的路口。

在寻找路线的最早可用时间时，如果您经过路线时所经过的每个路口在您当时可用时通过路线并考虑该路线的开始时间X“可用” 'd经过他们。

来源

2012-02-01 19:28:20 CodeGnome

感谢您抽出宝贵时间回复，我认为时间表将是这一次的前进方向。 – user1081326 2012-02-01 20:03:06

路由分配程序算法

回答

相关问题