Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Перспективы
|
|
Существуют четыре причины, в силу которых проводимые нами исследования алгоритмов достигают своей кульминации при изучении алгоритмов вычисления сетевых потоков. Во-первых, модель потоков в сети придает законную силу практическому применению абстракции графа в бесчисленных приложениях. Во-вторых, изученные нами алгоритмы вычисления максимальных потоков и потоков с минимальной стоимостью, суть естественные расширения алгоритмов на графах, изученные нами на примерах простых задач. В третьих, программные реализации этих алгоритмов показывают, сколь важную роль играют фундаментальные алгоритмы и структуры данных для достижения высокой производительности. В четвертых, модели максимальных потоков и потоков с минимальной стоимостью служат примерами применения подхода разработки все более общих моделей решения задач и их использования для решения широких классов задач. Наша способность разрабатывать эффективные алгоритмы, обеспечивающие решение таких задач, оставляет нам открытой возможность разработки еще более общих моделей, решающих такие задачи.
Прежде чем переходить к более детальному рассмотрению этих проблем, подготовим дальнейший контекст, перечислив важные задачи, которые нам не удалось изучить в этой главе, даже несмотря на то что они очень тесно связаны с известными задачами.
Задача о максимальном сочетании (maximum matching). В графах со взвешенными ребрами найти подмножество ребер, в котором ни одна из вершин не появляется больше одного раза и суммарный вес которых таков, что никакое другое множество ребер не имеет большего суммарного веса. Мы можем свести задачу о сочетании с максимальным кардинальным числом (maximum cardinality matching) в невзвешенных графах непосредственно к этой задаче, установив всем ребрам веса, равные 1.
Задача о назначениях и задача о сочетании с максимальным кардинальным числом сводятся к задаче максимального сочетания для графов общего вида. С другой стороны, максимальное сочетание не сводится к потокам минимальной стоимости, поэтому и рассмотренные выше алгоритмы к ней не применимы. Эта задача относится к числу решаемых, хотя объем вычислений в случае крупных графов, довольно-таки велик. Рассмотрение многочисленных методов, предложенных в попытках решить задачу сочетания на графах общего вида, заняло бы целый том: эта проблема относится к числу наиболее интенсивно исследуемых в теории графов. В этой книге мы подвели черту под потоком минимальной стоимости, но мы вернемся к задаче о максимальном сочетании в части 8.
Задача о многопродуктовом потоке (multicommodity flow). Предположим, что нам нужно вычислить второй поток, такой, что сумма обоих потоков в ребре ограничена пропускной способностью ребра, оба потока находятся в равновесии и их суммарная стоимость минимальна. Такое изменение моделирует наличие двух различных типов материалов в задаче о распределении товаров (merchandise-distribution problem); например, следует ли
Часть 5. Алгоритмы на графах
нам загрузить больше гамбургеров или больше картошки в грузовую машину, направляющуюся в ресторан быстрого питания? Подобного рода изменения делают эту задачу более трудной и требуют более совершенных алгоритмов ее решения, нежели рассмотренные в этой книге; например, не известен ни один аналог теоремы о максимальном потоке минимальной стоимости, который выполняется в общем случае. Постановка этой задачи как LP-задачи есть простое расширение примера, представленного на рис. 22.53, следовательно, эта задача относится к числу решаемых (поскольку решаема LP-задача).
Выпуклость и нелинейные стоимости. Простые функции стоимости, которые мы рассматриваем, представляют собой линейную комбинацию некоторых переменных, а используемые нами алгоритмы для их решения существенно зависят от простых математических структур, лежащих в их основе. Например, когда мы минимизируем расстояния, мы имеем дело с суммами квадратов стоимостей. Такие задачи не могут быть сформулированы как LP-задачи, они требуют специальных моделей решения задач, которые обладают еще большими возможностями. Многие из этих задач не принадлежат к числу легко решаемых.
Задачи календарного планирования (составления расписаний). В качестве примеров мы рассмотрели несколько таких задач. Они являются представителями нескольких сот различных задач календарного планирования. Научно-исследовательская литература изобилует описаниями исследований отношений между этими задачами и разрабатываемыми алгоритмами их решения и соответствующими программными реализациями (см. раздел ссылок). В самом деле, мы могли бы воспользоваться алгоритмами составления расписаний вместо алгоритмов вычисления потоков в сетях, чтобы разрабатывать идеи, обеспечивающие построение обобщенных моделей решения задач, и реализации сведения конкретных задач к этой модели (то же самое можно сказать и о соответствии). Многие задачи составления расписания приводятся к модели потока минимальной стоимости.
Возможности комбинаторных вычислений поистине велики, поэтому изучение задач подобного типа, несомненно, будут занимать умы исследователей еще многие и многие годы. Мы вернемся к некоторым из этих задач в части 8, в контексте поиска решений трудно решаемых задач.
Мы ознакомились лишь с небольшой частью исследованных алгоритмов решения задач о максимальных потоках и о потоках минимальной стоимости. Как было показано в упражнениях на протяжении данной главы, комбинации многочисленных их вариантов при их использовании в различных частях алгоритмов общего вида порождает широкое множество самых разнообразных алгоритмов. Алгоритмы и структуры данных для базовых вычислительных задач играют важную роль в обеспечении эффективности многих из этих подходов; и в самом деле, некоторые важные алгоритмы общего назначения, с которыми мы ознакомились, были разработаны во время поиска эффективной реализации алгоритма вычисления потоков в сети. Эта тема все еще находится в центре внимания многих разработчиков. Разработка все более совершенных алгоритмов решения задач вычисления потоков в сетях, несомненно, зависит от правильного использования базовых алгоритмов и структур данных.
Широкая область применения алгоритмов вычисления потоков в сети и экстенсивное использование метода сведения к другим задачам с целью еще большего расширения этой области заставляют нас рассмотреть здесь некоторые последствия применения понятия