Алгоритм программы присвоения маршрута

Question

Что я пытаюсь сделать, это создать программу, которая назначит маршрут для теста вождения. будет три разных маршрута, связанных в определенных точках. Никогда не должно быть более одного ученика в точке пересечения.

Лучший способ решить это, чтобы запланировать эти точки interection временем.

Это не единственная проблема, мне понадобятся маршруты, которые будут равномерно распределены экзаменаторам. Так маршрут 1 будет дано экзаменатор 1 маршрут 2 - экзаменатор 2 маршрут 3- экзаменатор 3 ...

Реальный Baumann предложил это:

Расчет столкновений раз с начала.

Маршрут 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-> F, A->

Маршрут 2: A-> F , A-> H, A->

Маршрут 3: A-> H, A->

Отсюда можно вычислить время различия, которые создают столкновения.

Если это займет у вас 20 минут, чтобы перейти от маршрута 1 маршрут 1F и 5 минут, чтобы добраться от маршрута 2 Маршрут 2F, то вы знаете, столкновение произойдет, если начать прием на трассу-ровно 15 минут после того, как вы начали встречу на пути 1.

Тогда вы бы иметь набор неработающих столкновений:

Маршрут 1 & 2 Collide по адресу: 15, 25, 40

Маршрут 1 & 3 Collide по адресу: 2 5, 30

Маршрут 2 & 3 сталкиваютс: 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}

Так что вам нужно вычислить следующие времена:

Маршрут 1: A-> F, A->

Маршрут 2: A- > F, A-> H, A->

Маршрут 3: A-> H, A->

Отсюда ча n вычислить разности во времени, которые создают столкновение.

Если вам нужно пройти 20 минут от маршрута 1А до маршрута 1F и 5 минут, чтобы добраться от маршрута 2A до маршрута 2F, то вы знаете, что столкновение произойдет, если вы начнете встречу на Маршруте 2 ровно через 15 минут после того, как вы начнете назначение на маршруте 1.

Тогда вы бы иметь набор неработающих столкновений:

Маршрут 1 & 2 сталкиваютса: 15, 25, 40

Маршрут 1 & 3 Collide в: 25 , 30

Маршрут 2 & 3 столкнуться по адресу: 30, 40, 45

Отсюда вы можете легко создать свое расписание без столкновений.

Answer 2

Я предполагаю, что вы не просите советов о написании супер-пуперного алгоритма, который может одновременно разрешать сотни путей с тысячами пересечений. Похоже, вам нужно что-то простое и удобное, поэтому давайте стремимся к этому.

Прежде всего, давайте упростим проблему. Глядя на карту, вы действительно говорите, что-то вроде этого: если студент начинает маршрут 1 в 8 утра, он будет находиться на пересечении A где-то между 8:03 и 8:05, а затем на пересечении B где-то между 8 : 07 и 8:09.

Для обеспечения того, чтобы на перекрестке не было других учеников, вы можете рассмотреть пересечение «забронировано» от 8: 03-8: 05 от первого парня, а Intersection B «забронировано» аналогично 8: 07-8: 09.

Каждое пересечение будет иметь свой собственный занятый/свободный стол.

Каждый раз, когда вы планируете маршрут, вы бронируете соответствующие перекрестки за время, когда вы считаете, что студент будет в них.

При поиске самого раннего доступного времени для маршрута вы проходите маршруты и считаете время начала X «доступным» для этого маршрута, если каждое пересечение, которое вы пройдете по маршруту, доступно в то время, когда вы Пройдите через них.