горитмы, приводящие к цели быстрее, чем алгоритмы для общего случая. Один пример такого рода доставляет задача, разбираемая в этом разделе; другие примеры - сводящиеся к задачам линейного программирования задача о кратчайшем пути между данной парой вершин (упражнение 25.5-4) и задача о максимальном потоке (упражнение 27.1-8).

В некоторых случаях целевая функция нас не интересует, а требуется найти хотя бы одно допустимое решение (feasible solution), то есть решение системы неравенств Ах Ь (или доказать, что таковых нет). Мы займемся именно задачей такого типа.

Системы ограничений на разности

Система ограничений на разности (system of difference constraints) - это система линейных неравенств Ах Ь, для которой в каждой строке матрицы А присутствуют ровно два ненулевых элемента, один из которых равен 1, а другой -1. Иными словами, все неравенства имеют вид

хг~ Xj 6,

где 1 i,j п и 1 0 т.

Например, задача нахождения 5-вектора ющего условию

удовлетворя-

/жД

х2 х3

Х4

\х5;

1

5 4 -1 -3

V-з/

равносильна системе линейных неравенств

х\ х\

х2 х3

Х4 Х4 х5 х5

х2 О, х5 -1, х5 1,

xi 5, xt 4, х3 -1, х3 -3, Х4 -3.

(25.4)

Одно из решений этой системы есть х = ( - 5,-3,0,-1,-4). Если ко всем компонентам вектора х прибавить одно и то же число, получится другое решение:

Рис. 25.9 Граф ограничений, соответствующий системе (25.4). В каждой вершине v, написано число S(vo, v,). Вектор х = ( - 5, -3, 0, -1, -4) является одним из решений системы (25.4).

Лемма 25.16

Если х = (xi,..., хп) - решение системы ограничений на разности и d - константа, то х = (х\ + d,..., хп + d) - решение той же системы.

Системы ограничений на разности возникают во многих приложениях. Например, жг- могут быть сроками начала различных работ при строительстве дома. Если х\ - срок начала рытья котлована под фундамент, а х2 - срок начала заливки фундамента, и если рытье котлована занимает 3 дня, то х\ - х2 -3.

Графы ограничений

Если система ограничений на разности представлена в виде Ах Ь, где А - т X га-матрица, удобно рассмотреть ориентированный граф, для которого А будет матрицей инцидентности (см. упражнение 23.1-7). Точнее говоря, мы сделаем не совсем это, а свяжем с системой взвешенный ориентированный граф G = (V,E), в котором V = {vo, v\,..., vn} (по одной вершине на каждое неизвестное плюс вершина г>о), а каждому неравенству xj - Xi Ьк соответствует ребро (иг-, Vj) с весом Ьк (несколько неравенств с одинаковой левой частью можно заменить одним, взяв минимум их правых частей). Кроме того, в графе имеются га ребер (г>о, v\), (г>о, v2),..., (t>o, vn) (каждое - веса 0). На рис. 25.9 изображен граф, соответствующий системе (25.4).

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

Теорема 25.17

Пусть G = (V, Е) - граф, соответствующий системе разностных ограничений с га неизвестными. Если он не содержит циклов отрицательного веса, то вектор

является решением системы. Если G содержит цикл отрицательного веса, то система разностных ограничений несовместна. Доказательство

Если цикла отрицательного веса нет, то все S(vo,Vj) явялются (конечными) числами и лемма 25.3 гарантирует, что числа жг- удовлетворяют всем неравенствам.

Если цикл отрицательного веса есть, то он не содержит вершины vo, поскольку ни одно ребро в эту вершину не входит, так что все ребра цикла соответствуют каким-то неравенствам системы. Складывая неравенства, соответствующие ребрам цикла, получим

(25.5)

(поскольку левые части неравенств цикла сокращаются) неравенство вида 06, где Ь < 0 - вес цикла. Следовательно, система несовместна.

Решение систем ограничений на разности

Теорема 25.17 показывает, что найти хотя бы одно решение системы ограничений на разности можно с помощью алгоритма Беллмана-Форда. Заметим, что цикл отрицательного веса, если он есть, обязательно достижим из вершины vq (поскольку из vq идут стрелки во все остальные вершины), так что система несовместна тогда и только тогда, когда алгоритм Беллмана-Форда возвращает значение false.

Система то разностных ограничений с га неизвестными порождает граф с га + 1 вершиной и не более чем га + то ребрами. Поэтому найти хотя бы одно решение можно за время О ((га + 1)(га + то)) = О (га2 + тога). В упражнении 25.5-5 мы попросим вас доказать, что можно модифицировать этот алгоритм таким образом, чтобы он находил решение или устанавливал несовместность системы за время О (тога).

Упражнения

25.5-1 Найдите хотя бы одно решение или установите несовместность следующей системы неравенств:

25.5-2 То же задание, что в предыдущем упражнении, для систе-