Изменения

Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[Определение матроида| база]] в графовом [[Определение матроида| матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма один в один копирует код алгоритма поиска базы минимального веса, который был приведен выше.

Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| Алгоритма алгоритма Куна]].

Классической задачей, которую мы рассмотрим, будет Рассмотрим задачу о нахождение максимального количества линейно независимых строк в матрице. Рассмотрим Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — матроид. Задача Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss e-maxxMAXimal :: algo :ru:Метод Гаусса]</ref>

* [http://habrahabr.ru/post/120343/| Habrahabr:— Жадные алгоритмы]