Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему (стр. 3 из 4)

m – количество строк таблицы покрытия;

n– количество столбцов таблицы покрытия;

i, j – переменные цикла по строкам и столбцам соответственно;

S_prev – предыдущая сумма столбца либо строки;

S_curr – текущая сумма столбца либо строки.

Таблица покрытия – это двумерная матрица. Ее целесообразно представить в виде двумерного массива 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 в переменной yadstroka(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 = {Х₁,…, Х_n}), и множества связей в парах вершин, которые называются дугами, или ребрами ((Х_i, Х_j) ÎG) в зависимости от наличия или отсутствия направленности связи.

Ребром называются две встречные дуги (Х_i, Х_j) и (Х_j, Х_i). На графеони изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей.

Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.

Две вершины, являющиеся концевыми для некоторого ребра или некоторой дуги, называются смежными. Соответственно этот граф может быть представлен матрицей смежности либо матрицей инцидентности.

Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: «1» ставится в случае если вершина v_i, инцидентна ребру u_j; «0» – в противном случае.

Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.

Путь из начальной вершины х_н к кончиной вершине х_к – последовательность дуг, начинающаяся в вершине х_н ÎХ, заканчивающаяся в вершине х_к ÎХ, и такая, что конец очередной дуги является началом следующей: (х_н, х_i1) (х_i1, х_i2) (х_i2… х_ik) (х_ik, x_k) = (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 выделяются.