algorithm - 一种路径分配程序算法

Question

我想做的是创建一个程序，为驾驶考试分配路线。将有 3 条不同的路线，在某些点连接在一起。一个交叉点永远不应该有一个以上的学生。

解决这个问题的最好方法是按时间安排这些交叉点。

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

真正的鲍曼建议:

Calculate collision times from start.

Route 1 has 6 points. {A,B,C,D,E,F}

Route 2 has 5 points. {A,F,G,H,I}

Route 3 has 6 points. {A,H,K,L,M,N}

Possible Collisions at: {A,F,H}

So you need to calculate the following times:

Route 1: A->F, A->A

Route 2: A->F, A->H, A->A

Route 3: A->H, A->A

From here you can calculate time differences that create a collision.

If it takes you 20 minutes to go from route 1A to Route 1F and 5 minutes to get from Route 2A to Route 2F, then you know a collision will occur if start an appointment on Route 2 exactly 15 minutes after you began an appointment at Route 1.

Then you would have a set of non-working collisions:

Route 1 & 2 collide at: 15, 25, 40

Route 1 & 3 collide at: 25, 30

Route 2 & 3 collide at: 30, 40, 45

这个我能理解到一点。但就算法而言，我不知道从哪里开始。 如果有人可以帮助我处理一些伪代码，或者让我自己更清楚一些。会有很大帮助。

Answer 1

您应该能够从一开始就计算碰撞时间。

路线 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}

所以需要计算以下时间:

路线一:A->F, A->A

路线2:A->F, A->H, A->A

路线3:A->H，A->A

从这里您可以计算出造成碰撞的时间差。

如果您从路线 1A 到路线 1F 需要 20 分钟，从路线 2A 到路线 2F 需要 5 分钟，那么您知道如果在路线 2 上开始预约后刚好 15 分钟就会发生碰撞在路线 1 预约。

然后你会有一组非工作碰撞:

路线 1 和路线 2 在 15、25、40 处相撞

路线 1 和路线 3 在 25、30 处相撞

路线 2 和路线 3 在 30、40、45 处相撞

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