Нахождение минимальной стоимости в транспортной сети

       Ориентированное дерево - это граф с выделенной вершиной (корнем), в котором между корнем и любой вершиной существует единственный путь. При этом возможны два варианта ориентации: либо все пути ориентированы от корня к листьям, либо все пути ориентированы от листьев к корню. Ориентированное дерево можно получить из неориентированного дерева, выбрав в нем любую вершину в качестве корня и один из двух вариантов ориентации дуг. Например, граф на рис. 8 получен из предыдущего графа (см. рис. 7)  выбором вершины 5 в качестве корня и ориентацией дуг от корня к листьям. Если ориентацию всех дуг поменять на противоположную, то получится дерево с ориентацией от листьев к корню; если же поменять ориентацию только у частей дуг, то полученный граф не будет ориентированным деревом.

       В заключение расскажем о классической задаче теории графов, которая называется «задачей о четырех красках». Внимательно  рассматривая географическую карту, можно  заметить, что кроме графов, изображающих железные или шоссейные дороги, есть ещё один — граф, состоящий из границ между странами (областями, районами). Сами границы служат ребрами, а вершинами  этого графа являются точки, в  которых сходятся границы трёх или  более стран. 

8. Пример  ориентированного дерева.

 
 

       Одна  из классических задач теории графов называется «задачей коммивояжера»  или «задачей о бродячем торговце».

       Представим  себе торгового агента, который должен побывать в нескольких городах и  вернуться обратно. Известно, какие  дороги соединяют эти города, и  каковы расстояния между ними по этим дорогам. Нужно выбрать самый  короткий маршрут. Это уже не «игрушечная» задача. Например, водитель почтового  автомобиля, вынимающий письма из ящиков, очень хотел бы знать кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам.  Решить эту задачу очень непросто, особенно когда число вершин графа велико. Поэтому ее решение мы рассмотрим позже, используя не только методы теории графов, но и специальные приемы программирования.

       Вот другая задача, в некотором смысле противоположная задаче коммивояжера. Предполагается проложить железную дорогу, которая соединит несколько  крупных городов. Для любой пары городов известна стоимость прокладки  пути между ними. Требуется найти  наиболее дешевый вариант строительства.

       Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах  теории графов). Продемонстрируем его  на примере дороги, соединяющей пять городов: A, B, C, D и E. Стоимость прокладки пути между каждой парой городов указана в таблице. 

 

       Сначала строим ту дорогу, которая имеет  наименьшую стоимость. В нашем случае это маршрут B – E. Теперь найдем самую дешевую линию, соединяющую город B или E с каким-то из остальных городов. Это путь между E и C. Включаем его в схему. Далее поступаем аналогично: ищем самый дешевый из путей, соединяющих один из городов B, C, E с одним из оставшихся – A или D. Это дорога между C и A. Осталось подключить к железнодорожной сети город D. Дешевле всего соединить его с C. Получим сеть, изображенную на рисунке 26. 

 

  

9. Схема железнодорожной  сети.

       Описанный алгоритм относится к категории  «жадных»: на каждом шаге мы выбираем самое  дешевое продолжение пути. Для  данной задачи он подходит как нельзя лучше. Но в других случаях «жадные» алгоритмы могут не давать оптимальное  решение, например, в задаче коммивояжера.

       Во  многих случаях применения графов ребра, соединяющие вершины, имеют четко  выраженное направление. Как вы уже  знаете, такие графы называются орграфами. На них удобно рассматривать различные  транспортные задачи. Сетевые графики  – не что иное, как орграфы. Они  применяются при планировании какой-либо деятельности. 

Вот мы и приблизились непосредственно к основной теме моей курсовой работы- минимизации  стоимости в транспортной сети, или  транспортной задаче.

      2.Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.

     Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени  на перевозку).

      Задача (сказка): Вы владелец некоторого завода, выпускающего «Товар», и недавно Вам посчастливилось заключить контракт с одной крупной фирмой, находящейся в другом городе на поставку товаров в их розничную сеть. Так как он находится очень далеко (во Владивостоке), товары придется доставлять авиаперевозкой. В ходе телефонных переговоров Партнер поинтересовался «а на какой объем поставок в день мы можем рассчитывать?». Вы задумались… У Вас есть собственные грузовики (дальнобойщики) осуществляющие транспортировку. Аэропорт находится далековато. Просмотрев накопленную статистику перевозок, Вы выявили, что в собственной области при транспортировке есть некоторые ограничения: на дорогах стоят пункты досмотра груза, весового контроля, некоторые дороги и вовсе ремонтируются. Все это назовем «пропускной способностью» дорог в день. Отталкиваясь от этих условий Вам необходимо узнать: сколько ящиков «Товара» в день вы можете подвозить в аэропорт? При этом, вы хотите эффективно вести бизнес и доставлять товар, кратчайшими маршрутами, т.к. это износ шин, механизмов, в общем амортизационные расходы.

     Итого: сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая пропускную способность дорог, при этом, чтобы  общее расстояние маршрутов было минимальным?

     Задача  – самая что ни на есть на графах. Решение будет построено постепенно.

Алгоритмы буду, если можно так выразиться, рассказывать, т.к. в сети предостаточно их описаний.

      2.1Основные понятия.

Карта дорог в  нашем случае представляется в виде графа. Вершинами являются перекрестки, а ребра графа – это дороги. Ребрам (дорогам) приписаны их характеристики: расстояние (до след. перекрестка), а  так же пропускная способность в  день. 

