Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. неориентированных или невзвешенных графах, легко решаются с помощью тех же алгоритмов, которые обрабатывают сети
|
|
неориентированных или невзвешенных графах, легко решаются с помощью тех же алгоритмов, которые обрабатывают сети, то к сетям (со взвешенными ребрами) применяется обычная терминология, как это и делается в данной главе.
Мы сосредоточимся на тех же базовых задачах, которые в разделе 18.7 были определены для неориентированных и невзвешенных графов. Мы вновь формулируем их здесь, обращая внимание на то, что определение 21.1 неявно обобщает их, с учетом весов в сетях.
Кратчайший путь источник-сток. Для заданной начальной вершины s и конечной вершины t найти кратчайший путь в графе из s в t. Мы будем говорить о начальной вершине, как об источнике (source), а о конечной вершине — как о стоке (sink), за исключением тех ситуаций, где такое использование упомянутых терминов конфликтует с определением источников (вершин без входящих ребер) и стоков (вершин без исходящих ребер) в орграфе.
Кратчайшие пути из единственного источника. Для заданной начальной вершины s найти кратчайшие пути из s во все остальные вершины графа.
Кратчайшие пути между всеми парами вершин. Найти кратчайшие пути, соединяющие каждую пару вершин в графе. Для краткости, при ссылке на это множество из V2 путей мы иногда будем использовать термин все кратчайшие пути.
Если имеется несколько кратчайших путей, соединяющих любую заданную пару вершин, мы довольствуемся любым из них. Поскольку пути имеют различное количество ребер, наши реализации предоставляют функции-элементы, которые позволяют клиентам различать пути за время, пропорциональное длинам путей. Любой кратчайший путь также неявно содержит и собственную длину, но наши реализации выдают длины явно. В итоге, чтобы быть точным, когда в только что данных постановках задач мы говорим " найти кратчайший путь", мы имеем в виду " вычислить длину кратчайшего пути и способ обхода заданного пути за время, пропорциональное его длине".
На рис. 21.3 показаны кратчайшие пути для сети, изображенной на рис. 21.1. В сетях с V вершинами для решения задачи с единственным источником нужно определить V путей, а для решения задачи всех пар потребуется отыскать V2 путей.
РИСУНОК 21.3. ВСЕ КРАТЧАЙШИЕ ПУТИ
Эта таблица дает все кратчайшие пути в сети рис. 21.1 вместе с их длинами. Данная сеть является сильно связной, так что в ней существуют пути, соединяющие каждую пару вершин.
Цель алгоритма поиска кратчайшего пути из источника в сток заключается в вычислении одного из элементов (входов) этой таблицы; цель алгоритма поиска кратчайших путей из единственного источника сводится к вычислению одной из строк в этой таблице; наконец, цель алгоритма поиска кратчайших путей между всеми парами предполагает вычисление всей таблица. В общем случае, мы используем более компактные представления, которые содержат по существу ту же информацию и разрешают клиентам обойти любой путь за время, пропорциональное числу его ребер (см. рис. 21.8).
Часть 5. Алгоритмы на графах
В наших реализациях мы используем более компактное представление, чем эти списки путей; мы ранее уже отмечали это в разделе 18.7, и, кроме того, обсудим его подробно в разделе 21.1.
В реализациях на C++ мы строим алгоритмические решения этих задач в виде реализаций АТД, что дает возможность создавать эффективные клиентские программы, которые могут решать разнообразные практические задачи обработки графов. Например, как будет показано в разделе 21.3, мы реализуем классы для определения кратчайших путей для всех пар с помощью конструкторов внутри классов, которые поддерживают запросы на поиск кратчайшего пути за постоянное (линейное) время. Мы также построим классы для решения задачи с единственным источником так, что клиенты, которым необходимо вычислить кратчайшие пути из заданной вершины (или небольшого их множества) могут избежать расходов на вычисления кратчайших путей для других вершин. Внимательное исследование таких результатов и соответствующее использование рассматриваемых нами алгоритмов поможет осознать разницу между эффективным решением практической задачи и решением, которое настолько дорого, что никакой клиент не мог бы позволить себе воспользоваться им.
Задачи о кратчайших путях в различных видах возникают во широком спектре приложений. Многие приложения интуитивно приводят непосредственно к их геометрической интерпретации, тогда как другие вовлекают структуры произвольного вида. Так же, как и в случае минимальных остовных деревьев (MST), которые рассматривались в главе 20, мы иногда будем обращаться к геометрической интерпретации, дабы облегчить понимание алгоритмов решения этих задач, не упуская при этом из виду того факта, что наши алгоритмы действуют должным образом и в более общих структурах. В разделе 21.5 мы рассмотрим специализированные алгоритмы для эвклидовых сетей. Чрезвычайно важно, что в разделах 21.6 и 21.7 будет показано, что базовые алгоритмы эффективны для многочисленных приложений, в которых при помощи сетей представляется абстрактная модель вычислений.
Дорожные карты. Таблицы, которые дают расстояния между всеми парами главных городов, - это замечательная особенность многих дорожных карт. Мы предполагаем, что издатель карты позаботился о том, чтобы расстояния, несомненно, были кратчайшими, но наше допущение не обязательно всегда верно (см., например, упражнение 21.11). В общем случае, такие же таблицы существуют и для неориентированных графов, которые мы будем рассматривать как сети с ребрами в обоих направлениях, соответствующими каждой дороге. Вполне можно подумать об их применении к улицам с односторонним движением — для карт города, а также в отношении ряда аналогичных приложений. Как было показано в разделе 21.3, нетрудно также обеспечить и другую полезную информацию, как, например, таблицу, которая сообщает о том, как выполнить (т.е. пройти) кратчайшие пути (см. рис. 21.4). В современных приложениях встроенные системы автомобилей и других транспортных систем предоставляют возможности подобного рода. Карты являются эвклидовыми графами, и в разделе 21.4 рассматриваются алгоритмы поиска кратчайших путей, которые при поиске учитывают позицию вершины.
Маршруты авиалиний. Карты маршрутов и расписания для авиалиний или других транспортных систем могут быть представлены как сети, для которых различные задачи о кратчайших путях имеют первостепенное значение. Например, может потребоваться минимизировать время, которое займет перелет между двумя городами, или же свести к
Глава 21. Кратчайшие пути
| ментарными алгоритмами и алгоритмически неразрешимыми задачами, но также подводят нас к мощным и общим механизмам принятия решений. Как и для алгоритмов MST из главы 20, мы часто смешиваем понятия веса, стоимости и расстояния. Как и там, мы обычно используем естественную привлекательность геометрической интуиции, даже рассматривая более общие постановки задач с произвольными весами ребер; так, мы говорим о " длине" пути и ребра вместо того, чтобы сказать " вес", и говорим, что один путь " короче" другого вместо того, чтобы сказать, что он " имеет меньший вес". Мы также можем сказать, что v находится " ближе" к s, чем w, вместо того, чтобы говорить, что " ориентированный путь наименьшего веса из s в v имеет вес меньше, чем вес ориентированного пути наименьшего веса из s в w", и т.д. Это проявляется и в стандартном использовании термина " кратчайшие пути" и выглядит естественным, |
минимуму стоимость путешествия. Стоимости, или расходы, в таких сетях могли бы включать функции времени, денег или других интегральных ресурсов. Например, перелеты между двумя городами обычно занимают больше времени в одном направлении, нежели в другом, по причине преобладающих ветров. Авиапассажиры также знают, что стоимость перелета не обязательно является простой функцией расстояния между городами — ситуации, где это будет стоить дешевле, например, использование окольного маршрута (или пересадки) вместо прямого перелета, встречаются довольно-таки часто. Такие усложненные модели могут быть обработаны базовыми алгоритмами поиска кратчайших путей, которые мы рассматриваем в этой главе; эти алгоритмы разработаны в предположении, что все стоимости будут положительными.
Фундаментальные вычисления кратчайших путей, предлагаемые этими приложениями, - это лишь то, что лежит на поверхности области применимости алгоритмов кратчайших путей. В разделе 21.6 мы рассматриваем задачи из областей применения, которые кажутся не имеющими отношения к данной тематике, в контексте обсуждения вопросов сведения, т.е. формального механизма для демонстрации связей между задачами. Мы решаем задачи для этих приложений путем превращения их в абстрактные задачи поиска кратчайших путей, которые не имеют интуитивной геометрической связи с только что описанными задачами. Действительно, некоторые приложения приводят к рассмотрению задач о кратчайших путях в сетях с отрицательными весами. Такие задачи могут оказаться намного более трудноразрешимыми, чем те задачи, где отрицательные веса не допускаются. Задачи о кратчайших путях для таких приложений не только прокладывают мост между эле-
РИСУНОК 21.4. РАССТОЯНИЯ И ПУТИ
Дорожные карты обычно содержат таблицы расстояний наподобие приведенной в центре рисунка для небольшого подмножества французских городов. Города соединяются через шоссе, как показано в верхней части рисунка. Тем не менее, на картах редко встречается таблица, подобная той, что внизу, хотя она была бы также полезной, поскольку отмечает пункты следования, лежащие на кратчайшем пути. Например, чтобы решить, как добраться из Парижа в Ниццу, можно было бы обратиться к такой таблице, из которой видно, что начинать следует с поездки в Лион.