Как найти оптимальное количество раундов и исключений, необходимых для DAG? - PullRequest
Новая
       129

Как найти оптимальное количество раундов и исключений, необходимых для DAG?

0 голосов
/ 12 июля 2020

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

Проблема в следующем:

Нам дается направленный ациклический код c граф (DAG) с N узлами и M ребрами. Ни у одного из узлов не может быть более одного внешнего края. Под исключением мы определяем процесс удаления узла, не имеющего внутренних краев, а округлением - процесс выполнения произвольного числа исключений. Наша цель - удалить все узлы из графа. Возникает вопрос: какое минимальное количество раундов необходимо для достижения нашей цели, и какое максимальное количество выбываний необходимо в раунде, если мы хотим минимизировать это количество? Например, если N = 9, и набор ребер равен {(1, 2), (2, 3), (3, 4), (5, 2), (8, 3), (6, 9) , (7, 9), (9, 3)}, то минимальное количество раундов равно 4, причем 4 - это максимальное количество необходимых исключений. Эти раунды следующие: Сначала мы устраняем 1, 5, 6, 7, затем 2, 8, 9, затем 3, затем 4. Ниже представлено визуальное представление этого графика.

График из примера

Мой подход следующий: чтобы найти необходимое количество раундов, мы строим обратный граф данного графа (граф, в котором ребра имеют обратное направление, чем в оригинале). Мы делаем обход в глубину на этом графике, чтобы вычислить для каждого узла P длину самого длинного пути, начиная с P. Тогда количество необходимых раундов будет максимальным из этих длин. 

main:
initialize seen as an array (1...N), with all elements false
initialize len as an array (1...N), with all elements 0
for each node between 1 and N do
    if seen[node] is false
        dfs(node)
let solution be the maximum in len
end of main

dfs(node):
    seen[node] = true
    let curr_len = 0
    for each next_node that is neighbour of node
        if seen[next_node] is false
            dfs(next_node)
        curr_len = max(curr_len, len[next_node])
    len[node] = curr_len + 1;
end of dfs

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

...