一个路由分配的程序算法 [英] A Route Assignment Program Algorithm
问题描述
什么即时试图做的，就是创建一个程序，将指定的路线驾驶考试。将有三个不同势路线，在某些点处连接在一起。决不应该有不止一个学生在一个交点。
What im trying to do, is create a program that will assign a route for a driving test. there will be three diffrent routes, linked together at certain points. Never should there be more than one student at a point of intersection.
要解决这个问题最好的办法是按时间来安排这些interection点。
Best way to solve this is to schedule these interection points by time.
这心不是我的唯一的问题，我将需要路由进行平均分配给考官。 因此，1号线将给予考官1 路线2 - 考官2 路线3考官3 ...
This isnt my only problem, i will need routes to be equally distributed to examiners. So route 1 will be given to examiner 1 route 2 - examiner 2 route 3- examiner 3...
真正的鲍曼认为这样的：
The Real Baumann suggested this:
从开始计算碰撞次数。
1号线有6个点。 {A，B，C，D，E，F}
Route 1 has 6 points. {A,B,C,D,E,F}
2号线有5个点。 {A，F，G，H，I}
Route 2 has 5 points. {A,F,G,H,I}
3号干线有6分。 {A，H，K，L，M，N}
Route 3 has 6 points. {A,H,K,L,M,N}
在可能的冲突： {A，F，H}
所以，你需要计算时间如下：
So you need to calculate the following times:
路线1：A-> F，A-> A
Route 1: A->F, A->A
路线2：A-> F，A-> H，A-> A
Route 2: A->F, A->H, A->A
路线3：A-> H，A-> A
Route 3: A->H, A->A
在这里，您可以计算出产生碰撞时间的差异。
From here you can calculate time differences that create a collision.
如果你花20分钟从路线1A前往路线1F和5 分钟，从路线2A到2F路线，那么你知道碰撞 如果开始约会在2号线正好15分钟后会发生 你开始约会在路线1。
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:
1号线和放大器; 2，在碰撞：15，25，40
Route 1 & 2 collide at: 15, 25, 40
1号线和放大器; 3，在碰撞：25，30
Route 1 & 3 collide at: 25, 30
路线2及3，在碰撞：30，40，45
Route 2 & 3 collide at: 30, 40, 45
这我可以理解为一个点。但是在算法方面我不知道从哪里开始。 如果有人可以帮助我做一些伪code工作过，或东西，使之在我自己的头脑更清晰。这将有很大的帮助。
This i can understand to a point. But in terms of an algorithm i dont know where to start. IF someone could help me with some pseudo code to work off, or something to make it clearer in my own mind. it would help a lot.
推荐答案
我假设你不要求提示上写一个超级骗子的算法，可以解决几百路径与成千上万交叉口的同时。这听起来像你需要一些简单和维修，让我们瞄准这一点。
I'm supposing you're not asking for tips on writing a super-duper algorithm that can resolve hundreds of paths with thousands of intersections simultaneously. It sounds like you need something simple and serviceable, so let's aim for that.
首先，让我们来简化问题。看着地图，你真的说是这样的：如果一个学生开始路线1上午8点，他会在一个路口之间的某个8点03和8点05，然后在路口乙之间的某个时候8 ：07和8:09。
First off, let's simplify the problem. Looking at the map, what you're really saying is something like this: If a student starts route 1 at 8am, he'll be in intersection A sometime between 8:03 and 8:05, and then in intersection B sometime between 8:07 and 8:09.
要确保没有其他学生都在路口，你可以考虑交叉口从8黄牌警告：3月8日：05由第一人，和相交B黄牌警告类似地从8：7月8日：09
To ensure that no other students are in the intersection, you can consider Intersection A "booked" from 8:03-8:05 by the first guy, and Intersection B "booked" similarly from 8:07-8:09.
每个路口将有自己的忙/免费表。
Each intersection would have its own busy/free table.
每次安排的路线，你在你相信学生将在他们的时间预定在适当的交叉点。
Each time you schedule a route, you book the appropriate intersections during the time you believe the student will be in them.
在寻找最早的可用时间，路线，你经过的路线，并考虑开始时间X用为途径，如果每个路口你会经过的路线上可那时的你 ð通过它们。
When looking for the earliest available time for a route, you go through the routes and consider start time X "available" for that route if the of each intersections you'd pass through on the route are available at the time you'd pass through them.
这篇关于一个路由分配的程序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
