Графы DAG

обработка графов DAG проще, чем обработка орграфа общего вида, тем не менее, мы знаем, что если мы столкнемся с задачей, которая трудно решается на графе DAG, то решение этой же задачи на орграфах общего вида едва ли окажется проще. Как мы смо­жем убедиться далее, задача вычисления транзитивного замыкания попадает именно в эту категорию. И наоборот, осознание сложности обработки графов DAG важно с той точ­ки зрения, что каждый орграф содержит некоторый DAG в качестве своего ядра (см. свойство 19.2), так что мы сталкиваемся с графами DAG даже в тех случаях, когда рабо­таем с орграфами, не являющимися графами DAG.

Приложение-прототип, в котором графы DAG возникают сами по себе, называется приложением составления расписаний (scheduling). В общем случае решение задачи состав­ления расписаний заключается в организации завершения решения некоторого множества задач (tasks) в условиях действия некоторого набора ограничений (constraints) путем зада­ния условий, когда и как эти задачи должны выполняться. Ограничениями могут быть не­которые функции от времени выполнения или от других ресурсов, потребляемых зада­чей. Наиболее важным типом ограничений является ограничения предшествования (precedence constraints), которые определяют, что одни задачи должны быть обязательно решены до того, как может быть начато решение других задач, благодаря чему на множество задач устанавливается некоторый частичный порядок. Различные виды дополнительных огра­ничений приводят к возникновению различных типов задач составления расписаний раз­ной степени сложности. Изучению подверглись буквально тысячи различных задач, при этом исследователи продолжают поиск более совершенных алгоритмов решения для мно­гих из них. Возможно, простейшую нетривиальную задачу составления расписания мож­но сформулировать следующим образом:

Составление расписаний. Пусть дано множество задач, требующих решения, на кото­ром задан частичный порядок, определяющий, что решение некоторых задач должны быть завершено, прежде чем начнется выполнение некоторых других задач. Каким образом можно организовать решение всех задач множества так, чтобы в конечном итоге все они были успешно завершены с соблюдением частичного порядка?

В своем основном виде задача составления расписания называется топологической сор­тировкой (topological sorting); при ее решении особых трудностей не возникает, как мы сможем убедиться в следующем разделе, в котором предлагаются два алгоритма ее реше­ния. В более сложных практических приложениях нам, возможно, придется накладывать дополнительные ограничения на то, как следует составлять расписание решения задач, и сложность топологической сортировки, естественно, возрастает. Например, задачи могут соответствовать курсам лекций в расписании занятий студентов, а частичный порядок может определяться некоторыми предварительными условиями. Топологическая сорти­ровка дает реальное расписание курса, удовлетворяющее предварительным условиям, но, по-видимому, не такое, какое учитывало бы другие виды ограничений, которые непло­хо было бы добавить в модель, такие как конфликт курсов, ограничения на прием сту­дентов и т.д. Еще один пример: задачи могут быть частью некоторого производственного процесса, при этом частичный порядок представляет собой требования к последователь­ности, в которой выполняются конкретные процессы. Топологическая сортировка пред­лагает нам способ планирования задач, но, возможно, существует другой такой способ, требующий меньше времени и денег или других ресурсов, не учтенных в модели. В гла-