Лабораторна робота № 2
Тема: Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом мінімального стовпчика - максимального рядка та методом ядерних рядків.
Мета: набути навиків застосування методу мінімального стовпчика - максимального рядка та методу ядерних рядків для побудови покриття на множинах.
Перелік рекомендованої літератури:
1. Горбашов В.А. Основы дискретной математики. - М.: Высшая школа, 1984.-311с.
2. Новоселов В. Т., Сташков А.В. Прикладная математика для
инженеров - системотехников. Дискретная математика в задачах и примерах.
Теоретичні відомості: Метод мінімального стовпчика - максимального рядка.
Покриття близьке до найкоротшого, дає наступний простий алгоритм перетворення таблиці покрить.
-
Вихідна таблиця вважається поточною перетвореною таблицею покрить, множина рядків покриття - порожня.
-
У поточної таблиці виділяється стовпчик з найменшим числом одиниць. Серед рядків, що містять одиниці в цьому стовпці, виділяється одна з найбільшим числом одиниць. Цей рядок включається в покриття, дана таблиця скорочується викреслюванням усіх стовпців, у яких обраний рядок має одиниці. Якщо в таблиці є не викреслені стовпці, то виконується п.2, інакше покриття побудоване. Помітимо, що при підрахунку числа одиниць у рядку враховуються одиниці в не викреслених стовпцях.
Метод ядерних рядків
1.2.6. Сокращение таблицы покрытий до циклической.
Теоремы о сокращении таблицы покрытий. Объем перебора существенно зависит от размеров таблицы покрытий, поэтому изложенные в данном разделе способы вычерчивания некоторых строк и столбцов таблицы покрытий имеют большое значение для сокращения перебора.
Теорема 1.3 /о ядре/. Если в столбце таблицы покрытий содержится единственная единица, то строка, имеющая эту единицу, входит во все покрытия. Эта строка называется ядерной.
Множество ядерных строк заранее выделяется и запоминается для введения во все покрытия. Ядерные строки из таблицы удаляются и вычеркиваются все покрытые ими столбцы, т.е. вычеркиваются все столбцы, в которых есть единицы в ядерных строках.
Теорема 1.4 /об антиядре/. Если после удаления ядерных строк и покрытых ими столбцов в таблице покрытий в какой-либо строке не остается единиц, то эта строка не входит ни в одно безызбыточное покрытие. Такие строки называются антиядерными и они вычеркивается из таблицы без запоминания.
Прежде, чем сформулировать следующие теоремы, напомним понятие поглощающего вектора: вектор Е поглощает вектор F /E≥F/, если для всех компонент ei, fi этих векторов можно одновременно записать:
/1.3/
Примеры. E = 1101, F = 0101, S = 1011, T = 1111
E≥F, E≤T, вектора E и S, F и S – несравнимы.
E - поглощающий вектор для F .
E - поглощаемый вектор для Т.
Теорема 1.5 /о поглощающих столбцах/. В таблице покрытий могут быть вычеркнуты все поглощающие столбцы /рассматриваемые как векторы/ без ущерба для построения всех беэыэбыточных покрытий.
Теорема 1.6 /о поглощаемых строках при поиске одного кратчайшего покрытия/. Если при решении задачи покрытия достаточно гарантировать получение хотя бы одного кратчайшего покрытия, то можно удалять все поглощаемые строки.
Теорема 1.7 /о поглощаемых строках при построении минимальных покрытий/. Если при решении задачи покрытия достаточно гарантировать построение всех /хотя бы одного/ минимальных покрытий, то можно вычеркивать поглощаемую строку, если цена ее больше /или равна/ цены поглощающей строки.
Примеры использования теорем. Таблица покрытий для примера 1.1 /см. рис.1.1/ не упрощается: в ней нет ни ядерных, ни антиядерных строк, ни поглощаемых столбцов, ни поглощаемых строк. Таблица покрытий для примера 1.2 /см. рис. 1.3/ тоже упрощается очень мало: в ней только столбец b1 можно вычеркнуть как поглощающий, т.е. (b1≥ b4 , b1≥ b5 ).
Рассмотрим более информативный пример 1.3 /рис.1.4/.
В столбцах b3 и b4 по одной 1 в каждом, поэтому строки А3 и А5 , содержащие эти 1, являются ядерными. Эти строки запоминаем для введения во все безыэбыточные покрытия этой таблицы и после удаления этих строк и всех покрытых ими столбцов, таблица покрытий сократится до таблицы /рис. 1.5/. Можно таблицу не перечерчивать, а вычеркнуть соответствующие строки и столбцы непосредственно на рис. 1.4.
На рис. 1.5 строка А6 не содержит 1, эта строка является антиядерной и ее вычеркиваем из таблицы.
Столбец b7 ≥b2, поэтому поглощающий столбец b7 вычеркиваем. Прежде чем перейти к дальнейшим упрощениям еще раз перечертим оставшуюся таблицу.
На рис. 1.6 строка А2 поглощается строкой А1 (А2≤А1) . Возможно несколько разветвлений процесса решения.
1. Если строятся все беэызбыточные покрытия, то никакие сокращения строк делать нельзя и таблица /рис. 1.6/ далее не упрощается.
2. Если ищутся минимальные покрытия, то согласно теореме 1.7 нужно обратить внимание на цены ai строк: А2≤А1 и a2<a1, поэтому року Аг нельзя вычеркивать и таблица также не упрощается.
3. Если ищем одно кратчайшее покрытие, то строку A2 как поглощаемую» можно вычеркнуть. Тогда строка A1 становится ядерной, так как в столбце b2 останется единственная единица. Строка А1 добавляется множеству ядерных строк –{A1, А3, А5} , таблица покрытий упрощается: вычеркивается строка А1 и покрытые ею столбцы b2 и b6 Оставшаяся таблица /рис. 1.7/ не упрощается.
Алгоритм сокращения таблицы покрытий. Используя теоремы 1.3 - 1.7, можно упростить таблицу покрытий, запомнив ядерные строки. Возможны два исхода процесса решения.
1. Таблица покрытий после упрощений становится пустой – вычеркнуты все столбцы. В этом случае множество ядерных строк - требуемое покрытие.
2. Остаток таблицы покрытий более не упрощается приемами, предлагаемыми теоремами 1.3-1.7. Получаем циклический остаток таблицы покрытий. Покрытая для циклического остатка таблицы можно строить только методами перебора покрытий: граничным перебором или разложением по столбцу /см. подразд. 1.9/, Когда к ядерным строкам добавляются строки покрытия циклического остатка, получается покрытие исходной таблицы покрытий. Сформулируем алгоритм построения циклического остатка таблицы покрытий и множества ядерных строк для случая построения одного кратчайшего покрытия.
-
Считаем исходную таблицу покрытий текущей таблицей покрытий, а множество ядерных строк - пустым.
-
Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем: вычеркиваем ядерные строки и все столбцы, покрытые ими.
-
Вычеркиваем антиядерные строки.
-
Вычеркиваем поглощающие столбцы.
-
Вычеркиваем поглощаемые строки.
5. Если в результате выполнения шт. 1-4 текущая таблица покрытий изменилась, снова выполняем п.1, иначе преобразования заканчиваем.
Подчеркиваем еще раз, что получаются два результата - множество ядерных строк и циклический остаток таблицы покрытий. Таблица покрытий примера 1.1 - циклическая, множество ядерных строк – пусто. Для примера 1.3 множество ядерных строк содержит три элемента - –{A1, А3, А5}; циклический остаток при построении одного кратчайшего покрытия показан на рис. 1.7.
При сокращении таблицы покрытий до циклической при построении одного минимального покрытая изменяется только п.4 алгоритма, который формулируется следующим образом:
вычеркиваются поглощаемые строки, веса которых не меньше весов соответствующих поглощаемых строк.
Для примера 1,3 в этом случае множество ядерных строк {А3, А5} циклический остаток таблицы покрытий показан на рис. 1.6.
При сокращении таблицы покрытий до циклической при условии построения всех безызбыточных покрытий п.4 алгоритма не выполняется: в этом случае нельзя вычеркивать никакие поглощаемые строки. Ответ для примера 1.3 тот же, что и при построении одного минимального покрытия.