Определение минимального времени выполнения запланированных задач с помощью топологической сортировки

Я предполагаю, что задачи не имеют циклических зависимостей. Таким образом, задачи и их зависимости могут быть представлены в виде направленного ациклического графа (отсюда сокращенно dag), где задачи являются вершинами, а ребро u -> v означает, что задача u должна быть завершена, прежде чем задача v может начаться.

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

1. Вычисление задач, которые можно выполнять одновременно
2. Вычисление минимального количества времени для выполнения всех задач

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

Вот псевдокод алгоритма (я думаю, он должен быть правильным, но поскольку я не делал этого некоторое время, я могу ошибаться, поэтому проверьте себя):

min_time_for_tasks(Graph, topological order):
    distance <- integer array whose size is number of vertices
    set all entries in visited array to negative infinity
    maxDist <- 0
    for v in topological order:
        if distance[v] == negative infinity:
            maxDist <- max(maxDist, longest_path(Graph, distance, v))
    return maxDist

// computes the longest path from vertex v
longest_path(Graph, distance, v):
    maxDist <- 0
    for all edges (v,w) outgoing from v:
        // vertex w has not been visited
        if distance[w] == negative infinity:
            longest_path(Graph, distance, w)
        // get the longest path among all vertices reachable from v
        maxDist <- max(maxDist, distance[w])
    distance[v] <- maxDist + time to complete task v
    return distance[v]

Что касается номера 1, то есть вычисления задач, которые можно выполнять одновременно, это немного сложнее. На самом деле я этого раньше не делал, но думаю, что это можно сделать с помощью алгоритма топологической сортировки под названием алгоритм Кана (это первый алгоритм топологической сортировки в Википедии, ссылка здесь). Не знаю, как вы, но обычно я выполняю топологическую сортировку, используя сначала поиск в глубину и стек, а затем выталкиваю вершины из стека для получения порядка. По сути, алгоритм Кана - это алгоритм топологической сортировки, и с некоторыми небольшими изменениями он должен быть в состоянии решить нашу первую проблему. Я не делал этого раньше, поэтому проверьте это еще раз. Псевдокод с пояснением в комментариях:

// This is a modified kahn's algorithm.
// Again, the graph is assumed to be a dag, and we first compute
// the number of incoming edges to every vertex, since Kahn's
// algorithm is dependent on this information.
// This function will return an array of sets of tasks which
// can be done at the same time.
// So all tasks in the set in returnArray[0] can be done at the same
// time, all tasks in the set in returnArray[1] can be done at the
// same time, etc. Explanation will be available after the
// pseudocode
compute_simultaneous_tasks(Graph):
    into <- integer array, all entries initialized to 0
    // this function is defined below
    compute_incoming_edges(Graph, into)
    returnArray <- empty array
    VSet <- Set of all vertices in the graph
    while VSet is not empty:
        // retrieve all vertices with no incoming edges
        // this means their prerequisite tasks have been completed,
        // and we can execute that particular task
        headVertices <- all vertices `v` in VSet such that into[v] is 0

        // remove all the vertices in headVertices from VSet
        VSet <- VSet.remove(headVertices)

        // we are going to remove the vertices in headVertices,
        // so the edges outgoing from them will be removed as well.
        for each vertex v in headVertices:
            for each vertex w outgoing from v:
                into[w] <- into[w] - 1

        // all the vertices in headVertices can be started at the
        // same time, since their prerequisite tasks have been
        // completed
        returnArray.append(headVertices)

    return returnArray

// computes the number of edges leading into each vertex
// so into[x] gives the number of edges leading into vertex x
// from some other vertex
compute_incoming_edges(Graph, into):
    for each vertex v in Graph:
        for each vertex w outgoing from v:
            into[w] <- into[w] + 1

Таким образом, функция compute_simultaneous_tasks вернет массив наборов. Каждый набор содержит вершины / задачи, которые можно выполнять одновременно. Чтобы понять, почему это так, внутри основного цикла compute_simultaneous_tasks мы извлекаем все вершины, у которых нет входящих ребер. Это эквивалентно извлечению всех задач без предварительных условий. Следовательно, мы видим, что выполнять этот набор задач одновременно безопасно, поскольку они не имеют предварительных требований и, конечно же, не зависят друг от друга! Затем мы удаляем их исходящие края, чтобы смоделировать их завершение. Затем мы переходим к следующей итерации цикла и т. Д.

Итак, мы видим, что на каждой итерации цикла while мы делаем то, что только что описали, и, следовательно, безопасно выполнять все задачи в returnArray[0] одновременно, все задачи в returnArray[1] одновременно но только после того, как все задачи в returnArray[0] выполнены, все задачи в returnArray[2] после задач в returnArray[1] выполнены и так далее.