我想做的是创建一个程序,为驾驶考试分配路线。将有 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
这个我能理解到一点。但就算法而言,我不知道从哪里开始。 如果有人可以帮助我处理一些伪代码,或者让我自己更清楚一些。会有很大帮助。
最佳答案
您应该能够从一开始就计算碰撞时间。
路线 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 处相撞
从这里您应该能够很容易地创建您的日程安排而不会发生冲突。
关于algorithm - 一种路径分配程序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9101474/