Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути
|
|
В начале этой главы мы обрисовали аргументацию, показывающую, что задача нахождения кратчайших путей в неориентированных взвешенных графах сводится к задаче нахождения кратчайших путей в сетях, так что наши алгоритмы для сетей можем использовать для решения задач поиска кратчайших путей в неориентированных взвешенных графах. В этом контексте имеет смысл рассмотреть два дополнительных замечания, касающихся сведения. Во-первых, обратное утверждение не справедливо: знание того, как решить задачи кратчайших путей в неориентированных взвешенных графах, не помогает решать их в сетях. Во-вторых, мы видим дефект в аргументации: если бы веса ребер могли быть отрицательными, сведение привело бы к сети с отрицательными циклами, а мы не знаем, как искать в них кратчайшие пути. Даже если сведение завершается аварийно, все еще может оказаться возможным с помощью неопределенно сложного алгоритма отыскать кратчайшие пути в неориентированных взвешенных графах без отрицательных циклов {см. раздел ссылок). Поскольку эта задача не сводится к направленной версии, данный алгоритм бесполезен при решении задачи поиска кратчайшего пути в сетях общего вида.
Концепция сведения, по существу, описывает процесс использования одного АТД для реализации другого, как это обычно делается современными системными программистами. Если две задачи эквивалентны, то известно, что если есть возможность эффективно решить какую-то из них, то можно эффективно решить и другую. Мы часто находим простые взаимно однозначные соответствия, такие как, например, в свойстве 21.13, где показана эквивалентность двух задач. В этом случае, даже до обсуждения способа решения каждой из задач, очень важен тот факт, что если удается отыскать эффективное решение одной задачи, то оно применимо и для решения другой. Еще один пример приводился в главе 17: когда мы встретились с задачей определения, имеет ли граф нечетный цикл, то обратили внимание, что данная задача эквивалентна определению, можно ли раскрасить этот граф двумя цветами.
Сведение имеет два основных применения в проектировании и анализе алгоритмов. Во-первых, оно помогает классифицировать задачи по их сложности на соответствующем абстрактном уровне без обязательной разработки и анализа полной реализации. Во-вторых, сведения часто делаются для установки нижних границ трудности решения различных задач, дабы получить понятие, когда прекращать поиск лучших алгоритмов. Мы видели примеры использования упомянутых приемов в разделах 19.3 и 20.7; позже в этом разделе будут рассматриваться и другие применения концепции сведения.
Помимо этой ориентации на практическое использование, принцип сведения также широко распространен в самой теории вычислений (со всеми вытекающими последствиями). Эти результаты важны потому, что позволяют понять, насколько возрастает трудность наших задач. Эта тема вкратце обсуждается в конце настоящего раздела, а вот подробно и совершенно формально - в части 8.
То, что стоимость преобразований не должна доминировать, является естественным фактором, который часто принимается во внимание. Во многих случаях, тем не менее, можно было бы принять решение использовать сведение даже при том, что стоимость преобразований оказывается действительно большой. Одно из наиболее важных применений концепции сведения заключается в преобразовании к понятной задаче, для которой известно эффективное решение, что обеспечивает эффективные решения таких задач, которые противном случае пришлось бы отнести к классу трудноразрешимых.
Часть 5. Алгоритмы на графах
Сведение А к В, даже если выполнение этих преобразований обойдется намного дороже, чем собственно решение В, может дать намного более эффективный алгоритм решения, чем тот, который мы могли бы придумать другим путем. Может существовать множество различных вариантов. Возможно, в большей степени важен фактор средней ожидаемой стоимости, нежели фактор стоимости для худшего случая. Возможно, для решения А потребуется решить две задачи, В и С. Может быть, необходимо многократно решать задачу В. Мы оставляем дальнейшее обсуждение таких вариантов до части 8, поскольку все примеры, которые мы рассмотрим к тому времени, являются упрощенными вариантами только что упомянутых примеров.
В частности, когда мы решаем задачу А, упрощая другую задачу В, мы знаем, что А можно свести к B но не обязательно наоборот. Например, выбор сводится к сортировке, поскольку есть возможность отыскать наименьший k -тый элемент в файле с помощью сортировки файла и затем перейти по индексу (или последовательно) в к-тую позицию; тем не менее, из этого факта, конечно же, не следует, что сортировка сводится лишь только к выбору. В данном контексте как задача поиска кратчайших путей для взвешенного DAG, так и задача поиска кратчайших путей для сетей с положительными весами сводятся к общей задаче вычисления кратчайших путей. Такое использование сведения соответствует интуитивному понятию некоторой более общей задачи. Любой алгоритм сортировки решает любую задачу выбора и, если можно решить задачу поиска кратчайших путей на сетях общего вида, то, разумеется, можно воспользоваться этим решением для сетей с различными ограничениями. Естественно, обратное утверждение не обязательно будет верным.
Подобное применение концепции сведения полезно, однако сама идея становится более полезной, если использовать ее для получения информации о взаимосвязях между задачами в различных областях. Например, рассмотрим следующие задачи, которые на первый взгляд кажутся далекими от обработки графов. При помощи сведения можно прояснить определенные взаимоотношения между этими задачами и задачей поиска кратчайших путей.
Календарное планирование. Пусть необходимо выполнить большой набор работ с разными продолжительностями. Мы можем выполнять любое количество работ одновременно, однако для каждой пары работ существует множество отношений предшествования, которые регламентируют, какая из работ должна быть завершена до того, как можно будет начать следующую работу. Каково минимальное время, которое необходимо для завершения всех работ, при условии выполнения всех ограничений предшествования? А именно, для данного набора работ (с указанием длительности каждой работы) и набора ограничений предшествования, требуется составить такой календарный план из выполнения (найти момент начала для каждой работы), чтобы достичь упомянутого выше минимума.
На рис. 21.22 приведен пример задачи календарного планирования. Здесь используется естественное представление в виде сети, которое в данном случае служит базой для сведения. Этот вариант задачи является, возможно, наиболее простым из буквально сотен вариантов, которые служили предметом исследований, т.е. вариантов, включающих другие характеристики работ и другие ограничения, подобные назначению работам персонала или других ресурсов, определению различных расходов, связанных с работами, конечных сроков выполнения и т.п. В этом контексте описанный выше вариант обычно
Глава 21. Кратчайшие пути
|
называется календарным планированием с ограничением предшествования и произвольным параллелизмом. Для краткости в дальнейшем будет применяться термин календарное планирование.
Для упрощения разработки алгоритма, решающего задачу планирования работ, мы рассмотрим следующую задачу, которая представляет интерес и сама по себе.
| РИСУНОК 21.22. КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ В этой сети вершины представляют работы, которые требуется выполнить (с весами, указывающими суммарное требуемое время), а ребра — отношения предшествования между работами. Например, ребра из 7 в 8 и в 3 означают, что работа 1 должна быть завершена перед тем, как может быть начата работа 8 или работа 3. Каково минимальное время, необходимое для завершения всех работ? |
Разностные ограничения. Присвоить неотрицательные значения множеству переменных от х0 до хп с целью минимизации значения хп при наличии множества ограничений на разность переменных, каждое из которых определяет, что разность между двумя этими переменными должна быть больше или равна заданной константе.
На рис. 21.23 показан пример задачи такого типа. Здесь представлена исключительно абстрактная математическая формулировка, которая может послужить основой для решения многих практических задач (см. раздел ссылок).
Задача разностных ограничений является частным случаем гораздо более общей задачи, где в уравнениях допускаются произвольные линейные комбинации переменных.
Линейное программирование. Присвоить неотрица-
тельные значения множеству переменных от х0 до хn с целью минимизации значения заданной линейной комбинации переменных при наличии множества ограничений на переменные, каждое из которых определяет, что заданная линейная комбинация переменных должна быть больше или равна заданной константе.
Линейное программирование является хорошо известным общим подходом к решению широкого класса задач оптимизации, поэтому мы не будем подробно его обсуждать, отложив это до части 8. Очевидно, что, как и многие другие задачи, задача разностных ограничений сводится к линейному программированию. В данный момент наши интересы сосредоточены на взаимосвязях между разностными ограничениями, календарным планированием работ и задачами поиска кратчайших путей.
Свойство 21.14. Задана планирования работ сводится к задаче разностных ограничений.
Доказательство: Для каждой работы добавим фиктивную работу и ограничения предшествования таким образом, чтобы данная работа должна была закончиться перед тем, как начнется фиктивная работа. Для этой задачи календарного планирования работ определим систему неравенств в конечных разностях, где каждой работе i соответствуют переменная xh и ограничение, согласно которому у не может начаться, пока не закончится i, в соответствии с неравенством х, > х, - + ci где ci, есть продолжительность работы i. Решение задачи разностных ограничений дает точное решение задачи планирования работ, со значением каждой переменной, задающим время начала соответствующей работы. ■
Рисунок 21.23 иллюстрирует систему неравенств в конечных разностях, создаваемых этим сведением для задачи планирования работ из рис. 21.22. Практическое значение этого
Часть 5. Алгоритмы на графах
| положительных константах эквивалентна задаче поиска наиболее длинных путей для единственного источника в ациклической сети. Доказательство: Для заданной системы уравнений в конечных разностях построим сеть, где каждая переменная хi, соответствует вершине i и каждое неравенство хi — хj > с соответствует ребру i-j веса с. Например, назначение каждому ребру в орграфе на рис. 21.22 веса исходной вершины дает сеть, соответствующую набору неравенств в конечных разностях на рис. 21.23. Добавим фиктивную вершину к сети с ребрами нулевого веса, направленными в каждую из остальных вершин. Если сеть имеет цикл, то система уравнений в конечных разностях не имеет решения (поскольку из положительности весов следует, что значения переменных, соответствующих каждой вершине, строго уменьшаются по мере продвижения вдоль пути и, следовательно, цикл покажет, что некоторая переменная меньше себя самой). Иначе, если сеть не имеет цикла, мы решаем задачу поиска наиболее длинных путей для единственного источника в фиктивной вершине. Для каждой вершины существует наиболее длинный путь, поскольку сеть является ациклической (см. раздел 21.4). Присвоим каждой переменной длину наиболее длинного пути из фиктивной вершины в соответствующую |
сведения состоит в том, что для решения задачи планирования работ можно воспользоваться любым алгоритмом, позволяющим решить задачи разностных ограничений.
Полезно рассмотреть вопрос, можно ли провести аналогичное построение в обратном направлении: если задан алгоритм планирования работ, то можно ли воспользоваться им для решения задачи разностных ограничений? Ответ на этот вопрос состоит в следующем: доказательство свойства 21.14 не позволяет показать, что задача разностных ограничений сводится к задаче планирования работ, поскольку системы неравенств в конечных разностях, которые получаются из задачи календарного планирования, имеют свойства, которые не обязательно сохраняются для каждой задачи разностных ограничений. А именно, если два неравенства имеют одинаковые вторые переменные, то они имеют те же самые константы. Следовательно, алгоритм для календарного планирования работ непосредственно не дает прямого пути решения системы неравенств в конечных разностях, которая содержит два таких неравенства: x i — xj> a и хк — x j > b, где а≠ b. Проверяя возможность сведения, следует иметь в виду ситуации, подобные следующей: при доказательстве возможности сведения А к В необходимо показать, что мы можем использовать алгоритм решения задачи В для решения любого варианта задачи А
Конструктивно константы в задачах с разностными ограничениями, создаваемые построением при доказательстве свойства 21.14, всегда являются неотрицательными. Этот факт имеет существенное значение.
Свойство 21.15. Задача с разностными ограничениями при
РИСУНОК 21.23. РАЗНОСТНЫЕ ОГРАНИЧЕНИЯ
Нахождение неотрицательных значений, присваиваемых переменным, при которых с учетом данного множества неравенств минимизируется значение х10, эквивалентно варианту задачи календарного планирования работ, который показан на рис. 21.22. Например, неравенство х8 > х7 + 0.32 означает, что работа 8 не может начаться, пока выполняется работа 7.
Глава 21. Кратчайшие пути
вершину в данной сети. Очевидно, что для каждой переменной значение этого пути удовлетворяет ограничениям, но никакое меньшее значение ограничениям не удовлетворяет.
В отличие от доказательства свойства 21.14, данное доказательство направлено на то, чтобы показать, что данные две задачи эквивалентны, поскольку построение работает в обоих направлениях. Мы не накладываем того ограничения, что два неравенства с одинаковыми вторыми переменными в неравенстве должны иметь одни и те же константы, и нет ограничений на то, чтобы ребра, исходящие из любой заданной вершины в сети, имели одни и те же веса. Для любой заданной ациклической сети с положительными весами такое же соответствие дает систему разностных ограничений с положительными константами, решение которой непосредственно приводит к решению задачи поиска наиболее длинных путей для единственного источника в сети. Детали этого доказательства оставляем на самостоятельную проработку (см. упражнение 21.90). ■
В сети на рис. 21.22 это соответствие показано для нашей типовой задачи, а на рис. 21.15 демонстрируется вычисление наиболее длинных путей в сети с использованием программы 21.6 (фиктивная начальная вершина скрыта в реализации). Календарный план, который вычисляется этим способом, приведен на рис. 21.24.
Программа 21.8 представляет собой реализацию, которая является примером применения рассмотренной теории к практической задаче. Она позволяет представить любой образец задачи календарного планирования работ как образец задачи поиска наиболее длинного пути в ациклических сетях, а затем использует программу 21.6 для ее решения.
Программа 21.8. Календарное планирование
РИС. 21.24. КАЛЕНДАРНЫЙ ПЛАН
Этот рисунок иллюстрирует решение задачи планирования работ из рис. 21.22, полученное из соответствия между задачей о наиболее длинных путях во взвешенном DAG и задачей календарного планирования. Длины наиболее длинных путей в массиве wt, которые вычисляются по алгоритму поиска наиболее длинных путей в программе 21.6 (см. рис. 21.15), есть в точности необходимые времена начала работ (правая колонка сверху). Мы начинаем работы 0 и 5 в момент 0, работы 1, 7 и 9 — в момент 0.41, работы 4 и б — в момент 0, 70 и т.д.
Эта реализация читает из стандартного ввода список работ с их длительностями, за которым следует список ограничений предшествования, затем выводит на стандартный выход список начальных времен работ, которые удовлетворяют данным ограничениям. Используя свойства 21.14 и 21.15, а также программу 21.6, она решает задачу календарного планирования работ за счет сведения ее к задаче поиска наиболее длинных путей для ациклических сетей.
#include " GRAPHbasic.cc" #include " GRAPHio.cc" #include " LPTdag.cc" typedef WeightedEdge EDGE; typedef DenseGRAPH< EDGE> GRAPH;
Часть 5. Алгоритмы на графах
int main(int argc, char *argv[]) { int i, s, t, N = atoi(argv[1]); double duration[N]; GRAPH G(N, true); for (int i = 0; i < N; i++)
cin» duration[i]; while (cin» s» t)
G.insert(new EDGE(s, t, duration[s])); LPTdag< GRAPH, EDGE> lpt(G); for (i = 0; i < N; i++)
cout «i «" " «lpt.dist(i) «endl; }
Неявно мы предполагали, что решение существует для любой постановки задачи календарного планирования работ; тем не менее, если во множестве ограничений предшествования имеется цикл, то не существует способа составления расписания работ, удовлетворяющего таким ограничениям. Перед тем, как искать наиболее длинные пути, мы должны проверить выполнение этого условия путем проверки, имеет ли соответствующая сеть цикл (см. упражнение 21.100). Данная ситуация является типичной, и для ее описания обычно используется специальный технический термин.
Определение 21.4. Говорят, что экземпляр задачи, который не допускает никакого решения, является невыполнимым.
Другими словами, для задач планирования работ вопрос определения, является ли некоторый экземпляр задачи планирования выполнимым, сводится к задаче определения, является ли орграф ациклическим. Поскольку мы продвигаемся ко все более сложным задачам, вопрос разрешимости становится все более важной (и более трудной!) частью затрат вычислительных ресурсов.
К данному моменту мы рассмотрели три взаимосвязанных задачи. Можно было бы показать непосредственно, что задача планирования работ сводится к задаче поиска наиболее длинных путей для единственного источника в ациклических сетях, однако мы также показали, что подобным же образом можно решить любую задачу разностных ограничений (с положительными константами) (см. упражнение 21.94), равно как и любую другую задачу, которая сводится к задаче разностных ограничений или задаче планирования работ. С другой стороны, можно было бы разработать алгоритм для решения задачи разностных ограничений и воспользоваться им для решения других задач, но мы не показали, что решение задачи календарного планирования работ могло бы дать способ решения других задач.
Эти примеры иллюстрируют использование сведения, которое позволяет расширить область применимости проверенных реализаций. Действительно, при построении реализаций современное системное программирование делает упор на необходимости многократного использования программного обеспечения за счет разработки новых интерфейсов и использования ресурсов существующего программного обеспечения. Этот важный процесс, который иногда называется библиотечным программированием, является практическим воплощением концепции сведения.
Библиотечное программирование представляется чрезвычайно важным в практическом отношении, однако оно составляет только часть последствий применения сведения. Что-
Глава 21. Кратчайшие пути
бы иллюстрировать это замечание, рассмотрим следующую версию задачи календарного планирования работ.
Планирование работ с конечными сроками завершения. Допускает в задаче планирования работ ограничения дополнительного типа, которые определяют, что работа должна начаться до истечения заданного промежутка времени относительно другой работы. (Условные конечные сроки отсчитываются относительно начальной работы.) Такие ограничения обычно требуются в критичных ко времени производственных процессах и во множестве других приложений; разумеется, они могут существенно затруднить решение задачи календарного планирования работ.
Предположим, что нам нужно добавить ограничение к примеру, представленному на рис. 21.22-21.24, состоящее в том, что работа 2 должна начинаться не позже заданного количества временных единиц с после начала работы 4. Если с больше 0.53, то построенное расписание укладывается в заданные рамки, поскольку оно предписывает начать работу 2 в момент времени 1.23, что соответствует задержке на 0.53 после окончания работы 4 (которая начинается в 0.70). Если с меньше 0.53, то можно сдвинуть начало работы 4 на более позднее время, дабы удовлетворить это ограничение. Если работа 4 является достаточно длинной, то это изменение могло бы увеличить время завершения всего календарного графика. Хуже, если существуют другие ограничения на работу 4 и мы не можем переместить время ее начала. Действительно, могут встретиться ограничения, которые не может удовлетворить ни одно расписание: например, в нашем примере не удалось бы удовлетворить такие ограничения, при которых работа 2 должна начаться раньше, чем через d единиц времени после начала работы 6, для d меньшего 0.53, поскольку из ограничения, что за 2 должна следовать 8 и за 8 должна следовать 6, следует, что 2 должна начаться позже, чем через.53 единицы времени после начала 6.
Если добавить в пример оба ограничения, рассмотренные в предыдущем абзаце, то, в зависимости от значений c u d, каждое ограничение окажет влияние на время, когда 4 может быть поставлена в расписание, на время завершения всего графика, а также на то, существует ли выполнимый календарный график. Добавление дополнительных ограничений подобного типа увеличивает число возможностей и превращает легкую задачу в трудноразрешимую. Следовательно, при поиске подхода к решению задачи имеются все основания сводить ее к некоторой известной задаче.
Свойство 21.16. Задана календарного планирования работ с конечными сроками завершения сводится к задаче поиска кратчайших путей (с возможностью существования отрицательных весов).
Доказательство: Преобразуем ограничения предшествования к неравенствам, используя то же сведение, что и описанное в свойстве 21.14. Для каждого ограничения конечного срока добавим неравенство хi, — хj < dj или, что эквивалентно, хj — хi, - > -dj где d j есть положительная константа. Преобразуем набор неравенств в сеть, применив то же сведение, что и описанное в свойстве 21.15. Изменим все веса на отрицательные. С помощью того же построения, что и при доказательстве свойства 21.15, можно показать, что любое дерево кратчайшего пути в сети с корнем в 0 будет соответствовать расписанию. ■
Это сведение подводит нас к вопросу о кратчайших путях с отрицательными весами. Оно основано на том, что, если можно найти эффективное решение задачи поиска крат-
Часть 5. Алгоритмы на графах
чайших путей с отрицательными весами, то можно отыскать и эффективное решение задачи планирования работ с конечными сроками завершения. (Опять-таки, соответствие в доказательстве свойства 21.16 не допускает обратное утверждение (см. упражнение 21.91).)
Добавление конечных сроков к задаче планирования работ соответствует допущению отрицательных констант в задаче с разностными ограничениями и отрицательным весам в задаче о кратчайших путях. (Это изменение также требует модификации задачи разностных ограничений, чтобы должным образом рассмотреть аналог отрицательных циклов в задаче о кратчайших путях.) Эти более общие варианты задач более трудноразрешимы, чем те варианты, которые мы рассматривали вначале, но, по всей видимости, они также и более полезны как обобщенные модели. Приемлемое приближение к решению всех их, скорее всего, следует искать в эффективном решении задачи поиска кратчайших путей с отрицательными весами.
К сожалению, с этим подходом связана принципиальная трудность, и она иллюстрирует другую сторону вопроса использования сведения, позволяющую оценить относительную трудность задач. Мы уже задействовали положительные свойства сведения для расширения применимости решений общих задач, однако оно обладает также и отрицательными сторонами, показывающими ограниченность возможности такого расширения.
Эта трудность заключается в том, что решение общей задачи поиска кратчайших путей слишком сложно. Далее мы увидим, как с помощью концепции сведения сформулировать данное утверждение точно и обоснованно. В разделе 17.8 было рассмотрено множество задач, известных как NP-трудные, которые мы посчитали неразрешимыми, поскольку все известные алгоритмы для их решения в худшем случае требуют экспоненциального времени. Сейчас будет показано, что в общем случае задача поиска кратчайших путей является NP-трудной.
Как кратко упоминалось в разделе 17.8 и подробно обсуждается в части 8, в общем случае, когда мы утверждаем, что задача является NP-трудной, это означает не только то, что не известно эффективного алгоритма, гарантирующего решение этой задачи, но также и то, что все-таки остается некоторая надежда отыскать таковой. В этом контексте мы используем термин эффективный, ссылаясь на алгоритмы, время счета которых ограничено в худшем случае некоторой полиномиальной функцией значения входной переменной. Мы предполагаем, что открытие эффективного алгоритма решения любой NP-трудной задачи должно быть ошеломляющим научным достижением. Концепция NP-трудности является важной для трудноразрешимых задач идентификации, поскольку часто легко доказать, что задача NP-трудна, используя следующую методику.
Свойство 21.17. Задана является NP-трудной, если существует любая NP-трудная задача, эффективно сводящаяся к ней.
Это свойство зависит от строгого определения эффективного сведения одной задачи Л к другой задаче В. Мы откладываем такие определения до части 8 (обычно применяются два различных определения). В данный момент мы просто используем этот термин, чтобы описать случай, когда существуют эффективные алгоритмы как для преобразования образца А к образцу B так и для преобразования решения В к решению Л.