Введение
Теорияалгоритмов и практика их построения и анализа является концептуальной основойразнообразных процессов обработки информации. В настоящее время теорияалгоритмов образует теоретический фундамент вычислительных наук. Применениетеории алгоритмов осуществляется как в использовании самих результатов(особенно это касается использования разработанных алгоритмов), так и в обнаруженииновых понятий и уточнении старых. С ее помощью проясняются такие понятия какдоказуемость, эффективность, разрешимость, перечислимость и другие.
Фактически,алгоритм – это точно определенная (однозначная) последовательность простых(элементарных) действий, обеспечивающих решение любой задачи из некоторогокласса, т.е. такой набор инструкций, который можно реализовать чистомеханически, вне зависимости от умственных способностей и возможностейисполнителя.
Как заметилКнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям могследовать даже компьютер».
Эффективностьалгоритма определяется анализом, который должен дать четкое представление,во-первых, о емкостной и, во-вторых, о временной сложности процесса.
Речь идет оразмерах памяти, в которой предстоит размещать все данные, участвующие ввычислительном процессе (естественно, к ним относятся входные наборы,промежуточная и выходная информация), а также физических ресурсах, затраченныхисполнителем.
В курсовойработе представлены различные подходы и методы использования алгоритмов,приведены оценки сложностей алгоритмов, реализации математических задач спомощью алгоритмов. Проведена краткая характеристика используемых структурданных, эффективность их применения в данной задаче
1. Выборварианта задания
В основе выбора индивидуального варианта задания лежит процедураопределения целочисленного остатка от деления выражения Y, образованного суммойномера студента по журнальному списку и числом Х, полученным умножениемпоследней цифры номера группы на 100. После определения значения выражения Y находится остаток отделения для соответствующего списка алгоритмов:
Y mod 4 + 1 – алгоритмы покрытия;
Y mod 6 + 1 – алгоритмы на графах;
Y mod 5 + 1– алгоритмы сортировки.
Мой номер пожурнальному списку равен 5, группа АЕ-035. Поэтому имеем Y=5+5*100=505. Получаемтакие варианты:
А = 505 mod 4+1 = 2;
B= 505 mod 6 +1 = 2;
C= 505 mod 5 +1 = 1.
Такимобразом, имеем следующие алгоритмы: покрытия – по методу «построение одногократчайшего покрытия», на графах – нахождение самого длинного пути, сортировки –простыми включениями.
Постановказадачи. Необходимо ввести таблицу покрытия. Алгоритм должен найти покрытие,близкое к кратчайшему.
2.Алгоритм сортировки
2.1Математическое описание задачи и методов её решения
В общемсмысле сортировку следует понимать как процесс перегруппировки заданногомножества объектов в некотором определенном порядке. Её цель – облегчитьпоследующий поиск элементов в таком отсортированном множестве.
Если у насесть элементы а1, …, аn, то сортировка есть перестановка этих элементовв массив ак1, …, акn, где при некоторойупорядочивающей функции f выполняются отношения f(ak1)≤f(ak2)≤…≤f(akn).
Методсортировки называется устойчивым, если в её процессе относительное расположениеэлементов с равными ключами не изменяется.
Существуюттакие алгоритмы сортировок массива: сортировка с помощью прямого включения,прямого выбора, прямого обмена, включений с уменьшающимися расстояниями,дерева, разделения и другие.
2.2Словесное описание алгоритма и его работы
В силупростоты алгоритм сортировки простыми включениями не требует разделения наподпрограммы.
Элементымысленно делятся на уже «готовую» последовательность а1…а2и исходную последовательность а1…аn. При каждом шаге, начинаяс i=2 и увеличивая i каждый раз на единицу,из исходной последовательности извлекается i-й элемент иперекладывается в готовую последовательность, при этом он вставляется в нужноеместо.
Словесноеописание алгоритма сортировки простыми включениями:
0. В готовуюподпоследовательность записывается а1, во входную – а2,….аn.
1. i = 2.
2 Переносим элемент х = аиз входной подпоследовательности в готовую так, чтобы готоваяподпоследовательность осталась под сортированной. Для этого:
а) расширяем готовуюподпоследовательность слева: а0= х – барьер;
б) просматривая элементыготовой подпоследовательности слева направо, находим такой номер j что и ai
в) если j=j-1, то переходим к пунктуг), иначе расширяем готовую
подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо;
г) ai+1 = x
д) i = i + 1. Если i
Процесс можетзакончиться при двух различных условиях: 1) найден элемент с ключом, меньшим,чем ключ x;2) достигнут конец готовой последовательности. Получается цикл с двумяусловиями. Поэтому для некоторого улучшения быстродействия применяется барьер –a[0] присваиваетсязначение ключа x.
Проанализируемэтот алгоритм. Число сравнений (Сi) при i-м просеивании самое большее равно i-1, самое меньшее – 1;если предположить, что все перестановки из n ключей равновероятны, тосреднее число сравнения – i/2. Число же пересылок (присваиваний элементов) Mi равно Сi+2 (включая барьер).Поэтому общее число сравнений и число пересылок таковы:
Сmin=n-1, Mmin=3*(n-1)
Cave=(n2+n-2)/4, Mave=(n2+*n-10)/4,
Cmax=(n2+n-4)/4, Mmax=(n2+3n-4)/2.
Минимальныеоценки в случае уже упорядоченной исходной последовательности элементов,наихудшие же оценки – когда они первоначально расположены в обратном порядке.Очевидно, что приведенный алгоритм описывает метод устойчивой сортировки (см.[1]).
Этот алгоритмможно легко улучшить, поскольку готовая последовательность сама ужеупорядочена. Поэтому при поиске подходящей позиции для i-го ключа целесообразноиспользовать двоичный поиск. При этом такой модифицированный алгоритм носитназвание метода с двоичным включением.
Словесное описаниеалгоритма сортировки с двоичным включением:
0. В готовуюподпоследовательность записывается а1, во входную а2,….аn.
1. i = 2
2 Переносим элементх=аi из входной подпоследовательности в готовую так, чтобы последняяосталась под сортированной. Для этого:
а) организуем бинарныйпоиск места включения х в готовую подпоследовательность: находим срединныйэлемент готовой подпоследовательности – am, где m =] i/2 (, и сравниваемего с х. Если am > х то ведем далее поиск в левой половине готовойподпоследовательности, т.е. опять находим срединный элемент и сравниваемего с х и т.д., пока не найдем номер j такой, что ai
б) если j=j-1, то переходим к пунктув), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы,начиная с ai вправо;
в) ai+1 = х
3. i=i+1. Если i
Делениепополам производится i*log2i. Число сравнений практически не зависит от начальногопорядка элементов. В нижней части последовательности место включенияотыскивается несколько быстрее, чем в верхней, поэтому предпочтительнаситуация, когда элементы немного упорядочены. Фактически, если элементы вобратном порядке, потребуется минимальное число сравнений, если уже упорядочены– максимальное:
C≈n*log2(log2-log2e±0,5).Однако числопересылок так и остается порядка n2. И на самом деле сортировка уже упорядоченногомассива потребует больше времени, чем метод с прямыми включениями (см. [1]).
2.3 Выборструктур данных
Алгоритмысортировки очень сильно зависят от структуры данных, так что выделяют двакласса: сортировку массивов и сортировку последовательностей (файлов). В даннойработе рассматривается сортировка массивов. Тип данных «массив» удобен тем, чтохранится во внутренней памяти и имеет случайный доступ к элементам, то естьболее быстрый, чем у последовательности. Поэтому массивы целесообразноиспользовать для хранения небольших, часто используемых множеств.
Обычноупорядочивающая функция не вычисляется по какому-либо правилу, а хранится какявная компонента (поле) каждого элемента. Её значение называется ключом элемента.Поэтому для представления элемента хорошо подходит тип «запись», что на языке «Pascal» выглядит следующимобразом:
TYPEitem = RECORD key: INTEGER;
{здесьописаны другие компоненты}
END;
Поскольку валгоритме сортировки используется только ключ элемента, то остальную информациюоб элементе можно опустить – считаем, что тип элемента определен как INTEGER. Можно выбрать и другойтип, на котором определено общее отношение порядка.
Из вышесказанного следует, что в процессе работы потребуются следующие переменные:
n – количество элементовмассива;
A – сортируемый массив;
i – переменная цикла (поисходной последовательности);
j – переменная внутреннегоцикла (по готовой последовательности);
x – i-й ключ (переносимыйэлемент).
Всепеременные целого типа.
2.4Описание схемы алгоритма
Блок-схемаданного алгоритма изображена на рис. 2 в Приложении.
Алгоритмработает следующим образом. Сначала вводятся исходные данные: длина массива иего элементы (блоки 1, 2), затем организуется цикл по всей длине массива, вовремя которого ставится «барьер» (блок 3) и проводится сравнение i-го ключа с элементамиготовой последовательности (стоящими раньше него). При этом все элементы,большие этого ключа (это условие проверяется в блоке 4), сдвигаются вправо(блок 5). Это происходит до тех пор, пока не встретится элемент меньший либоравный данному ключу (по крайней мере барьеру). Тогда i-й ключ вставляется в этупозицию (блок 6).
2.5 Контрольные примеры решения задачи с помощью алгоритмасортировки простыми включениями
Пример сортировки массива, отсортированного случайным образом.
Пусть задан такой массив из восьми элементов:(32,43,2,30,82,8,5,52) (см. Таб. 1).Начальные ключи 32 43 02 30 82 08 05 52 i = 2 32 43 02 30 82 08 05 52 i = 3 02 32 43 30 82 08 05 52 i = 4 02 30 32 43 82 08 05 52 i = 5 02 30 32 43 82 08 05 52 i = 6 02 08 30 32 43 82 05 52 i = 7 02 05 08 30 32 43 82 52 i = 8 02 05 08 30 32 43 52 82
Пошаговоерешение:
Шаг 1:
1) i=2;
2) x=43; a[0]=43; j=1;
3)x > a[j]=32;
3.2) a[2]= 43;
4)i=3; i ≤ n=8 → п. 2;
Шаг 2:
2) x=2; a[0]=2;j=2;
3)x
3.1)a[3]=43; j=1; → п. 3;
3)x
3.1)a[2]=32; j=0; → п. 3;
3)x = a[j];
3.2)a[1]=2;
4)i=4; i
Шаг 3:
2)x=30; a[0]=30; j=3;
3)x
3.1)a[4]=43; j=2; → п. 3;
3)x
3.1)a[3]=32; j=1; → п. 3;
3)x > a[1]=2
3.2)a[2]=30;
4)i=5; i
Шаг 4:
2)x=82; a[0]=82; j=4;
3)x > a[j];
3.2)a[5] = 82;
4)i=6; i
Шаг 5:
2)x=8; a[0]=8; j=5;
3)x
3.1)a[6]=82; j=4; → п. 3;
3)x
3.1)a[5]=43; j=3; → п. 3;
3)x
3.1)a[4]=32; j=2; → п. 3;
3)x
3.1)a[3]=30; j=1; → п. 3;
3)x > a[j]=2;
3.2)a[2]=8;
4)i=7; i
Шаг 6:
2)x=5; a[0]=5; j=6;
3)x
3.1)a[7]=82; j=5; → п. 3;
3)x
3.1)a[6]=43; j=4; → п. 3;
3)x
3.1)a[5]=32; j=3; → п. 3;
3)x
3.1)a[4]=30; j=2; → п. 3;
3)x
3.1)a[3]=8; j=1; → п. 3;
3)x > a[j]=2;
3.2)a[2]=5;
4)i=8; i≤n → п. 2;
Шаг 7:
2)x=52; a[0]=52; j=7;
3)x
3.1)a[8]=82; j=6; → п. 3;
3)x > a[j]=43;
3.2)a[7]=52;
4) i=9; i>n → конец алгоритма.
Такимобразом, имеем 21 пересылку элементов и 20 сравнений.
Примерсортировки уже отсортированного массива.
Пусть задан такой массив из восьми элементов:(2,5,8,30,32,43,52,82).
Пошаговоерешение:
Шаг 1:
1) i=2;
2) x=5; a[0]=2; j=1;
3)x > a[j]=2;
3.2)a[2]=5;
4)i=3; i
Шаг 2:
2)x=8; a[0]=8; j=2;
3)x > a[j]=5;
3.2)a[3]=8;
4)i=4; i
Шаг 3:
2)x=30; a[0]=30; j=3;
3)x > a[j]=8;
3.2)a[4]=30;
4)i=5; i
Шаг 4:
2)x=32; a[0]=32; j=4;
3)x > a[j]=30;
3.2)a[5]=32;
4)i=6; i
Шаг 5:
2)x=43; a[0]=43; j=5;
3)x > a[j]=32;
3.2)a[6]=43;
4)i=7; i
Шаг 6:
2)x=52; a[0]=52; j=6;
3)x > a[j]=43;
3.2)a[7]=52;
4)i=8; i≤n → п. 3;
Шаг 7
2)x=82; a[0]=82; j=7;
3)x > a[j]=52;
3.2)a[8]=82;
4)i=9; i>n →конец алгоритма.
Таким образомполучили 7 пересылок и 7 сравнений.
Примерсортировки массива, отсортированного в обратном порядке.
Пусть задан такой массив из восьми элементов:(82,52,43,32,30,8,5,2).
Пошаговоерешение:
Шаг 1:
1) i=2;
2) x=52; a[0]=52; j=1;
3)x
3.1)a[2]=82; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=52;
4)i=3; i
Шаг 2:
2)x=43; a[0]=43; j=2;
3)x
3.1)a[3]=82; j=1; → п. 3;
3)x
3.1)a[2]=52; j=0; → п. 3;
3)x = a[j];
3.2)a[1]=43;
4)i=4; i
Шаг 3:
2)x=32; a[0]=32; j=3;
3)x
3.1)a[4]=82; j=2; → п. 3;
3)x
3.1)a[3]=52; j=1; → п. 3;
3)x
3.1)a[2]=43; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=32;
4)i=5; i
Шаг 4:
2)x=30; a[0]=30; j=4;
3)x
3.1)a[5]=82; j=3; → п. 3;
3)x
3.1)a[4]=52; j=2; → п. 3;
3)x
3.1)a[3]=43; j=1; → п. 3;
3)x
3.1)a[2]=32; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=30;
4)i=6; i
Шаг 5:
2)x=8; a[0]=8; j=5;
3)x
3.1)a[6]=82; j=4; → п. 3;
3)x
3.1)a[5]=52; j=3; → п. 3;
3)x
3.1)a[4]=43; j=2; → п. 3;
3)x
3.1)a[3]=32; j=1; → п. 3;
3)x
3.1)a[2]=30; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=8;
4)i=7; i
Шаг 6:
2)x=5; a[0]=5; j=6;
3)x
3.1)a[7]=82; j=5; → п. 3;
3)x
3.1)a[6]=52; j=4; → п. 3;
3)x
3.1)a[5]=43; j=3; → п. 3;
3)x
3.1)a[4]=32; j=2; → п. 3;
3)x
3.1)a[3]=30; j=1; → п. 3;
3)x
3.1)a[2]=8; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=5;
4)i=8; i
Шаг 7:
2)x=2; a[0]=2; j=7;
3)x
3.1)a[8]=82; j=6; → п. 3;
3)x
3.1)a[7]=52; j=5; → п. 3;
3)x
3.1)a[6]=43; j=4; → п. 3;
3)x
3.1)a[5]=32; j=3; → п. 3;
3)x
3.1)a[4]=30; j=2; → п. 3;
3)x
3.1)a[3]=8; j=1; → п. 3;
3)x
3.1)a[2]=5; j=0; → п. 3;
3)x=a[j];
3.2)a[1]=2;
4)i=9; i>n → конец алгоритма.
Такимобразом, имеем 35 сравнений и 35 пересылок.
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). В каждом столбцеидет счет нулей (счетчик i инициализируется в каждом проходе – блок 2; счет ведется вблоке 5), то есть если встречается хотя бы одна единица (проверка в блоке 3),то происходит переход в следующий столбец. Алгоритм работает до тех пор, покане будет достигнут конец таблицы (то есть конец цикла по j, блок6) либо пока небудет сосчитано m нулей в одном столбце (проверка условия в блоке 4), то есть i=m. Функция возвращает 0,если найдено mнулей, и 1, если достигнут конец таблицы.
Функция YAD-STROKA(A) ведет поиск ядерных строк. В блоке 1 Sинициализируетсязначением 0. Далее организуется цикл по всем столбцам (блок 2). Обнуляемтекущую сумму (блок 4) и считаем сумму в j-м столбце (цикл в блоках5–7 и собственно суммирование элементов в блоке 6). Далее сравниваем полученнуюсумму Sс 1 (блок 8). Если текущая сумма равна 1, запоминаем её и номеру этого столбца присваиваем0 (блок 9), иначе переходим к следующему столбцу. Таким образом, по окончаниицикла по jв переменной yad stroka(A)будет храниться массив ядерных строк. Блок-схема данного алгоритма изображенана рис. 3.2 в Приложении.
Функция ANTI_STROK(A) ведет поиск антиядерныхстрок. Переменной S2 присваивается значение 0. Организовывается цикл по строкам.Ищется сумма каждой строки и если она равна 0, то строка вычеркивается. Если нет,то переходим к следующей строке. Блок-схема данного алгоритма изображена нарис. 3.3 в Приложении.
Процедура VICHEK(A) реализует вычеркиваниестолбцов, покрытых ядерными строками. Аналогично данная процедура работает идля самих ядерных строк, и для антиядерных строк, поглощающих столбцов,поглощаемых строк. Чтобы данный столбец (строку) «вычеркнуть», необходимо поставить1 на его (ее) пересечении с нулевой строкой (столбцом). Блок-схема данногоалгоритма изображена на рис. 3.4 в Приложении.
Процедура VIVOD(P) реализует выводполученного множества строк из массива P. Для этого организуетсяцикл по элементам массива Р (блоки 1–4), в котором проверяется отмечен ли номерстроки iединицей (блок 2). Если да, то выводится номер строки i (блок 3). Блок-схема данногоалгоритма изображена на рис. 3.5 в Приложении.
3.6 Примерработы алгоритма
Пусть заданатаблица покрытий (см. Таб. 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)
Таб. 5. В2 В4 А3 1 А4 1
Таким образом кратчайшеепокрытие {A3,A4}.
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.
Кратчайшим путем междувыделенной парой вершин хн и хк называется путь, имеющийнаименьшую длину среди всех возможных путей между этими вершинами.
При построениидлиннейшего пути рассматриваются элементарные или простые длиннейшие пути,длиннейшие пути с заданным числом выполненных циклов. Длиннейший путь между хни хк – путь, имеющий наибольшую длину среди всех возможных путеймежду этими вершинами.
Таким образом, нахождениедлиннейшего пути – это поиск множества вершин, составляющих этот путь.
Волновой алгоритм получилсвое название из-за того, что сам принцип его функционирования основан на «испусканииволны,» какого-либо гипотетического возмущения по результатам которого имеетсявозможность судить о количестве смежных с выделенной вершин, а так же орасстоянии (длине дуги) до каждой из них.
Очевидно, что к каждойвершине могут идти от вершины X н несколько путей, суммы длин дуг поразным путям различны. При поиске длиннейшего пути следует выбиратьмаксимальную сумму. Волны распространения веса по разным путям доходят докаждой вершины последовательно, при очередной волне необходимо оставить либостарый вес вершины, либо заменить его на новый (больший). Поэтому при расчетевеса вершины X i за счет волны, подошедшей к ней по дуге (X j,X i), производится вычисление веса V i по формуле V i=max (V i, V j + l ji).
Веса вершин в процессе распространенияволны могут меняться неоднократно. При каждом изменении веса V iвершины это увеличение веса необходимо передать вершинам исхода X i,т.е. необходимы специальные средства, отражающие факты получения вершинойнового веса и передачу его другим вершинам. В качестве такого средстваиспользуется массив номеров вершин, получивших новый вес (при каждом изменениивеса номер вершины включается в этот массив, если его там не было, при передачивеса исключается).
4.2 Словесное описаниеалгоритма и его работы
1. Все вершины графаполучают веса V i=0, номер вершины X нзаносится в массив М номеров вершин, изменивших вес. Остальные вершины X iне попадают в массив М.
2. Если массив М пуст,выполняется п. 3, иначе выбирается с исключением из его очередная вершинаX i и пересчитываются веса вершин, принадлежащих исходу G (X i)вершины X i:
/>
Если вес V j изменяется,то номер j включается с приведением подобных в М. Снова выполняется п. 2.
3. Если вес />, то делается вывод, чтопути из вершины X н к вершине X k не существует, иначевыполняется процедура выделения дуг, двигаясь в обратном порядке проверяемвыполняется ли условие X i – X j = l ij, длявходов /> вершины X i,если оно выполняется, то вершина X j и дуга l ij выделяются.
4. После выделения дугстроятся длиннейшие пути, длины которых равны V k.
При построении длиннейшихпутей рассматриваются элементарные или простые длиннейшие пути,длиннейшие пути с заданным числом выполнения циклов.
4.3 Структуры данных
Из самой структурыалгоритма очевидно, что для его функционирования необходимы:
1. Массив В-массивдуг-связностей в ячейках с номерами i, j которого будет находиться вес соответствующей дуги l ij.
2. МассивМ – массив изменивших свой вес вершин.
3. МассивЕ – массив содержащий значения весов и состояний вершин.
4. МассивР – массив содержащий выделенные дуги.
5. Рядиндексных переменных необходимых для перемещения по массивам В, Е, Р, а такжесодержащие индекс текущей вершины, и ряд буферных переменных необходимых длятекущих арифметических и циклических операций (все индексы должны бытьцелочисленного типа).
4.4 Контрольный пример
Для подробного описаниядействия волнового алгоритма поиска длиннейшего пути воспользуемся графомзадаваемым таблице связностей: X1 X2 X3 X4 X5 X6 X1 1 4 X2 2 5 X3 2 4 X4 1 4 X5 2 X6
Таким образом, знаятаблицу связностей можно построить граф для более наглядной иллюстрациипримера:
Итак, на первом проходе волновогоалгоритма выполняется пункт 1, т.е. устанавливаются значения весов всех вершинв нуль, и помещает в массив М индекс начальной вершины, математически это можнозаписать так:
Шаг №1:
П. 1: />
На втором проходе, т. к.М0, выполняется пункт 2, из массива М забирается первый элемент, этотиндекс присваивается индексной переменной i составляется множество исходов длявершины Х i, а затем вычисляются веса смежных вершин:
Шаг №2:
П. 2: />
/>
/>
Как видно из приведенныхзаписей, в результате этого прохода две вершины: вторая и третья получили новыевеса, и соответственно в массив М попали их индексы, так как до этого они в немне содержались. (В дальнейшем для краткости изложения будут приводитьсяпреимущественно математические записи работы алгоритма).
Шаг №3:
П. 2: />
/>
/>
Следует отметить, что врезультате этого прохода вершина Х 3 не поменяла своего веса, таккак уже имела максимально возможный.
Шаг №4:
П. 2: />
/>
/>
Шаг №5:
П. 2: />
/>
/>
Шаг №6:
П. 2: />
/>
Шаг №7:
П. 2: />
Шаг №8:
П. 2: М=0,выполняется п. 3.
Итак, на данный моментполучен граф, все вершины которого приобрели максимально возможные значения. Атак как массив изменивших вес вершин пуст, то управление передается третьемупункту алгоритма, который отмечает длиннейший путь. Следует особо отметить, что,как видно из предыдущих вычислений, максимальные веса вершин могут бытьдостигнуты при продвижению по разным дугам. Для большей наглядности примераниже приведен вид графа на данном этапе:
На этапе выполнениятретьего пункта алгоритма критерием для выделения дуги, как и для алгоритманахождения кратчайшего пути, является совпадение разности весов соответствующихвершин с весом самой дуги. Таким образом, начиная с вершины Х6 получим:
Шаг №9: Для выделеннойвершины />
П. 3: />
/>, поэтому дуга /> выделяется.
/>, и дуга />выделяется, одновременно выделяютсявершины /> и />.
Шаг №10: Для выделеннойвершины />
П. 3: />
/>, поэтому дуга /> не выделяется.
/>, и дуга />выделяется, одновременно
выделяется вершина />.
Шаг №11: Для выделеннойвершины />
П. 3: />
/>, поэтому дуга /> выделяется.
/>, и дуга />выделяется, одновременно выделяетсявершина />, следует отметить, чтовершина /> не выделяется, так как ужевыделена.
Шаг №12: Для выделеннойвершины />
П. 3: />
/>, поэтому дуга /> не выделяется.
/>, и дуга />выделяется, одновременно выделяетсявершина />.
Шаг №13: Для выделеннойвершины />
П. 3: />
/>, и дуга />выделяется, следует отметить,что вершина /> не выделяется, так как ужевыделена.
Шаг №14: Для выделеннойвершины />
П. 3: />
Так как в данную вершинуне входит не оной дуги и больше нет отмеченных вершин, переходим к этапусоставления длиннейшего пути.
Итак соединяя дуги по принципу:конечный индекс предыдущей – начальный последующий, получаем три длиннейшихпутей /> длиной 10:
1. />
2. />
3. />
Для большей наглядностиизобразим граф в своем конечном состоянии, нанеся на него значения весоввершин, веса дуг, а так же выделив длиннейшие пути и вычисление длин дуг этихпутей:
Приведем табличный методзаписи процесса:
/>
Заключение
В даннойработе разработаны алгоритмы сортировки, поиска длиннейшего пути во взвешенном графеи поиска покрытия, близкого к кратчайшему. Алгоритмы исполнены с нужнойстепенью детализации, необходимой для понимания их работы. Рассмотрены путиулучшения эффективности каждого алгоритма учитывая требования конкретнойзадачи.
Большоевнимание уделено сравнению возможного использования нескольких структур данных,проведён анализ эффективности работы алгоритма в зависимости от используемойструктуры.
Рассмотренасложность каждого алгоритма, её зависимость от условий данной задачи, методыупрощения и облегчения понимания алгоритма.