85488 (Абстрактное отношение зависимости), страница 4

Пример 3.

Матроид трансверсалей. Пусть - некоторое конечное множество, и - некоторое семейство подмножеств этого множества. Подмножество называется частичной трансверсалью семейства , если содержит не более чем по одному элементу каждого подмножества из семейства . Частичные трансверсали над образуют матроид на А.

Перейдем к рассмотрению жадного алгоритма. Для начала нужно сформулировать задачу, которую будем решать с его использованием.

Пусть имеются конечное множество , , весовая функция и семейство .

Рассмотрим следующую задачу: найти , где . Другими словами, необходимо выбрать в указанном семействе подмножество наибольшего веса.

Не ограничивая общности, можно считать, что

Рассмотрим такой алгоритм, который исходными данными имеет множество , семейство его подмножеств и весовую функцию , причем множество упорядочено в порядке убывания весов элементов. После выполнения этого алгоритма мы получим подмножество .

Изначально искомое множество пусто, далее просматриваем по очереди все элементы из множества и проверяем зависимость множества , если - независимо, то элемент добавляем в множество , если же - зависимо, то переходим к элементу , пока все элементы из множества не будут проверены.

Алгоритм такого типа называется «жадным». Совершенно очевидно, что по построению окончательное множество , то есть независимо. Также очевидно, что жадный алгоритм является чрезвычайно эффективным: количество шагов составляет , то есть жадный алгоритм является линейным. (Не считая затрат на сортировку множества и проверку независимости .)

Пример 4.

Пусть дана матрица . Рассмотрим следующие задачи.

Задача 1. Выбрать по одному элементу из каждого столбца, так чтобы их сумма была максимальна.

Здесь весовая функция ставит в соответствие элементу матрицы его значение. Например, .

Множество упорядоченно следующим образом:

.

Семейство независимых подмножеств будут образовывать такие множества, в которых все элементы из разных столбцов и пустое множество.

Наш алгоритм будет работать следующим образом:

0 шаг (нач. усл.): ;

1 шаг: поверяем для элемента , ;

2 шаг: для , ;

3 шаг: для , ;

4 шаг: для , ;

5 шаг: для , ;

6 шаг: для , ;

7 шаг: для , ;

8 шаг: для , ;

9 шаг: для , ;

В результате получили множество , ., полученный результат действительно является решением задачи.

Задача 2. Выбрать по одному элементу из каждой строки, так чтобы их сумма была максимальна.

Здесь функция и множество такие же как и в предыдущей задаче, а семейство независимых подмножеств будут образовывать такие множества, в которых все элементы из разных строк и пустое множество.

Используя наш алгоритм получим следующее решение: множество и , которое так же является верным.

Задача 3. Выбрать по одному элементу из каждого столбца и из каждой строки, так чтобы их сумма была максимальной.

В этой задаче функция и множество остаются прежними, а семейство независимых подмножеств будут образовывать такие множества, в которых все элементы из разных столбцов и различных строк и пустое множество.

Нетрудно видеть, что жадный алгоритм выберет следующие элементы:

и , которые не являются решением задачи, поскольку существует лучшее решение - и .

Возникает вопрос, в каких же случаях жадный алгоритм действительно решает поставленную задачу? На поставленный вопрос поможет ответить теорема, сформулированная и доказанная в [4, с.75-76].

Теорема 7.

Для любой функции жадный алгоритм находит независимое множество с наибольшим весом, тогда и только тогда, когда является матроидом.

Действительно, в нашем примере в задачах 1 и 2 - матроид, а в задаче 3 таковым не является, так как не выполняется аксиома М₃. Если рассмотреть , тогда получили противоречие с независимостью хотя бы одного из множеств.

Список библиографии

1. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с.

2. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с.

3. Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с.

4. Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с.

5. Фрид Э. Элементарное введение в абстрактную алгебру. – М.: Мир, 1974. – 260 с.