Структуры данных. Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда)

Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда)

Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Дейкстры)

Функция находит путь минимального веса в графе G=(V,E), заданном весовой матрицей w, у которой элемент w_{i j} равен весу ребра, соединяющего i -ю и j -ю вершины. При этом предполагается, что все элементы w_{i j} неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2. Функция использует алгоритм Дейкстры. Для бесконечности используется число GM, его можно задавать в зависимости от конкретной задачи.

Алгоритм, по которому происходит поиск, заключается в следующем:

1) всем веpшинам пpиписывается вес - вещественное число, d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;

2) всем веpшинам пpиписывается метка m(i)=0;

3) вершина u1 объявляется текущей - t=u1;

4) для всех вершин у которых m(i)=0, пересчитываем вес по формуле: d(i):=min{d(i), d(t)+W[t,i]};

5) среди вершин для которых выполнено m(i)=0, ищем ту, для которой d(i) минимальна, если минимум не найден, т.е. вес всех “непомеченных” вершин равен бесконечности (GM), то путь не существует; ВЫХОД;

6) иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1);

7) если t = u2, то найден путь веса d(t),ВЫХОД;

8) переходим на шаг 4.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует; length=0, если u1=u2), переменную Weight -вес пути и массив Path, содержащий последовательность номеров вершин, определяющих путь.

Функция находит пути минимального веса в графе G=(V,E), заданном весовой матрицей w, у которой элемент w_{i j} равен весу ребра, соединяющего i -ю и j -ю вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM, его можно задавать в зависимости от конкретной задачи.

Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае, описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее, надо заметить, что если граф неориентированный (W[i,j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

D⁰=W d^m+1[i,j]=min{d^m[i,j], d^m[i,(m+1)] + d^m[(m+1),j]}, где i<>j; d^m+1[i,i]=0.

Преобразование проделывается для m=1..n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное d^m[i,m]+d^m[m,i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i, и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P, при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i, если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.
Заметим, что если граф неориентированный, то W, а также все матрицы получаемые в результате преобразований, симметричны и, следовательно, достаточно вычислять только элементы, расположенные выше главной диагонали.

2.4. Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена)

Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе между вершинами u1,u2. Ищутся пути, которые не содержат петель.
Итак, задача состоит в отыскании нескольких минимальных путей, поэтому возникает вопрос о том чтобы не получить путь, содержащий петлю, в случае поиска одного пути минимального веса это условие выполняется по необходимости, в данном же случае мы используем алгоритм Йена, позволяющий находить K кратчайших простых цепей.

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

Более точное пошаговое описание:

1. Найти минимальный путь P₁=(v¹₁,...,v¹_L[1]). Положить k = 2. Включить P₁ в результирующий список.

2. Положить MinW равным бесконечности. Найти отклонение минимального веса от (k–1) -го кратчайшего пути P_k-1 для всех i=1,2,...,L[k-1], выполняя для каждого i шаги с 3-го по 6-й.

3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути P_k-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,k–1). Если да, положить W[v^k-1_i,v^j_i+1] равным бесконечности, в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результате одних и тех же путей).
4. Используя алгоритм нахождения кратчайшего пути, найти пути от v^k-1_i к u2, исключая из рассмотрения корни (v^k-1₁,...,v^k-1_i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам, входящим в корень.

5. Построить путь, объединяя корень и найденное кратчайшее ответвление; если его вес меньше MinW, то запомнить его.

6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.
7. Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив l для хранения соответствующих длин, при этом, если начиная с некоторого i элементы l[i] равны -1, значит существует только i-1 кратчайших путей без петель.

Конспект лекций

Лекция 15

Объектные типы данных

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

Содержание

1. Классы и объекты.. 2

2.Объектно-ориентированная парадигма. 4

3. Работа с классами в С++. 7

1. Классы и объекты

По мере прогресса в области вычислительной математики акцент в программировании смещается в какую-либо сторону. Первой была идея процедурного структурирования программ, затем – организация данных. В настоящее время акцент делается на объектно-ориентированное программирование (ООП).

Его руководящая идея заключается в стремлении связать данные с обрабатывающими эти данные функциями в единое целое – объект.

Термин "объект" в программной индустрии впервые был введен в языке Simula (1967 г.) и означал какой-либо аспект моделируемой реальности. Сейчас под объектом понимается "нечто, имеющее четко определенные границы" (определение известного американского специалиста Г.Буча). Объекты, обладающие одинаковыми свойствами, составляют классы (например, курица, пингвин и чайка - объекты класса "птицы"). Обычно класс описывается как новый тип данных, а объекты (экземпляры класса) - определенные на его основе переменных.

Класс (class) и объект (object) – два общепринятых термина. Однако, поскольку имеется несколько различных трактовок этих понятий, давайте сразу договоримся о том, как их будем понимать мы. Классом называется определенный пользователем тип данных, который включает в себя состояние (представление класса) и некие операции (поведение класса). Класс имеет некоторое количество внутренних данных и несколько методов, существующих в форме функций, и обычно описывает общее поведение и характеристики набора аналогичных друг другу объектов.

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

К сожалению, в некоторых языках и средах эта разница не столь ясна. Дополнительную сложность создает также то обстоятельство, что ранние версии компилятора Borland Pascal использовали ключевое слово object для определения классов. По этой причине программисты на Pascal со стажем предпочитают использовать для обозначения типа термин “объект” вместо термина “класс”, а для обозначения реальных объектов - термин “экземпляр объекта” (object instance).

Дата добавления: 2014-01-07