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