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

Question

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

Лучший способ решить эту проблему - запланировать эти точки взаимодействия по времени.

Это не единственная моя проблема, мне понадобятся маршруты, которые будут равномерно распределены между экспертами. Таким образом, маршрут 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-> F, A-> A

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

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

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

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

Тогда у вас будет множество нерабочих столкновений:

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

Маршруты 1 и 3 сталкиваются в: 25, 30

Маршруты 2 и 3 сталкиваются в: 30, 40, 45

Это я могу понять до некоторой степени. Но с точки зрения алгоритма я не знаю, с чего начать. ЕСЛИ кто-то может помочь мне с каким-то псевдокодом отработать, или что-то, чтобы сделать это более ясным в моем собственном уме. это очень помогло бы.

Answer 1

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

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

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

У каждого пересечения будет свой собственный занятый / свободный стол.

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

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

Answer 2

Вы должны быть в состоянии рассчитать время столкновения с начала.

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

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

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

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

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

Тогда у вас будет набор нерабочих коллизий:

Маршрут 1 и 2столкновение в: 15, 25, 40

Маршрут 1 и 3 сталкиваются в: 25, 30

Маршрут 2 & 3 сталкиваются в: 30, 40, 45

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