Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему
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). Рассмотрим пример работы алгоритма.
|
| B | B1 | B2 | B3 | B4 | B5 | B6 |
|
А1 |
1 | 1 |
1 | |||
|
К-во Просмотров: 354
Бесплатно скачать Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему
|