Абстрактное отношение зависимости (стр. 8 из 9)
Пример 2.
Свободные матроиды. Если
- произвольное конечное множество, то 
- матроид. Такой матроид называется свободным. В свободном матроиде каждое множество независимо, А является базисом и 
.Пример 3.
Матроид трансверсалей. Пусть
- некоторое конечное множество, и 
- некоторое семейство подмножеств этого множества. Подмножество 
называется частичной трансверсалью семейства 
, если 
содержит не более чем по одному элементу каждого подмножества из семейства 
. Частичные трансверсали над образуют матроид на А.Перейдем к рассмотрению жадного алгоритма. Для начала нужно сформулировать задачу, которую будем решать с его использованием.
Пусть имеются конечное множество
, 
, весовая функция 
и семейство 
.Рассмотрим следующую задачу: найти
, где 
. Другими словами, необходимо выбрать в указанном семействе подмножество наибольшего веса.Не ограничивая общности, можно считать, что
Рассмотрим такой алгоритм, который исходными данными имеет множество
, семейство его подмножеств 
и весовую функцию 
, причем множество упорядочено в порядке убывания весов элементов. После выполнения этого алгоритма мы получим подмножество 
.Изначально искомое множество
пусто, далее просматриваем по очереди все элементы из множества 
и проверяем зависимость множества 
, если 
- независимо, то элемент 
добавляем в множество 
, если же - зависимо, то переходим к элементу 
, пока все элементы из множества 
не будут проверены.Алгоритм такого типа называется «жадным». Совершенно очевидно, что по построению окончательное множество
, то есть независимо. Также очевидно, что жадный алгоритм является чрезвычайно эффективным: количество шагов составляет 
, то есть жадный алгоритм является линейным. (Не считая затрат на сортировку множества и проверку независимости 
.)Пример 4.
Пусть дана матрица
. Рассмотрим следующие задачи.Задача 1. Выбрать по одному элементу из каждого столбца, так чтобы их сумма была максимальна.
Здесь весовая функция
ставит в соответствие элементу матрицы 
его значение. Например, 
.Множество
упорядоченно следующим образом: 
.Семейство независимых подмножеств
будут образовывать такие множества, в которых все элементы из разных столбцов и пустое множество.Наш алгоритм будет работать следующим образом:
0 шаг (нач. усл.):
;1 шаг: поверяем для элемента
, 
;2 шаг: для
, 
;3 шаг: для
, 
;4 шаг: для
, 
;5 шаг: для
, 
;6 шаг: для
, 
;7 шаг: для
, 
;8 шаг: для
, 
;9 шаг: для
, 
;В результате получили множество
, 
., полученный результат действительно является решением задачи.Задача 2. Выбрать по одному элементу из каждой строки, так чтобы их сумма была максимальна.
Здесь функция
и множество такие же как и в предыдущей задаче, а семейство независимых подмножеств 
будут образовывать такие множества, в которых все элементы из разных строк и пустое множество.Используя наш алгоритм получим следующее решение: множество
и 
, которое так же является верным.Задача 3. Выбрать по одному элементу из каждого столбца и из каждой строки, так чтобы их сумма была максимальной.
В этой задаче функция
и множество остаются прежними, а семейство независимых подмножеств 
будут образовывать такие множества, в которых все элементы из разных столбцов и различных строк и пустое множество.Нетрудно видеть, что жадный алгоритм выберет следующие элементы:
и 
, которые не являются решением задачи, поскольку существует лучшее решение - 
и 
.