189
правок
Изменения
Нет описания правки
}}
==Время работы==
[[Файл:Figure_5.9.a.png|400px200px|thumb|right|Рис. 2.1]]
[[Файл:Figure_5.9.b.png|400px|thumb|right|Рис. 2.2]]
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности.
Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Это дает <tex>\varepsilon</tex>-приближении алгоритм со сложностью <tex>O (mn^3(log(n) + log(1 / \varepsilon) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма.
Задача <tex>Q | pmtn; ri | Cmax</tex>, которая представляет собой частный случай <tex>Q | pmtn; ri | Lmax</tex>, может быть решена более эффективно. Labetoulle, Lawler, Lenstra, and Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов. Это вытекает из следующих соображений:
Решение <tex>Q | pmtn; ri | Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, что проблема с временными окнами [г, т] (г = 1, ..., п) имеет возможности решение.
С другой стороны, решение <tex>Q | pmtn | Lmax</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение.
Таким образом, задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax</tex> симметричны.
