Содержание
Введение
1 Выбор варианта задания
2 Алгоритм сортировки Шейкер
2.1 Математическое описание задачи
2.2 Словесное описание алгоритма и его работы
2.3 Описание схемы алгоритма
2.4 Контрольный пример
3 Алгоритм покрытия: построение одногократчайшего покрытия
3.1 Математическое описание задачи
3.2 Словесное описание алгоритма и его работы
3.3 Описание схемы алгоритма
3.4 Контрольный пример
4 Алгоритм на графах: нахождениекратчайшего пути
4.1 Математическое описание задачи
4.2 Словесное описание алгоритма и его работы
4.3 Описание схемы алгоритма
4.4 Контрольный пример
Заключение
Перечень литературы
Введение
Алгоритм –это точно определенная (однозначная) последовательность простых (элементарных)действий, обеспечивающих решение любой задачи из некоторого класса, т.е. такойнабор инструкций, который можно реализовать чисто механически, вне зависимостиот умственных способностей и возможностей исполнителя.
Как заметилКнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям могследовать даже компьютер».
Теорияалгоритмов и практика их построения и анализа является концептуальной основойразнообразных процессов обработки информации. В настоящее время теорияалгоритмов образует теоретический фундамент вычислительных наук. Применениетеории алгоритмов осуществляется как в использовании самих результатов(особенно это касается использования разработанных алгоритмов), так и вобнаружении новых понятий и уточнении старых. С ее помощью проясняются такиепонятия как доказуемость, эффективность, разрешимость, перечислимость и другие.
Эффективностьалгоритма определяется анализом, который должен дать четкое представление,во-первых, о емкостной и, во-вторых, о временной сложности процесса.
Речь идет оразмерах памяти, в которой предстоит размещать все данные, участвующие ввычислительном процессе (естественно, к ним относятся входные наборы,промежуточная и выходная информация), а также физических ресурсах, затраченныхисполнителем.
В курсовойработе представлены различные подходы и методы использования алгоритмов,приведены оценки сложностей алгоритмов, реализации математических задач спомощью алгоритмов. Проведена краткая характеристика используемых структурданных, эффективность их применения в данной задаче
1 ВЫБОРВАРИАНТА
Номерварианта определяется нахождением остатка от целочисленного деления числа У, котороеявляется суммой числа Х и номера по списку в журнале. Номер по списку в журналеN=9. Таким образом:
X=Nгр*100=5*100=500;
Y=N+X=9+500=509.
По формуламнахожу соответствующие виды алгоритмов.
1) (Y mod 4) + 1 =(509 mod 4) + 1=1 + 1= 2; Алгоритмпокрытия: построение одного кратчайшего покрытия.
2) (Y mod 6) + 1 =(509 mod 6) + 1 = 5 + 1=6;Алгоритм на графах: поиск кратчайшего пути.
3) (Y mod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5;Алгоритм сортировки: сортировка-шейкер.
2 АЛГОРИТМ СОРТИРОВКИ:СОРТИРОВКА ШЕЙКЕР
2.1 Математическоеописание задачи
Сортировка –это перестановка элементов некоторого множества в заданном порядке принекоторой упорядочивающей функцию.
Сортировка используетсядля облегчения поиска элемента в таком отсортированном множестве.
Задачасортировки решается с помощью таких алгоритмов: сортировка с помощью прямоговключения, прямого выбора, прямого обмена, включений с уменьшающимисярасстояниями, дерева, разделения и другие.
2.2 Словесное описаниеалгоритма и его работы
СортировкаШейкер является усовершенствованной сортировкой методом пузырька. Идея метода:шаг сортировки состоит в проходе снизу вверх по массиву. По путипросматриваются пары соседних элементов. Если элементы некоторой пары находятсяв неправильном порядке, то меняем их местами.(см. Таб. 1)
Таблица1i=1 2 3 4 5 6 7 8 44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 55 44 42 42 42 42 94 42 18 55 44 44 44 44 18 94 42 42 55 55 55 55 06 18 94 94 67 67 67 67 67 67 67 67 94 94 94 94
Посленулевого прохода по массиву «вверху» оказывается самый«легкий» элемент — отсюда аналогия с пузырьком. Следующий проходделается до второго сверху элемента, таким образом второй по величине элементподнимается на правильную позицию.
Делаем проходыпо все уменьшающейся нижней части массива до тех пор, пока в ней не останетсятолько один элемент. На этом сортировка заканчивается, так какпоследовательность упорядочена по возрастанию. Среднее число сравнений иобменов имеют квадратичный порядок роста: отсюда можно заключить, что алгоритмпузырька очень медленен и малоэффективен.
Тем не менее,у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мысейчас и займемся. Во-первых, рассмотрим ситуацию, когда на каком-либо изпроходов не произошло ни одного обмена. Что это значит? Это значит, что всепары расположены в правильном порядке, так что массив уже отсортирован. Ипродолжать процесс не имеет смысла(особенно, если массив был отсортирован ссамого начала !). Итак, первое улучшение алгоритма заключается в запоминании,производился ли на данном проходе какой-либо обмен. Если нет — алгоритмзаканчивает работу. Процесс улучшения можно продолжить, если запоминать нетолько сам факт обмена, но и индекс последнего обмена k. Действительно: всепары соседих элементов с индексами, меньшими k, уже расположены в нужномпорядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобыдвигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить изследующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за одинпроход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг заитерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, асортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
Чтобы избежать подобного эффекта, можно менять направлениеследующих один за другим проходов. Получившийся алгоритм называют "шейкер-сортировкой".Далее проведена программа на языке С++, реализующая сортировку Шейкер.
template
void shakerSort(T a[], long size) {
long j, k = size-1;
long lb=1, ub = size-1; // границы неотсортированной части массива
T x;
do {
// проход снизу вверх
for( j=ub; j>0; j-- ) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}
lb = k+1;
// проход сверху вниз
for (j=1; j
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}
ub = k-1;
} while ( lb
}
Насколько описанные изменения повлияли на эффективность метода?Среднее количество сравнений, хоть и уменьшилось, но остается O(n2),в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее)количество операций остается квадратичным, количество излишних двойных провероксократилось.
Дополнительная память, очевидно, не требуется. Поведениеусовершенствованного (но не начального) метода довольно естественное, почтиотсортированный массив будет отсортирован намного быстрее случайного.Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает этокачество.
На практике методпузырька, даже с улучшениями, работает, увы, слишком медленно. А потому — почтине применяется.
2.3 Описание схемыалгоритма
Алгоритмысортировки очень сильно зависят от структуры данных… В данной работерассматривается сортировка массивов. Тип данных «массив» удобен тем, чтохранится во внутренней памяти и имеет случайный доступ к элементам, то естьболее быстрый, чем у последовательности. Поэтому массивы целесообразноиспользовать для хранения небольших, часто используемых множеств
Из вышесказанного следует, что в процессе работы потребуются следующие переменные:
n – количество элементовмассива;
A – сортируемый массив;
j – переменная;
x – i-й ключ (переносимыйэлемент);
r – номер последнегообмена при просмотре входной последовательности слева-направо.
l — номер последнегообмена при просмотре входной последовательности справа -
налево.
Всепеременные целого типа.
Описаниесхемы алгоритма. Блок-схемаданного алгоритма изображена на рис. 1 в Приложении.
Алгоритмработает следующим образом. Сначала вводятся исходные данные: длина массива иего элементы (блок 1, 2), затем организуется цикл по всей длине массива, вовремя которого (блоки 3 -7) и проводится сравнение элементов а[j-1]>a[j] и их обмен при проходесправа-налево. Номер последнего обмена l запоминается. Далееорганизуется цикл, в котором проводится проверка условия а[j-1]>a[j] при проходе массиваслева-направо (блоки8 — 12).
2.4 Контрольныйпример
Рассмотримпример работы алгоритма сортировки Шейкер.
ЗаданмассивA, состоящий из 8элементов: 44, 55, 12, 42, 94, 18, 6, 67.
Шаг1. l = 2, r = 8
Таблица 2l 2 3 3 4 4 r 8 8 7 7 4 Направление ↑ ↓ ↑ ↓ ↑ j=1 44 6 6 6 6 j = 2 55 44 44 12 12 j= 3 12 55 12 44 18 j = 4 42 12 42 18 42 j = 5 94 42 55 42 44 j = 6 18 94 18 55 55 j = 7 6 18 67 67 67 j = 8 67 67 94 94 94
1) j = r =8
2) A[7]
3) A[6]>A[7],x=18, A[6]=6, A[7]=x=18; j=6
4) A[5]>A[6], A[5]=6, A[6] = 94
5) A[4]>A[5], A[4]=6, A[5] =42
6) A[3]>A[4], A[3]=6, A[4] =12
7) A[2]>A[3], A[2]=6, A[3] = 55
8) A[1]>A[2], A[1]=6, A[2] = 44
9) l=3.
Шаг 2. A[7]
1)A[1]>A[2]; j=6
2)A[2]>A[3], A[1] =, A[2] = 44, j= 4
3)A[3]>A[4], A[2] =6, A[3] =12, j=5
4)A[4]>A[5], A[3] =6, A[4] =12, j=6
5)A[5]>A[6], j =7
6)A[6]>A[7], A[5] =6, A[6] = 18, j=8
7)r =7.
Шаг 3.
1) A[7]>А[8], j = j -1 =7
2) A[6]>A[7],x=18, A[6]=6, A[7]=x=18; j=6
3) A[5]>A[6], A[5]=6, A[6] = 94; j=5
4) A[4]>A[5], A[4]=6, A[5] =42; j=4
5) A[3]>A[4], A[3]=6, A[4] =12; j=3
6) A[2]>A[3], A[2]=6, A[3] = 55; j=2
7) A[1]>A[2], A[1]=6, A[2] = 44; j=1
8) l=3.
Шаг4.
1)A[1]>A[2], x=18, A[6]=6, A[7]=x=18; j=6
2)A[2]>A[3], A[1] =, A[2] = 94, j= 4
3)A[3]>A[4], A[2] =6, A[3] =42, j=5
4)A[4]>A[5], A[3] =6, A[4] =12, j=6
5)A[5]>A[6], j =7
6)A[6]>A[7], A[5] =6, A[6] = 44, j=8 ,
7)r =7. → конец алгоритма.
Такимобразом, мы получили исходный массив, отсортированный методом Шейкер:
6, 12, 18,42, 44, 55, 67, 94.
3 АЛГОРИТМ ПОКРЫТИЯ:ПОСТРОЕНИЕ ОДНОГО КРАТЧАЙШЕГО ПОКРЫТИЯ
3.1 Математическоеописание задачи и методов её решения
Пусть />-опорноемножество. Имеется множество
подмножеств/>множества B (/>). Каждому подмножеству/>сопоставленочисло />,называемой ценой. Множество />называется решением задачи опокрытии, или просто покрытием, если выполняется условие />, при этом цена />. Термин«покрытие» означает, что совокупность множеств /> содержит все элементы множества В,т.е. «покрывает» множество B
Безизбыточнымназывается покрытие, если при удалении из него хотя бы одного элемента оноперестает быть покрытием. Иначе — покрытие избыточно.
Покрытие Рназывается минимальным, если его цене /> — наименьшая среди всех покрытийданной задачи.
Покрытие Рназывается кратчайшим, если l — наименьшее среди всех покрытий данной задачи.
Удобным и нагляднымпредставлением исходных данных и их преобразований в задаче о покрытии являетсятаблица покрытий. Таблица покрытий — это матрица Т отношения принадлежностиэлементов множеств /> опорному множеству В. Столбцыматрицы сопоставлены элементам множества В, строки — элементам множества
А: />
Нули в матрице T не проставляются.
Имеются следующиеварианты формулировки задачи о покрытии:
1. Требуется найти всепокрытия. Для решения задачи необходимо выполнить полный перебор всехподмножеств множества А.
2. Требуется найти толькобезызбыточные покрытия. Не существует простого и эффективного алгоритма, нетребующего построения всех избыточных покрытий: хорошо, если уменьшается ихколичество. (Используется граничный перебор либо разложение по столбцу в ТП).
Требуется найти однобезизбыточное покрытие. Решение задачи основано на сокращении таблицы.
Задачи о покрытии могутбыть решены точно (при небольшой размерности) либо приближенно (см. [2] ).
Для нахождения точногорешения используются такие алгоритмы.
1) Алгоритм полногоперебора. (Основан на методе упорядочения перебора подмножеств множества А).
2) Алгоритм граничногоперебора по вогнутому множеству. (Основан на одноименном методе сокращенияперебора).
3) Алгоритм разложения постолбцу таблицы покрытия. Основан на методе сокращения перебора, которыйсостоит в рассмотрении только тех строк таблицы покрытия, в которых имеется«1» в выбранном для разложения столбце.
4) Алгоритм сокращениятаблицы покрытия. Основан на методе построения циклического остатка таблицыпокрытия, для которого далее покрытие строится методами граничного переборалибо разложения по столбцу.
Приближенное решениезадачи о покрытии основано на следующем соображении. Если даже сокращенныйперебор приводит к очень трудоемкому процессу решения, то для получения ответаприходится отказываться от гарантий построения оптимального решения(минимального либо кратчайшего); однако целесообразно получить не самый худшийрезультат — хотя бы безызбыточное покрытие, удовлетворяющее необходимомуусловию. При этом в ущерб качеству можно значительно упростить процесс решения.
Для случая построенияодного кратчайшего покрытия используется алгоритм построения циклическогоостатка таблицы покрытий и множества ядерных строк.
3.2 Словесное описание алгоритма и его работы
0) Считаем исходнуютаблицу покрытий текущей, а множество ядерных строк – пустым.
1) Находим ядерныестроки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем,вычеркивая ядерные строки и все столбцы, покрытые ими.
2) Вычеркиваемантиядерные строки.
3) Вычеркиваемпоглощающие столбцы.
4) Вычеркиваемпоглощаемые строки.
5) Если в результатевыполнения пунктов с 1 по 4 текущая таблица покрытий изменилась, сновавыполняем пункт 1, иначе преобразование заканчиваем.
Поэтому алгоритм работыследующий:
1) ввод числа строк истолбцов таблицы покрытия;
2) ввод таблицы покрытия;
3) поиск ядерных строк.Если их нет, то п.4. Иначе, запоминаем эти ядерные строки. Ищем столбцы,покрытые ядерными строками. Вычеркиваем все ядерные строки и столбцы, покрытыеими.
4) вычеркиваниеантиядерных строк. Переход в п.5.
6) вычеркиваниепоглощающих столбцов.
7) вычеркиваниепоглощаемых строк.
8) если в результатепреобразований таблица покрытий изменилась, выполняем пункт 3. Иначе — вывод множествапокрытия, конец алгоритма.
3.3 Выбор структур данных
Из анализазадачи и ее данных видно, что алгоритм должен работать с таблицей покрытия и снекоторыми переменными, которые представлены ниже (все переменные целого типа):
m – количество строк таблицыпокрытия;
n – количество столбцовтаблицы покрытия;
i, j – переменные цикла построкам и столбцам соответственно;
Sprev – предыдущая суммастолбца либо строки;
Scurr – текущая сумма столбцалибо строки.
Таблицапокрытия — это двумерная матрица. Ее целесообразно представить в видедвумерного массива A(m,n).
P — одномерный массив дляхранения номеров строк, покрывающих матрицу. Для хранения номеров выбранмассив, поскольку количество строк, хотя и неизвестно заранее, ограниченоколичеством строк матрицы покрытия (m).
3.4 Описание схемыалгоритма
Блок-схемаданного алгоритма изображена на рис. 3 в Приложении.
Сначалавводятся исходные данные: размерность таблицы m и n и сама таблица покрытия(блок 1). Далее происходит поиск пустого столбца (блок 2): это целесообразно,поскольку, если хотя бы один столбец не покрыт, то и не существует покрытияданной таблицы, и, следовательно, конец алгоритма. Далее, если не найденопустого столбца (проверка в блоке 3), — поиск ядерных строк (блок 4), после–столбцов, покрытых ими (блок 5). После этого вычеркиваются все столбцы истроки, найденные в блоках 4,5 (блок 6).Вычеркиваются антиядерные строки (блок7). Вычеркиваются поглощающие столбцы (блок 8). Вычеркиваются поглощаемыестроки (блок 9). Если в результате выполнения блоков 6-9 текущая таблицапокрытий изменилась, то выполняется блок 4; иначе следует вывод найденногократчайшего покрытия в виде номеров строк, покрывающих таблицу. Затем конецалгоритма.
3.5 Подпрограммыосновного алгоритма
Функция MOJNO_LI(A) ведет поиск пустыхстолбцов, то есть не покрываемых ни одной строкой. Блок-схема этой функциипредставлена на рис. 3.1 Приложения. Организуется цикл по всем столбцам (блоки1-6). В каждом столбце идет счет нулей (счетчик l инициализируется вкаждом проходе — блок 2; счет ведется в блоке 5), то есть если встречается хотябы одна единица (проверка в блоке 3), то происходит переход в следующийстолбец. Алгоритм работает до тех пор, пока не будет достигнут конец таблицы(то есть конец цикла по j, блок6) либо пока не будет сосчитано m нулей в одном столбце(проверка условия в блоке 4), то есть l=m. Функция возвращает 0, если найдено m нулей, и 1, еслидостигнут конец таблицы.
Функция YAD-LINE(A) ведет поиск ядерныхстрок… В блоке 1 Sинициализируется значением 0. Далее организуетсяцикл по всем столбцам (блок 2). Обнуляем текущую сумму (блок 4) и считаем суммув j-м столбце (цикл в блоках5-7 и собственно суммирование элементов в блоке 6). Далее сравниваем полученнуюсумму Sс 1 (блок 8). Если текущая сумма равна 1, запоминаем её и номеру этого столбцаприсваиваем 0 (блок 9. Таким образом, по окончании цикла по j в переменной yad_line(A) будет хранится массивядерных строк. Блок-схема данного алгоритма изображена на рис. 3.2 вПриложении.
Функция ANTI_LINE ведет поиск антиядерныхстрок. Переменной S2 присваивается значение 0. Организовывается цикл по строкам.Ищется сумма каждой строки и если она равна 0, то строка вычеркивается. Еслинет, то переходим к следующей строке. Блок-схема данного алгоритма изображенана рис. 3.3 в Приложении.
Процедура ERASE(A) реализует вычеркиваниестолбцов, покрытых ядерными строками. Аналогично данная процедура работает идля самих ядерных строк, и для антиядерных строк, поглощающих столбцов,поглощаемых строк. Чтобы данный столбец (строку) «вычеркнуть», обходимо поставить1 на его (ее) пересечении с нулевой строкой (столбцом). Блок-схема данногоалгоритма изображена на рис. 3.4 в Приложении.
Процедура VIVOD(P) реализует выводполученного множества строк из массива P. Для этого организуетсяцикл по элементам массива Р (блоки 1-4), в котором проверяется отмечен ли номерстроки iединицей (блок 2). Если да, то выводится номер строки i (блок 3). Блок-схемаданного алгоритма изображена на рис. 3.5 в Приложении.
3.6 Пример работыалгоритма
Пусть заданатаблица покрытий (см. Таб. 3). Рассмотрим пример работы алгоритма.
Таб. 3. Пример. 1. Множествоядерных строк пустое.B B1 B2 B3 B4 B5 B6 А1 1 1 1 А2 1 1 1 A3 1 1 1 А4 1 1 1
2. Множествоантиядерных строк пустое .
3.Вычеркиваем столбцы В1, В3, В5, В6 как поглощающие
4.Вычеркиваем строку А2 как поглощенную.
Теперьтаблица покрытий будет иметь вид
(см. Таб .4)
Таб.4. В2 В4 А1 А3 1 А4 1
1. Множествоядерных строк Р={A3, A4}.
2. Множествоантиядерных строк А={А1}.
3. Множествопоглощающих столбцов пустое.
4. Множествопоглощаемых строк пустое.
Теперь таблица покрытийпримет вид (см. Таб 5) В2 В4 А3 1 А4 1
Таким образом кратчайшеепокрытие {A3,A4} Таб. 5.
4 АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ
4.1 Математическое описание задачи и методов её решения
Графом (G, X) называетсясовокупность двух конечных множеств: множества точек, которые называютсявершинами (X = {Х1,..., Хn}), и множества связей впарах вершин, которые называются дугами, или ребрами ( (Хi, Хj) Î G ) в зависимости отналичия или отсутствия направленности связи.
Ребром называются двевстречные дуги (Хi, Хj) и (Хj, Хi). На графе они изображаются однойлинией без стрелки. Ребро, или дуга, конечные вершины которого совпадают,называется петлей.
Если на каждом ребрезадается направление, то граф (G, Х) называется ориентированным. В противном случае графназывается неориентированным.
Две вершины, являющиесяконечными для некоторого ребра или некоторой дуги, называются смежными.Соответственно этот граф может быть представлен матрицей смежности либоматрицей инцидентности.
Матрицей инцидентностиназывается прямоугольная матрица с числом строк, равным числу вершин графа, и счислом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаютсяследующим образом: “1” ставится в случае если вершина vi, инцидентна ребру uj; “0” — в противномслучае.
Вершина и ребро (дуга)называются инцидентными друг другу, если вершина является для этого ребра(дуги) концевой точкой.
Путь из начальной вершиныхн к конечной вершине хк — последовательность дуг,начинающаяся в вершине хн Î Х, заканчивающаяся ввершине хк Î Х, и такая, что конец очередной дуги является началомследующей:
(хн, хi1)( хi1, хi2)( хi2… хik)( хik, xk) = (xн, хк).
Элементарный путь – путь,в котором вершины не повторяются.
Простой путь — путь, вкотором дуги не повторяются.
Маршрут — последовательность ребер, составляющих, как и путь, цепочку.
Длина пути взвешенногографа определяется как сумма весов — его дуг. Если граф не взвешен, то можносчитать веса дуг равными 1 .
Кратчайшим путем междувыделенной парой вершин хн и хк называется путь, имеющийнаименьшую длину среди всех возможных путей между этими вершинами.
Таким образом, нахождениекратчайшего пути – это поиск множества вершин, составляющих этот путь.
4.2 Словесное описание алгоритма и его работы
0. Инициализациякратчайших путей от вершины s до каждой вершины графа ∞, а все вершины 0, v=s.
1. Для каждой вершины u, смежной v, проверяем, отмечена лиона и какова длина пути между u и v. Если меньше, то запоминаем длину пути и текущую вершину u.
2. t= ∞, v=0. Для каждой вершиныграфа проверяем, отмечена ли она, и меньше ли путь от нее до s, чем t. Если так, то запоминаемеё v=u, и её путь t=T[u] .
3. Если v=0, то пути нет, иначеесли v=f, то путь найден и конецалгоритма.
4. Помечаем вершину v. Переход в п.1.
4.3 Выбор структур данных
Пусть p – количество вершин.Поскольку граф взвешен, то его представим в форме матрицы длин дуг:
С: array[1..p,1..p].
Используются следующиепеременные и массивы:
s, f – вершины, междукоторыми следует найти кратчайший путь;
u, v – переменные циклов повершинам;
T: array[1..p] of real – вектор, если вершина v лежит на кратчайшем путиот s к t, то T[v] – длина кратчайшегопути от sк v;
H: array[1..p] of 0..p – вектор, H[v] – вершина,непосредственно предшествующая v на кратчайшем пути;
X: array[1..p] of 0..1 – вектор метоквершин.
4.4 Описание схемы алгоритма
Блок-схема данногоалгоритма изображена на рис. 4 в Приложении.
В блоке 1 происходит вводграфа в форме матрицы длин дуг, а также номеров вершин s и f. Далее организуется циклпо вершинам графа (блок 2). В нем инициализируются массив кратчайших путей имассив меток (блок 3): поскольку пути не известны, то они инициализируютсябесконечностью, а метки – нулем. Далее отмечается вершина s, кратчайший путь от неёдо неё же самой равен 0, и ей никто не предшествует; текущей вершиной v становится s (блок 5). Далееорганизовывается цикл по смежным с текущей вершинам (блок 6). В блоке 7происходит проверка смежны ли вершины. В блоке 8 сравнивается уже имеющийсяпуть с путем между u и v. Если текущий меньше, то он и номер вершины запоминаются (блок9).
В остальных блокахпроисходит поиск конца кратчайшего пути. Изначально его длина не известна(равна ∞), и вершина, оканчивающая его также не известна (блок 11). Вблоке 12 организуется цикл по всем неотмеченным вершинам. В блоке 13производиться сравнение уже имеющегося кратчайшего пути t с текущим T[u]. Если текущий меньше,то запоминаем его и вершину (блок 14). Далее производится анализ полученногоконца пути. Если v=0 (блок 16), то не была найдена вершина конца кратчайшего пути,и, следовательно, нет такого пути (блок 17). Если же v=f (блок 18), то есть конецсовпадает с заданной вершиной, то между ними существует кратчайший путь (блок19). В обоих случаях конец алгоритма.
Если же не достигнутазаданная вершина f, то текущая вершина v помечается (блок 20) и переход в блок 6.
Алгоритм работает, покане будет вершина t либо пока не станет ясно, что пути из s в f нет.
4.5 Контрольный пример решения задачи с помощью алгоритмапоиска кратчайшего пути
Пусть задан граф,изображенный на рис. 1. Рассмотрим на этом примере работу алгоритма.
0.for v=1..p
T[v]=∞;
/>X[v]=0;
H[s]=0;
T[s]=0;
X[s]=1;
v=s;
1.X2 € G(1) →
X[2]=0&(∞>0+4)→
T[2]=T[1]+C[1,2]=4;
H[2]=1;
X3€ G(1) →
X[3]=0&(∞>0+5)→
T[3]=T[1]+C[1,3]=5;
H[3]=1;
2.t=∞; v=0;
foru=1..p
X[2]=0&T[2]=4
v=2;t=T[2]=4;
X[3]=0&T[3]=5!
3.v=2≠0;
v=2≠f=6;
4.X[2]=1 → п.1;
1.X4 € G(2) →
X[4]=0&(∞>0+2)→
T[4]=T[2]+C[2,4]=6;
H[4]=2;
2.t=∞; v=0;
foru=1..p
X[4]=0&T[4]=6
v=4;t=T[4]=6;
3.v=4≠0;
v=4≠f=6;
4.X[4]=1 → п.1;
1.X3 € G(4) →
X[3]=0&(5!>6+3)
X5€ G(4) →
X[5]=0&(∞>0+7)→
T[5]=T[4]+C[4,5]=13;
H[5]=4;
X6€ G(4) →
X[6]=0&(∞>0+1)→
T[6]=T[4]+C[4,6]=7;
H[6]=4;
2.t=∞; v=0;
foru=1..p
X[3]=0&T[3]=5
v=3;t=T[3]=5;
X[5]=0&T[5]=13!
X[6]=0&T[6]=1
v=5;t=T[5]=7;
3. v=6≠0;
v=6=f=6; → конецалгоритма.
ЗАКЛЮЧЕНИЕ
В даннойработе разработаны алгоритмы сортировки, поиска кратчайшего пути в графе ипоиска покрытия, близкого к кратчайшему. Алгоритмы исполнены с нужной степеньюдетализации, необходимой для понимания их работы. Рассмотрены пути улучшенияэффективности каждого алгоритма учитывая требования конкретной задачи.
Большоевнимание уделено сравнению возможного использования нескольких структур данных,проведён анализ эффективности работы алгоритма в зависимости от используемойструктуры.
Рассмотренасложность каждого алгоритма, её зависимость от условий данной задачи, методыупрощения и облегчения понимания алгоритма.
ЛИТЕРАТУРА
1. Вирт Н. Алгоритмы и структуры данных. – С.-П.:Невский диалект, 2001. – 350 с.
2. Новиков Ф.А. Дискретная математика дляпрограммистов. – С.-П.: Питер, 2003.–292 с.
3. Шендрик Е.В. Конспект лекций по дисциплине«Теория алгоритмов». – Одесса, 2003.