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

Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов. Определение наилучшего выбора, руководствуясь принципами динамического программирования, во многих задачах оптимизации напоминает стрельбу из пушки по воробьям; другими словами, для этих задач лучше подходят более простые и эффективные алгоритмы. В жадном алгоритме (greedy algorithm) всегда делается выбор, который кажется самым лучшим

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

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

программированием, изложенным в главе 15, в частности, с разделом 15.3.

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

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

сначала будет рассмотрено решение, основанное на парадигме динамического

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

получить, исходя из принципов жадных алгоритмов. В разделе 16.2 представлен

обзор основных элементов подхода, в соответствии с которым разрабатываются

жадные алгоритмы. Это позволит упростить обоснование корректности жадных

алгоритмов, не используя при этом сравнение с динамическим программированием, как это делается в разделе 16.1. В разделе 16.3 приводится важное приложение

методов жадного программирования: разработка кодов Хаффмана (Huffman) дляГлава 16.

сжатия данных. В разделе 16.4 исследуются теоретические положения, на которых основаны комбинаторные структуры, известные под названием “матроиды”,

для которых жадный алгоритм всегда дает оптимальное решение. Наконец, в разделе 16.5 матроиды применяются для решения задачи о составлении расписания

заданий равной длительности с предельным сроком и штрафами.

Жадный метод обладает достаточной мощью и хорошо подходит для довольно

широкого класса задач. В последующих главах представлены многие алгоритмы,

которые можно рассматривать как применение жадного метода, включая алгоритмы поиска минимальных остовных деревьев (minimum-spanning-tree) (глава 23),

алгоритм Дейкстры (Dijkstra) для определения кратчайших путей из одного источника (глава 24) и эвристический жадный подход Чватала (Chvatal) к задаче

о покрытии множества (set-covering) (глава 35). Алгоритмы поиска минимальных

остовных деревьев являются классическим примером применения жадного метода. Несмотря на то, что эту главу и главу 23 можно читать независимо друг от

друга, может оказаться полезно читать их одна за другой.

(http://www.williamspublishing.com/PDF/5-8459-0857-4/part.pdf)- сайт с главами лекции