В коде граф представляют либо в виде списков смежности, либо матрицы смежности. Для простоты мы будем использовать матрицу смежности. Если в матрице смежности на пересечении [u] и [v] вершины стоит «1» – значит, что эти вершины (перекрестки) соединены ребром (дорогой). Не обязательно обозначать именно «1», в матрице очень удобно можно хранить и иную полезную информацию приписанную ребру: например расстояние, и пропускную способность (в аналогичной матрице).

     На  рисунке изображена матрица, симметричная относительно главной диагонали, т.е. M[u][v] = M[v][u]. Это значит, что нам задан ненаправленный граф и по ребру можно пройти в любом направлении (туда-обратно). Если в матрице M[u][v] = 1, а в обратном направлении M[u][v] = 0, то граф – направленный и можно пройти по ребру только от вершины [u] до [v].

     Пропускные  способности дорог у нас будут  записаны в матрицу C[..][..], которая вообще говоря, представляет собой направленный граф. Ведь дороги нам нужны для того, чтобы проехать от «завода» по направлению в «аэропорт». Направленный граф с заданными пропускными способностями (заводом и аэропортом) называется – сетью.

     Когда для графа необходимо вычислить  определенную характеристику, но не массово  «от всех-ко-всем», а допустим расстояние от одной вершины до остальных, то гораздо удобнее воспользоваться  массивом (меньше памяти). Т.е. допустим в [u] ячейке массива dist[..] будем хранить расстояние до [u] вершины от «завода». Аналогично массивами будем пользоваться, при обходе графа для того, чтобы отмечать уже посещенные вершины (mark), записывать сколько ящиков привезли (push), и откуда мы в вершину приехали (pred).

     ОК. Отлично. Знаем, как преобразовать  нашу карту в граф. А как мы будем доставлять ящики до аэропорта? Нам нужно уметь находить путь от «завода» до «аэропорта». Для этого  будем пользоваться…

     2.2Алгоритм поиска в ширину (breadth first search), BFS.

     Пока  мы учитываем только: смежность (соседство) вершин графа, не рассматривая пропускные способности и расстояния.

BFS является одним из самых основных алгоритмов, составляющих основу многих других.

      Простое описание (рисунок будет ниже). Мы сейчас стоим в некоторой стартовой (завод) вершине [s], из которой по ребрам видны только соседние вершины. И нам очень нужно как можно скорее попасть в вершину [t], которая находится где-то в этом графе. Далее мы поступаем так. Просматриваем по ребрам (а именно свободным дорогам) нашей вершины соседей: есть ли среди них [t]. Если нет, то записываем всех (впервые обнаруженных) соседей в очередь «нужно там побывать». Когда просмотрели всех соседей — отмечаем свою вершину – «тут уже побывали». Достаем первую непосещенную вершину из очереди и идем в нее.

      Продолжаем  поиски таким же образом. При этом те вершины, в которых однажды  побывали — игнорируем (ни шагу назад). Если по дороге встретили [t] – отлично, цель достигнута!

Для того, чтобы не заезжать в одни и те же перекрестки  по нескольку раз, мы будем их отмечать в массиве mark[..]. После осмотра соседей из [u] вершины, ставим отметку mark[u] = 1 – значит, что на [u]-ом перекрестке мы «уже побывали».

На рисунке: в вершинах – написаны порядковые номера

После завершения алгоритма  получим следующую картину:

Отметим основные особенности:

в каждую вершину  мы попадаем ровно (не более чем) один раз

помещаем вершины  в очередь при их первом просмотре

от своего завода мы радиально (волнообразно) находим  остальные вершины в графе

«радиус осмотра» постоянно  увеличивается

когда мы найдем «аэропорт», то количество ребер (дорог) между «заводом»  и «аэропортом» будем минимальным. Т.о. мы быстрейшим осмотром графа найдем «аэропорт»

Смотрим только по свободным  дорогам, по которым можно перевезти  ящики!

      Теперь  мы знаем, как найти путь, по которому можно провезти наши ящики «Товара» в аэропорт. Хорошо… Провезем их по дороге, и отметим это себе на карте. Эту пометку – «сколько ящиков, по какой дороге (ребру) и  в какую сторону мы везем» мы назовем  «поток». Отмечать это будем в  матрице (flow) F[..][..]. Т.е. по дороге из [u] в [v] мы везем F[u][v] ящиков.

      Пора  столкнуться с реальностью –  придется считаться с «пропускной  способностью», которая обозначается матрицей (capacity) C[..][..]. Ведь по дороге от [u] в [v] мы можем провезти не более C[u][v] ящиков. That’s a pity.

Мы поступили дальновидно. Пока мы BFS’ом искали «аэропорт», пока отмечали «посещенные вершины» мы так же отмечали, из какого перекрестка приехали — записывали в массив pred[..]. Т.е. в вершину [v] мы попали из вершины pred[v]. И так же заблаговременно завели еще один полезный массив: push[v], т.е. сколько мы могли бы «толкнуть» ящиков в перекресток [v] по некоторой дороге [u]-[v].

И поддерживали его  в актуальном состоянии: push[v] = min(push[u], C[u][v]-F[u][v]);

      Благодаря этому, пока нам не придется лишний раз «разматывать» траекторию от «аэропорта» до «завода» в обратном порядке, чтобы вычислить, сколько  максимально ящиков мы сможем провести по этому маршруту.

      Push[v] = push[«аэропорт»] = flow = вот! сколько ящиков довезли в аэропорт по найденному пути. Один раз размотаем маршрут и по всем ребрам (дорогам), и добавим «поток» flow ко всем ребрам пути.

      Но, хоть в задаче речь идет о натуральных  величинах: количестве ящиков, пропускной способности и расстояниях, все  же возможно придется столкнуться с  «минусом»… 

2.3 Увеличение потока (или Алгоритм Форда-Фалкерсона)