Решение: Минимальное время выполнения процессов
В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. Информация о процессах представлена в виде таблицы: в первом столбце указан идентификатор процесса, во втором — время его выполнения в миллисекундах, в третьем перечислены через «;» идентификаторы процессов, от которых зависит данный процесс. Если процесс независимый, указано значение 0. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, если все независимые друг от друга процессы могут выполняться параллельно. Используйте данные из прилагаемого файла.
Решение по шагам
3 шагаПредставим процессы в виде ориентированного графа зависимостей. Для каждого процесса вычисляем минимальное время, к которому он может завершиться.
$$T_i = t_i, если процесс независимый$$Если у процесса есть зависимости, он может начаться только после завершения всех процессов-предшественников. Поэтому к его длительности прибавляется максимальное время завершения среди зависимостей.
$$T_i = t_i + \max\limits_{j \in D_i} T_j$$После обработки всех строк файла выбираем максимальное время завершения процесса. Для приведённых в файле данных это значение равно 53 миллисекундам.
$$\max_i T_i = 53$$Где здесь ошибаются
Складывают времена всех процессов, хотя независимые процессы выполняются параллельно.
Прибавляют к времени процесса минимальное, а не максимальное время завершения его зависимостей.
Не учитывают цепочку зависимостей из нескольких процессов.