Основные задачи и методы их решения

Критическим путем в ориентированном графе G =(X, U) с источником s и стоком t называется самый длинный путь максимальной длины

m[ s, t ] между этими вершинами. Если кратчайший путь в орграфе не существует при наличии контуров отрицательной длины, то критический путь не существует в ориентированном графе с контурами [1].

Таким образом, задача поиска критического пути в графе G =(X, U) имеет решение только в том случае, если этот граф является бесконтурным. Понятие "критический путь" является фундаментальным для методов PERT и CPM управления выполнением проекта и соответствует минимальному времени, необходимому для реализации проекта (см. раздел 1.5). Самый длинный путь m[ s, t ] в сети PERT или CPM называется критическим, так как дуги (x_i, x_j)Îm[ s, t ] отображают этапы операции проекта, для которых любая задержка начала выполнения приводит к увеличению срока завершения проекта в целом.

Совершенно очевидно сходство задачи поиска критического пути с задачей о кратчайшем пути между источником и стоком. Ее можно решить с помощью любого алгоритма построения кратчайшего пути из раздела 1. Для этого используется два подхода:

- модификация графовой модели задачи;

- модификация алгоритма поиска пути.

В первом случае изменяются веса l (x_i, x_j) всех дуг (x_i, x_j) Î U исходного графа G =(X, U) на значения l '(x_i, x_j) = - l (x_i, x_j) или l '(x_i, x_j) = 1/(x_i, x_j). Затем применяется любой алгоритм поиска кратчайшего пути без каких-либо изменений. Результат будет определять критический путь в исходном графе G =(X, U).

Второй способ предполагает модификацию применяемого алгоритма. Для этого все операции min заменяются на max, а значения элементов d_ij = ¥ матрицы весов D (c _ij = ¥ для матрицы C в алгоритме Флойда), где (x_i, x_j) Ï U, заменяются на d ' _ij = -¥ и c ' _ij = -¥ соответственно. Необходимо отметить, что при поиске критического пути m[ s, t ] изменяется смысл пометок l^*(x_i) и g^*(x_i) вершин графа. Значение l^*(x_i) определяет длину максимального пути m[ s, x_i ] от источника s до вершины x_i, а g^*(x_i) - длину максимального пути m[ x_i, t ] от x_i до стока t.

Учитывая различную трудоемкость алгоритмов поиска кратчайших путей и обязательное отсутствие контуров в графовых моделях, наиболее целесообразным для определения критического пути m[ s, t ] является применение метода динамического программирования. В качестве примера модификации алгоритма ниже приводится процедура поиска критического пути методом динамического программирования, которая базируется на использовании пометок l(x_i) вершин графа.

Алгоритм 2.1 (поиск критического пути m [ s,t ] методом динамического программирования)

Данные: бесконтурный граф G = (X, U) с n вершинами, имеющими правильную нумерацию; выделенные источник s = x ₁ и сток t; произвольные веса дуг l (x_i, x_j).

Результат: длина l^*(t) критического пути m[ s, t ].

Шаг 1 (присвоение начальных значений)

Задать пометки l^*(x ₁)= -¥ вершинам x_i Î X \ s и l^*(x ₁)= 0 для s = x ₁. Присвоить j =1.

Шаг 2 (изменение пометок)

Присвоить j = j +1 и для вершины x_j вычислить окончательное значение пометки

(2.1)

где T = Г^-1(x_j). При T =Ø пометка вершины x_j не изменяется.

Шаг 3 (проверка условия окончания)

Если x_j = t, то конец алгоритма. Иначе переход к шагу 2.

Очевидно, что выражение (2.1) обеспечивает корректный результат только при правильной нумерации вершин графа (см. раздел 1.5), для которой индексы вершин любой дуги (x_i, x_j)Î U удовлетворяют условию i < j. Построение критического пути m[ s, t ] может быть выполнено на основе известного соотношения (1.2) или с помощью двойных пометок вида [l^*(x_j), m_j ], где l^*(x_j) - длина максимального пути от источника s до вершины x_j.

Наиболее близким к задаче поиска критического пути на графе являются следующие задачи:

- определить пути m[ s, x_j ] максимальной длины от источника s = x ₁ до всех других вершин x_j Î X \ s;

- определить пути m[ s, t ] максимальной длины от всех вершин x_i Î X \ t; до стока t = x_n;

- определить пути максимальной длины m[ x_i, x_j ] между всеми парами вершин x_i, x_j Î X.

Для решения первых двух задач успешно применяется метод динамического программирования (с пометками вершин l(x_i) и g(x_i) соответственно). Последняя задача может быть решена по алгоритму Флойда после необходимой модификации (см. выше).

У П Р А Ж Н Е Н И Я

2.1. Сформулировать задачу поиска критического пути в бесконтурном ориентированном графе в виде задачи целочисленного линейного программирования.

2.2. Почему при решении задачи поиска критического пути в графе не допускается существование контуров?

2.3. Перечислить основные методы определения путей максимальной длины в ориентированных бесконтурных графах.

2.4. Что показывают пометки l(x_i) и g(x_i), приписываемые вершинам графа в алгоритмах поиска путей максимальной длины?

2.5. Модифицировать алгоритмы Форда-Беллмана и Дейкстры для решения задачи поиска путей максимальной длины.

2.6. Составить программу для построения критичеcкого пути в ориентированном графе методом динамического программирования.

2.7.Определить по методу Дейкстры критический путь от источника s = x ₁ до стока t = x ₉ в графе, показанном на рис. 1.7.

2.8. Методом динамического программирования определить длину максимального пути от вершины x ₁ до вершины x ₈ для графа на рис. 1.8.

2.9. Разработать алгоритм построения путей максимальной длины между всеми парами вершин по методу Флойда.

2.10. Определить пути максимальной длины m[ x_i, x_j ] для всех пар вершин x_i и x_j в графе, приведенном на рис. 1.9.