metod_15.03.04_atppp_moas_2016 (1016590), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Этот факт следует изабсолютной унимодулярности матрицы. Первое ограничение требует, чтобы каждому исполнителю была назначена в точности одна задача, второе требует,чтобы для каждой задачи был назначен один исполнитель.Нахождение кратчайших путей в графеБудем рассматривать ориентированные графы Gu,V,, дугам которыхE поставлено в соответ-ствие некоторое вещественное число a (u, v), называемое весом данной дуги.Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, tV. Длину такого кратчайшего пути мы будем обозначатьd (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, тополагаем d (s, t) = ╔ .

Если каждый контур нашего графа имеет положительнуюдлину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.С другой стороны, если в графе существует контур отрицательной длины,то расстояние между некоторыми парами вершин становится неопределенным,потому что, обходя этот контур достаточное число раз, мы можем показать путьмежду этими вершинами с длиной, меньшей произвольного вещественногочисла. В таком случае, можно было бы говорить о длине кратчайшего элементарного пути, однако задача, поставленная таким образом, вероятно будет значительно более сложной, так как, в частности, она содержит в себе задачу существования гамильтонова пути.Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги.

Мы ищем затем кратчайшиепути между городами. Вес дуги также может соответствовать стоимости (иливремени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуаu,равен вероятности p(u, v) безаварийнойработы канала передачи информации. Если предположить, что аварии каналовне зависят друг от друга, то вероятность исправности пути передачи информацииравна произведению вероятностей составляющих его дуг.

Задачу нахождениянаиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - lg p(u, v).Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этогодостаточно отметить, что для произвольных s, tV (s , t) существует вершина v,такая что d (s, t) = d (s, v) + a (v, t).Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v),и т.д.Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ...

не сожержит повторений и оканчивается вершиной s.Очевидно, что она определяет (при обращении очередности) кратчайшийпуть из s в t.Таким образом, мы получаем следующий алгоритм:Алгоритм нахождения кратчайшего путиДанные: Расстояния D[v] от фиксированной вершины s до всех остальныхвершин vV, фиксированная вершина t, матрица весов ребер, A[u, v], u, vV.Результаты: СТЕК содержит последовательность вершин, определяющуюкратчайший путь из s в t.beginCTEK :=; CTEKt; v:= t;while v ╧ s dobeginu := вершина, для которой D[v] = D[u] + A[u, v];CTEKu;v:= uendend.V,-=n= m. Если выборвершины u происходит в результате просмотра всех вершин, то сложностьнашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что, то в этом случае сложность будетO(m).Отметим, что в случае положительных весов ребер задача о кратчайшемпути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа.

С этой целью достаточно заменить каждоеребро {u, vu,v,, каждая с таким же весом, что и {u,v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.Далее будем всегда предполагать, что G=nV,является ориентирован-= m. В целях упрощения изложения и избежаниявырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.Будем также предполагать, что веса дуг запоминаются в массиве A[u, v],V (A[u, v] содержит вес a (u, v)).u, vКратчайшие пути от фиксированной вершиныБольшинство известных алгоритмов нахождения расстояния между двумяфиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u,v], u, vV, вычисляются некоторые верхние ограничения D[v] на расстояния отs до всех вершин vV.

Каждый раз, когда мы устанавливаем, чтоD[u] + A[u, v] < D[v], оценку D[v] улучшаем: D[v] = D[u] + A[u, v].Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно.Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины u и v для проверки условия минимальности расстояния.

Эта очередности, как будет показано ниже, очень сильно вли-яет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа.Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной.

С эти алгоритмомобычно связывают имена Л.Р. Форда и Р.Е. Беллмана.Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимоРичардом Беллманом и Лестером Фордом.Алгоритм маршрутизации RIP (алгоритм Беллмана–Форда) был впервыеразработан в 1969 году, как основной для сети ARPANET.Формулировка задачиДан ориентированный или неориентированный граф G со взвешеннымирёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.Заметим, что кратчайших путей может не существовать.

Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угоднокороткий путь от одной вершины этого цикла до другой (каждый обход циклауменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называетсяотрицательным циклом.Решение задачи на графе без отрицательных циклов[править | правитьисходный текст]Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.Для нахождения кратчайших путей от одной вершины до всех остальных,воспользуемся методомдинамического программирования.

Построим матрицу Aij, элементы которой будут обозначать следующее: Aij — это длинакратчайшего пути из s в i, содержащего не более j рёбер.Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и +∞ в противном случае.Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждыйтакой путь есть путь изЕсли про пути длиныребра, к которому добавлено последнее ребро.все данные уже подсчитаны, то определить j-й стол-бец матрицы не составляет труда.Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов:fordofortodo forifthenreturnЗдесь V — множество вершин графа G, E — множество его рёбер, а w —весовая функция, заданная на ребрах графа (возвращает длину дуги, ведущей извершины u в v), d - массив, содержащий расстояния от вершины s до любойдругой вершины.Внешний цикл выполняетсяраз, поскольку кратчайший путь неможет содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти.

Зато при этом можно вычислить и сами кратчайшие пути, а не только ихдлины. Для этого заведем матрицу Pij.Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).Теперь алгоритм Беллмана–Форда выглядит так:forfortodofortodo forifthenПосле выполнения этого алгоритма элементысодержат длины крат-чайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий.

А сам кратчайший путь до вершины i с j ребрами восстанавливается так:whilereturn pЗанятие 5 – практическое занятие № 11. Транспортная задача.Условие:Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am.Данный груз необходимо доставить n потребителям в объемах b1, b2 ...

bn.Известны Cij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.Исходные данные транспортной задачи записываются в виде таблицы:Исходные данные задачи могут быть представлены в виде:вектора А=(a1,a2,...,am) запасов поставщиковвектора B=(b1,b2,...,bn) запросов потребителейматрицы стоимостей:МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИПеременными (неизвестными) транспортной задачи являются xij ,i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю.Эти переменные могут быть записаны в виде матрицы перевозок:Так как произведение Cij*Xij определяет затраты на перевозку груза от iго поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:По условию задачи требуется обеспечить минимум суммарных затрат.Следовательно, целевая функция задачи имеет вид:Система ограничений задачи состоит из двух групп уравнений.Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:Учитывая условие неотрицательности объемов перевозок математическаямодель выглядит следующим образом:В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарынм запросам потребителей, т.е.:Такая задача называется задачей с правильным балансом, а модель задачи закрытой.

Характеристики

Список файлов учебной работы