Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Минимальное связующее дерево - Prim алгоритм и Kruskal's алгоритм

Расчет кратчайшего пути - Dijkstra algorithm

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

Я удивлен, что никто не указал на кодировку huffman/shannon...

Ответ 5

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

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

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

Минимальные алгоритмы остовного дерева - это жадные алгоритмы

Известный Dijkstra Algorithm также является жадным алгоритмом

Ответ 6

Реальный пример алгоритма жадного алгоритма будет Interval Scheduling.

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

Ответ 9

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

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

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

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

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

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