Жадный алгоритм

Жадный алгоритм (Greedy algorithm) — алгоритм комбинаторной оптимизации отыскания подмножества максимального веса заданного множества, элементам которого приписаны неотрицательные веса. Жадный алгоритм даёт правильное решение, если исходное множество есть матроид. К жадным алгоритмам принадлежат многие алгоритмы на графах, например алгоритм Краскала и Прима отыскания каркаса наименьшего веса.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

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

• Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.