Направленный ациклический граф и его топологическая сортировка (назначить приоритеты)

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

Я хочу добиться ** топологического порядка, в котором каждый узел имеет приоритет p позже используется для планирования (где более высокое значение означает более высокий приоритет)

Топологическую сортировку, такую ​​как линейный список в приведенной ниже визуализации, можно вычислить за линейное время, посетив каждый узел и ребро один раз (O (| V | + | E |) (https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search)

Однако, когда задача распределения приоритетов вступает в игру, я не могу найти лучший алгоритм, чем делать это ниже.

  1. Назначить каждому узлу n в графе g приоритет p=0,
  2. для каждого узла n в графе g:
    • начать глубинную рекурсию с узла n
      • пересекая подграф из n
        • если родительский узел уже имеет более высокий приоритет в качестве текущего узла, вам не нужно идти глубже, и вы можете продолжить работу с другими узлами в рекурсии первой глубины.
        • если приоритет равен или ниже,
          установить приоритет родительских узлов на приоритет
          текущий узел + 1 и навестить родителя.

(есть несколько небольших оптимизаций: игнорирование подграфов, с которых мы уже запустили DFS, и только увеличение смещения приоритета подграфа, приоритет каждого узла затем вычисляется по его локальному приоритету + смещению приоритета подграфа)

Каждая рекурсия в глубину начинается с n нельзя упростить, игнорируя уже посещенные узлы внутри цикла for выше, как это можно сделать для простой топологической сортировки (линейный список в изображении, (https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search))

Лучше ли сначала вычислить топологический порядок (O (| V | + | E |), а затем выполнить итерацию по линейному списку и назначить приоритеты (O (| V | + | E |))?
Я хотел бы иметь менее четкие приоритеты, насколько это возможно, чтобы учесть параллельное планирование (узлы D и E могут быть запланированы одновременно на изображении)

Топологическая сортировка по назначению приоритетов

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector