У меня есть ориентированный ациклический график, подобный показанному на рисунке ниже.
Я хочу добиться ** топологического порядка, в котором каждый узел имеет приоритет p
позже используется для планирования (где более высокое значение означает более высокий приоритет)
Топологическую сортировку, такую как линейный список в приведенной ниже визуализации, можно вычислить за линейное время, посетив каждый узел и ребро один раз (O (| V | + | E |) (https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search)
Однако, когда задача распределения приоритетов вступает в игру, я не могу найти лучший алгоритм, чем делать это ниже.
n
в графе g
приоритет p=0
, n
в графе g
:
n
n
(есть несколько небольших оптимизаций: игнорирование подграфов, с которых мы уже запустили DFS, и только увеличение смещения приоритета подграфа, приоритет каждого узла затем вычисляется по его локальному приоритету + смещению приоритета подграфа)
Каждая рекурсия в глубину начинается с n
нельзя упростить, игнорируя уже посещенные узлы внутри цикла for выше, как это можно сделать для простой топологической сортировки (линейный список в изображении, (https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search))
Лучше ли сначала вычислить топологический порядок (O (| V | + | E |), а затем выполнить итерацию по линейному списку и назначить приоритеты (O (| V | + | E |))?
Я хотел бы иметь менее четкие приоритеты, насколько это возможно, чтобы учесть параллельное планирование (узлы D и E могут быть запланированы одновременно на изображении)
Задача ещё не решена.
Других решений пока нет …