![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Минимальные остовные деревья
одели графов, в которых мы связываем веса (weights) или стоимости (costs) с каждым ребром, используются во многих приложениях. В картах авиалиний, в которых ребрами отмечены авиарейсы, такие веса означают расстояния или стоимость проезда. В электронных схемах, где ребра представляют электрические соединения, веса могут означать длину соединения, его стоимость или время, необходимое для распространения по ней сигнала. В задачах календарного планирования веса могут представлять время или расходы, затрачиваемые на выполнение задач, либо время ожидания завершения соответствующей задачи. Естественно, в таких ситуациях возникают вопросы, касающиеся различных аспектов минимизации стоимости. Мы будем изучать алгоритмы решения двух задач такого рода: (i) определение пути с наименьшей стоимостью, соединяющего все точки, и (ii) отыскание пути наименьшей стоимости, соединяющего две заданных точки. Первый тип алгоритма применяется для решения задач на неориентированных графах, которые представляют такие объекты как электрические цепи, находит минимальное остовное дерево (minimum spanning tree); это дерево является основной темой данной главы. Второй тип алгоритма, применяемый для решения задач на орграфах, которые представляют такие объекты, как карты авиарейсов, определяет кратчайшие пути (shortest path), и они являются темой обсуждений в главе 21. Эти алгоритмы находят широкое применение не только в приложениях, связанных со схемами авиарейсов и электрическими схемами, они используются также и при решении задач, возникающих во взвешенных графах. Когда мы изучаем алгоритмы обработки взвешенных графов, наша интуиция часто отождествляет веса с расстояни- Часть 5. Алгоритмы на графах
ями: мы употребляем выражение " ближайшая к х вершина" и ему подобные. Действительно, термин " кратчайший путь" оказывается в русле этой тенденции. Однако, несмотря на многочисленные приложения, в которых мы по существу имеем дело с расстояниями, и несмотря на все преимущества геометрической интуиции в понимании базовых алгоритмов, важно помнить, что веса не обязательно должны быть пропорциональны расстоянию, они могут представлять время и стоимость или совсем другую переменную величину. В самом деле, как мы убедимся в главе 21, веса в условиях задач определения кратчайшего пути могут принимать даже отрицательные значения. Прибегая к помощи интуиции при описании алгоритмов и примеров и сохраняя при этом общую применимость, мы используем неоднозначные термины, когда попеременно ссылаемся на длины и веса. В большей части примеров, приводимых в настоящей главе, мы используем веса, пропорциональные расстоянию между вершинами, как это нетрудно видеть на рис. 20.1. Такие графы удобно рассматривать в качестве примеров, поскольку нет необходимости указывать метки ребер, ибо достаточно одного взгляда, дабы уяснить, что более длинные ребра имеют большие веса по сравнению с короткими ребрами. Когда веса представляет расстояния, мы получаем возможность рассматривать алгоритмы, которые становятся более эффективными, когда учитывают РИСУНОК 20.1. ВЗВЕШЕННЫЙ НЕОРИЕНТИРОВАННЫЙ ГРАФ И ЕГО ДЕРЕВО MST Взвешенный неориентированный граф представляет собой набор взвешенных ребер. Дерево MST есть множество ребер минимального общего веса, которые соединяют все вершины (выделены черным в списке ребер, утолщенные ребра на чертеже графа). В рассматриваемом графе веса пропорциональны расстояниям между вершинами, однако базовые алгоритмы, которые мы исследуем, соответствуют графам общего вида и не накладывают никаких условий на веса (см. рис. 20.2).
|