- •1Графика
- •1.1Алгоритм Сазерленда-Кохена, отсечение отрезка прямоугольным окном
- •1.2Алгоритм Лианга-Барски, отсечение отрезка прямоугольным окном
- •2Представление разреженных матриц.
- •2.1Форматы представления разреженных матриц
- •2.2Конвертация разреженной матрицы из нормальной формы в формат rr(c)o
- •2.3Конвертация разреженной матрицы, представленной в формате rr(c)u в нормальную форму
- •2.4Транспонирование разреженной матрицы, заданной в формате rr(c)u
- •2.5Сложение двух матриц, заданных в формате rr(c)u.(1-й способ)
- •2.6Сложение двух матриц, заданных в формате rr(c)u.(2-й способ)
- •2.7Умножение двух матриц, заданных в формате rr(c)u.(1-й способ)
- •2.8Умножение двух матриц, заданных в формате rr(c)u.(2-й способ)
- •3Интегральные уравнения.
- •3.1Введение
- •3.2Уравнение Вольтерра первого рода
- •3.3Линейное уравнение Вольтерра второго рода
- •3.4Уравнение Фредгольма второго рода
- •4Методы оптимизации
- •4.1Метод наискорейшего спуска
- •4.2Минимизация функции многих переменных методом конфигураций
- •5Теория графов
- •5.1Способы задания графа
- •5.2Путь с минимальным количеством промежуточных вершин.(волновой алгоритм)
- •5.3Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда)
- •5.4Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена)
- •5.5Построения минимального остовного дерева (Алгоритм Краскала)
- •6Сетевое программирование
5.4Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена)
Алгоритм предназначен для нахождения К путей минимальной длины во взвешеном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель.
Задача состоит в отыскании нескольких минимальных путей, поэтому возникает вопрос о том чтобы не получить путь содержащий петлю, в случае поиска одного пути минимального веса, это условие выполняется по необходимости, в данном же случае мы используем алгоритм Йена, позволяющий находить K кратчайших простых цепей.
Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать следующий алгоритм.(алгоритм Дейкстры).
всем веpшинам пpиписывается вес - вещественное число, d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;
всем веpшинам пpиписывается метка m(i)=0;
вершина u1 объявляется текущей - t=u1
для всех вершин у которых m(i)=0, пересчитываем вес по формуле: d(i):=min{d(i), d(t)+W[t,i]}
среди вершин для которых выполнено m(i)=0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует; ВЫХОД;
иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1)
если t=u2, то найден путь веса d(t),ВЫХОД;
переходим на шаг 4.
Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Более точное пошаговое описание: 1. Найти минимальный путь P1=(v11,...,v1L[1]) .Положить k = 2. Включить P1 в результирующий список. 2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k–1)-го кратчайшего пути Pk-1 для всех i=1,2,...,L[k-1], выполняя для каждого i шаги с 3-го по 6-й. 3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,k–1). Если да, положить W[vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей). 4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,...,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень. 5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его. 6. Восстановить исходную матрицу весов W и возвратиться к шагу 3. 7. Поместить путь минимального веса (MinW), найденый в результате выполнения шагов с 3 по 6, в результирующий список.Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.
Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайшех путей без петель.
5.5Построения минимального остовного дерева (Алгоритм Краскала)
Алгоритм предназначен для нахождения минимального остовного дерева, т.е. такого подграфа который бы имел столько же компонент связности, сколько и исходный, но не содержал петель и сумма весов всех его ребер была бы минимальной.
Вначале опишем алгоритм (возможно не достаточно строго), а затем обсудим какой способ задания графа был бы наилучшим в данном случае, а так же покажем как от тех способов задания, которые мы использовали ранее перейти к способу применимому здесь.
Итак алгоритм Краскала: 1. Сортируем ребра графа по возрастанию весов. 2. Полагаем что каждая вершина относится к своей компоненте связности. 3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:
Если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву.
Если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения. 4. Если есть еще нерассмотренные ребра и не все компоненты связности объеденены в одну, то переходим к шагу 3, иначе выход.
Предположим, что как и ранее граф задается матрицой весов W ясно, что в данном случае работать непосредственно с матрицей весов не удобно, это выявляется уже на этапе упорядочивания ребер по весу, поэтому вначале выделим массив ребер с соответствующими весами. В нашем случае достаточно если ребро будет иметь три свойства: начальная вершина, конечная вершина и вес (вообще работа с графами хорошо реализуется методами ООП, но поскольку мы не используем расширения языков, то будем работать с простыми массивами). Для задания набора ребер используем два массива E: array [1..m,1..2] of integer - здесь m - количество ребер (m<n2-n+1, где n - количество вершин), и массив EW: array [1..m] of real, тогда ребро ei, соединяющее вершины u,v с весом wi будет соответствовать элементам E[i,1]=u,E[i,2]=v,EW[i]=w. Таким образом до начала непосредственно поиска минимального остовного дерева нам необходимо пройти матрицу весов W и заполнить массивы E и EW.
Преобразовав представление графа от весовой матрицы к набору ребер (часто граф изначально задается при помощи списка ребер, и тогда предыдущая часть алгоритма становиться не нужна), мы уже можем легко упорядочить ребра по неубыванию весов, я для этого использую в блок-схеме алгоритм пузырька, чтобы не "замазывать" основной алгоритм, но можно легко перейти и к другим способам упорядочивания. Далее в алгоритме вводиться массив V:array [1..n] of integer элементы, которого характеризуют номер компоненты связности соответствующих вершин (две вершины u1,u2 лежат в одной компоненте связности, если и только если V[u1]=V[u2]). Теперь все структуры используемые в алгоритме описаны, и его работу легко будет понять из блок-схемы.
В заключении еще только одно замечание. В алгоритме используется переменная q, которая инициализируется значением n-1(на единицу меньше числа вершин) и затем, при объединении двух компонент связности на шаге 3, q уменьшается на единицу, таким образом когда (если) q на некотором шаге занулиться, то это будет означать, что все вершины лежат в одной компоненте связности и работа алгоритма завершена.
Найденое дерево будет определено с помощью массива WO - матрицы весов.