Абстрактное отношение зависимости — страница 11

  • Просмотров 5866
  • Скачиваний 76
  • Размер файла 765
    Кб

независимо. Также очевидно, что жадный алгоритм является чрезвычайно эффективным: количество шагов составляет , то есть жадный алгоритм является линейным. (Не считая затрат на сортировку множества и проверку независимости .) Пример 4. Пусть дана матрица . Рассмотрим следующие задачи. Задача 1. Выбрать по одному элементу из каждого столбца, так чтобы их сумма была максимальна. Здесь весовая функция ставит в соответствие элементу

матрицы его значение. Например, . Множество упорядоченно следующим образом: . Семейство независимых подмножеств будут образовывать такие множества, в которых все элементы из разных столбцов и пустое множество. Наш алгоритм будет работать следующим образом: 0 шаг (нач. усл.): ; 1 шаг: поверяем для элемента , ; 2 шаг: для ,; 3 шаг: для ,; 4 шаг: для ,; 5 шаг: для ,; 6 шаг: для ,; 7 шаг: для ,; 8 шаг: для ,; 9 шаг: для ,; В результате получили множество , .,

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

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

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

- матроид, а в задаче 3 таковым не является, так как не выполняется аксиома М3. Если рассмотреть , тогда получили противоречие с независимостью хотя бы одного из множеств. Список библиографии Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с. Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с. Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с. Фрид Э.