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