Кто-нибудь знает определение или объяснение сути жадного алгоритма. Самое общее, без привязки к конкретной задаче.

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

Вроде не верно. Если бы он не перебирал все пути, он не был бы жадным...
А ты прочитай в Кормене про жадные алгоритмыю целая глава есть. 

То что он не перебирает все пути - это 100%. Именно из-за этого он может получать не оптимальное решение. Зато работает быстрее (при правильной реализации). Пример:
Пусть дана матрица A с действительными элементами, где
      10  8  4
A =  6   7  6
       5   6  4
и сформулируем следующую оптимизационную задачу. Найти такое подмножество элементов S матрицы A, для которого выполнены условия: 
а) каждый столбец и каждая строка матрицы содержит не более одного элемента множества S,
б) сумма выбранных элементов максимальна. 
Будем решать поставленную задачу при помощи жадного алгоритма, который на каждом шаге выбирает наибольший элемент из возможных. Получим решение S = {a11, a22, a33} = {10, 7, 4}, причём 10+7+4 = 21. Но это не максимальное решение, т.к. решение S’ = {a11, a23, a32} = {10, 6, 6} даёт 10+6+6 = 22.


А что за Кормен? Какое полное название?