График светофора

Question

Скажем, у вас есть стандартный граф со значениями, прикрепленными к каждому узлу и каждому ребру. Вы хотите перейти от одного узла на графике к другому в кратчайшие сроки. Время, которое вы потратили до этого графика, будет называться T. Если ребро имеет значение V, обход этого края добавит V к вашему времени (T + = V). Если узел имеет значение N, то перемещение этого узла заставит вас ждать, пока ваше потраченное время будет делимым на N (T + = (N - T% N)% N).

Вы можете думать об этом как о улицах и светофорах. Вождение по улице занимает постоянное время, чтобы добраться до другого конца. Вождение через светофор занимает столько времени, что вам придется ждать, пока он станет зеленым.

Например, предположим, что у вас есть этот график:

S--6--[1]--2--[7] 
     |  | 
     3  2 
     |  | 
     [9]--3--[6]--1--E 

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

Start: 0 + 6 -> 6 
     6 % 1 == 0 # We can pass 
     6 + 3 -> 9 
     9 % 9 == 0 # We can pass 
     9 + 3 -> 12 
     12 % 6 == 0 # We can pass 
     12 + 1 -> 13 
End: 13 

А потом верх:

Start: 0 + 6 -> 6 
     6 % 1 == 0 # We can pass 
     6 + 2 -> 8 
     8 % 7 != 0 # Have to wait 
     8 + 6 -> 14 
     14 % 7 == 0 # We can pass 
     14 + 2 -> 16 
     16 % 6 != 0 # Have to wait 
     16 + 2 -> 18 
     18 % 6 == 0 # We can pass 
     18 + 1 -> 19 
End: 19 

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

Answer 1

Он известен как проблема поиска кратчайшего пути и может быть решена алгоритмом Дейкстры в полиномиальное время. Когда вычисляется длина пути, необходимо также добавить количество времени ожидания в целевой вершине (за исключением целевой вершины). Таким образом, это проблема поиска кратчайшего пути, но весовая функция немного отличается от суммарной массы простых ребер.