![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. ния задач о потоках в сетях, рассматриваемые далее алгоритмы решения задач о потоках в сети намного проще и эффективнее
Классическое решение задач о потоках в сетях тесно связаны с другими, уже изученными, алгоритмами на графах, и мы можем писать удивительно компактные программы их решения, воспользовавшись разработанными ранее алгоритмическими инструментами. Как мы могли убедиться во множестве других ситуаций, качественные алгоритмы и структуры данных иногда позволяют существенно уменьшить время выполнения программ. Изучение методов разработки более совершенных реализаций классических алгоритмов, способных решать обширные классы задач, продолжается, и время от времени появляются новые подходы. В разделе 22.1 мы проведем исследование свойств транспортных сетей (flow networks), в рамках которого мы интерпретируем веса ребер как пропускные способности (capacities) и рассматриваем свойства потоков (flows), представленные вторым множеством весов ребер, которые удовлетворяют некоторым естественным условиям. Далее мы рассмотрим задачу о максимальном потоке, которая заключается в вычислении лучшего в некотором специальном техническом смысле потока. В разделах 22.2 и 22.3 мы рассмотрим два подхода к решению задачи о максимальном потоке и изучим некоторое множество различных реализаций ее решения. Многие из алгоритмов и структур данных, которые мы рассматривали ранее, непосредственно зависят от разработки эффективного решения задачи о максимальном потоке. У нас еще нет наилучшего из возможных алгоритмов решения задачи о максимальном потоке, поэтому мы пока рассмотрим конкретные решения, используемые на практике. Чтобы продемонстрировать масштабность и разноплановость задачи поиска максимального потока, в разделе 22.4 мы рассмотрим другие формулировки этой задачи, равно как и возможность ее сведения к другим задачам. Алгоритмы решения задачи о максимальном потоке и их реализации подготавливают нас к обсуждению более важной и более общей задачи о потоке минимальной стоимости, по условиям которой мы присваиваем ребрам стоимости (еще одно множество весов ребер) и определяем стоимости потоков, когда ищем решение задачи о максимальном потоке, обладающем минимальной стоимостью. Мы рассмотрим классическое общее решение задачи о потоке минимальной стоимости, известное как алгоритм вычеркивания циклов (cycle-canceling algorithm), а затем, в разделе 22.6, дадим конкретную реализацию алгоритма вычеркивания циклов, известную как сетевой симплексный алгоритм. В разделе 22.3 мы обсудим все сведения к задаче о потоке минимальной стоимости, которые включают, помимо прочих, все приложения, которые отмечались выше. Алгоритмы решения задачи о потоках в сети представляют собой тему, подходящую для завершения данной книги, сразу по нескольким причинам. Упомянутая тема является как бы вознаграждением за усилия, потраченные на изучение базовых алгоритмических инструментальных средств, таких как связные списки, очереди с приоритетами и общие методы поиска на графах. Классы, осуществляющие обработку графов, которые изучались в этой книге, непосредственно приводят к компактным и эффективным реализаци- Часть 5. Алгоритмы на графах
|