Лекция 3. Greedy алгориттмы

Begin

Ifthen

; // Добавление ребра.

; // Укрупнение разбиения.

end;

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

2) Матричные матроиды [1,2,3,4,5,6,7,8,9]

3) Линейная независимость над полем GF(2) и матроиды [1,2,3,4,5,6,7,8,9]

Литература:

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. – 416 с.

2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.

3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.

4. Донской В. И. Дискретная математика. –Симферополь: Сонат, 2000. –356 с.

5. Липский В. Комбинаторика для программистов. М.: Мир, 1988. – 215 с.

6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995. – 256 с

7. Линдон Р. Заметки по логике. М.: Мир, 1968. – 128 с.

8. Оре О. Теория графов. М.: Наука, 1980. – 336 с.

9. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. – 400 с.

1) Примеры успешной работы GREEDY алгоритмов

Литература:

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. – 416 с.

11. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. – 536 с.

12. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.

13. Донской В. И. Дискретная математика. –Симферополь: Сонат, 2000. –356 с.

14. Липский В. Комбинаторика для программистов. М.: Мир, 1988. – 215 с.

15. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физико-математическая литература, 1995. – 256 с

16. Линдон Р. Заметки по логике. М.: Мир, 1968. – 128 с.

17. Оре О. Теория графов. М.: Наука, 1980. – 336 с.

18. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. – 400 с.

Преподаватель Донской В.И. подпись