Примеры использования жадных алгоритмов?

Question

Какая польза от жадных алгоритмов? Реальный пример?

Answer 1

Минимальное остовное дерево - Прим алгоритм и Крускала алгоритм

Расчет кратчайшего пути - Алгоритм Дейкстры

Подробнее: (дробная задача о ранце, кодирование Хаффмана, оптимальное слияние, топологическая сортировка).

Answer 2

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

Answer 3

Все, где было бы невозможно оптимальное решение - или очень, очень сложное.

Жадные алгоритмы принимают лучшее решение на текущий момент, даже если это не лучшее решение, если вы изучили все альтернативы

Answer 4

Я удивлен, что никто не указал кодировку Хаффмана / Шеннона ...

Answer 5

Какая польза от жадных алгоритмов?

Жадные алгоритмы - это выбор наилучшего / оптимального решения на каждом этапе. Посмотрите на статью в Википедии

Реальный пример?

Минимальные алгоритмы связующего дерева являются жадными алгоритмами

• Алгоритм Прима
• Алгоритм Крускала
• Алгоритм обратного удаления

Знаменитый Алгоритм Дейкстры также является жадным алгоритмом

Answer 6

Реальным примером жадного алгоритма будет Интервальное планирование .

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

Answer 7

Какая польза от жадных алгоритмов?

Мы используем алгоритм жадности для получения оптимального решения. Но все проблемы не могут быть решены с помощью жадного алгоритма.

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

Реальные примеры?

• Проблема планирования активности
• Код Хаффмана
• Номинал монеты
• Задача кратчайшего пути из одного источника (Дейкстра)
• Минимальное остовное дерево (алгоритм Прима, алгоритм Крускала)
• Задача дробного ранца.

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

Answer 8

Применение жадного метода

Алгоритм Прима , Алгоритм Крускала

Answer 9

http://en.wikipedia.org/wiki/Greedy_algorithm