Навигация
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}.
Похожие работы
... 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути. 3) (Y mod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер. 2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР 2.1 Математическое описание задачи Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию. Сортировка используется для ...
... распределения материальных благ и развития промышленного производства (сельского хозяйства, здравоохранения, связи и т. п.). Рис. 8.3. Структура системы управления общественным производством В реализации задачи инновационный менеджмент занимает специфическую и важную роль в установлении критериев и путей развития. 1 – Сбор данных и выделение ошибок. 2 – Анализ последствий ...
... телеги, микропроцессорные системы и т.д. В данном дипломном проекте поставлена задача оптимизировать сборку телеги, а также выявить экономический эффект за счет инноваций технологии и экономии ресурсов. Рассмотрим основные составляющие телеги: - Полка ТМ.201.01.03 – 24 шт. – Лист Б-О-ПН-2,0 ГОСТ 19903-74/12Х18Н10Т ГОСТ 5582-75; - Заглушка ТМ.201.01.09 – ...
... руководителя. Большое внимание следует уделять мотивации управленческого труда. 56. Организационно-распорядительные методы управления (Или административные). С их помощью осуществляются регулирующие функции гос-ва. Основаны на исполнении обязательных предписаний и рекомендаций, позволяют оперативно воздействовать на ход событий в процессе упр-я, ср-во волевого и конкретного воздействия ( ...
0 комментариев