![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. и мы исследуем их в этом разделе несколько позже, после того как рассмотрим реализации более подробно.
Первый выбор, с необходимостью которого мы столкнемся при разработке сетевого симплексного алгоритма, касается представления остовного дерева. Построение остовного дерева требует решения следующих вычислительных задач: ■ Вычисление потенциалов вершин. ■ Наращивание потока в циклах (и выявление на нем порожних или заполненных ■ Вставка нового ребра и удаление ребра из образованного при этом цикла. Каждая из этих задач сама по себе представляет интересное упражнение в разработке структур данных и в проектировании алгоритмов. Существует несколько структур данных и многочисленные алгоритмы, обладающие различными рабочими характеристиками которые нам полезно изучить. Мы начнем это изучение, пожалуй, с простейшей доступной нам структуры данных — с которой мы впервые столкнулись в главе 1 (!) — т.е. с представления дерева в форме родительских связей. После того, как мы проведем анализ алгоритмов и реализаций, которые построены на основе представлении дерева в форме родительских связей для выше перечисленных задач и опишем, как следует их использовать в контексте сетевого симплексного алгоритма, мы обсудим альтернативные структуры данных и алгоритмы. Подобно тому, как мы поступали в ряде других реализациях, рассмотренных в данной главе, начиная от реализации вычисления максимального пути методом построения аугментальных путей, мы сохраняем связи с сетевым представлением, обеспечивающим доступ к параметрам потока, а не простые индексы в представлении дерева, что позволит получать доступ к величинам потоков, не теряя времени на доступ к именам вершин. Программа 22.10 представляет реализацию, которая присваивает потенциалы вершинам за время, пропорциональное V. В ее основе лежит следующая идея, проиллюстрированная на рис. 22.47. Мы начинаем с того, что выбираем любую вершину и в рекурсивном режиме вычисляем потенциалы ее предшественников, следуя вверх по родительскому списку до самого корня, которому по соглашению присваивается потенциал 0. Затем мы выбираем другую вершину и используем родительские связи для рекурсивного вычисления потенциалов ее предшественников. Рекурсивные вычисления заканчиваются, когда мы достигнем предшественника, потенциал которого известен; далее, при выходе из рекурсии мы возвращаемся по тому же пути, вычисляя потенциал каждого узла с использованием потенциала родителя. Процесс продолжается до тех пор, пока не будут вычислены значения потенциалов. Если мы уже прошли по какому-либо пути, то мы больше не посещаем ни одно из его ребер, следовательно, этот процесс протекает в течение времени, пропорционального числу вершин V. Программа 22.10. Вычисление потенциала вершины______________________________ Рекурсивная функция phiR следует вверх по дереву вдоль родительской связи до тех пор, пока не выйдет на вершину, потенциал которой имеет силу (в соответствии с соглашением, потенциал корня всегда имеет силу), а затем, завершая рекурсивные вызовы, вычисляет потенциалы вершин, которые она проходит на обратном пути. Она маркирует каждую вершину, потенциал которой вычисляет, устанавливая ей значение метки, равное текущему значению функции valid.
|