Решение: Минимальное время процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце указан идентификатор процесса ($ID$), во втором — время его выполнения в миллисекундах, в третьем перечислены через разделитель «;» $ID$ процессов, от которых зависит данный процесс. Если процесс является независимым, указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Для решения используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПредставим процессы в виде ориентированного графа: ребро направлено от процесса-предшественника к процессу, который от него зависит.
Для каждого независимого процесса время завершения равно его длительности.
$$T_i=t_i$$Для процесса с предшественниками определяем наиболее позднее время их завершения. Процесс начинается только после этого момента.
$$T_i=t_i+\max_{j\in P_i}T_j$$Минимальное время выполнения всей совокупности процессов равно времени завершения последнего процесса, то есть максимуму рассчитанных значений.
$$T_{\min}=\max_i T_i$$Числовой ответ определяется по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Складывать времена всех процессов, хотя независимые процессы могут выполняться параллельно.
Брать минимум времени завершения предшественников вместо максимума.
Не учитывать цепочку зависимостей через промежуточные процессы.