В чем польза жадных алгоритмов? Реальный пример?
Примеры использования жадных алгоритмов?
comment
en.wikipedia.org/wiki/Algorithm#By_design_paradigm
- person Axn schedule 01.02.2011
Ответы (10)
Минимальное связующее дерево — алгоритм Prim и алгоритм Крускала
Расчет кратчайшего пути — алгоритм Дейкстры
Подробнее: (Дробная задача о рюкзаке, Кодирование Хаффмана, Оптимальное слияние, Топологическая сортировка).
person
Sanjit Saluja
schedule
01.02.2011
Некоторые проблемы таковы, что жадное решение на самом деле будет оптимальным, и иногда они так устроены. Забавным примером является то, что стоимость монет во многих странах такова, что жадный подход к возврату сдачи (т. е. всегда возвращать максимально возможную монету, пока вы не закончите) работает.
person
Ulrich Schwarz
schedule
01.02.2011
В Хогвартсе -- извините, кто-то должен был сделать замечание
- person Foo Bah; 02.02.2011
@drvitex: Фу, старая британская система может сработать. 4,3,1 будет примером монетной системы, которая не подходит для 6.
- person Ulrich Schwarz; 02.02.2011
Удивительно, но найти оптимальное количество монет вообще сложно (это NP-сложно), но существует полиномиальный алгоритм для проверки работоспособности жадного подхода. Пирсон, Алгоритм с полиномиальным временем для задачи внесения изменений, соч. Рез. Позволять. 33:3 (2005), стр. 231-234. DOI 10.1016/j.orl.2004.06.001
- person vonbrand; 26.04.2019
Все, где оптимальное решение было бы невозможным или очень сложным.
Жадные алгоритмы выбирают лучшее решение на данный момент, даже если это не лучшее решение, если вы рассмотрели все альтернативы.
person
Martin Beckett
schedule
01.02.2011
Оптимальные решения для коммивояжера не являются невозможными. На самом деле есть несколько эффективных алгоритмов, дающих точные решения для большого количества городов. И ничто не мешает жадному алгоритму дать оптимальное решение проблемы. Я думаю, что ваш ответ немного вводит в заблуждение. Жадные алгоритмы даже не используются для решения задачи коммивояжера. Для неоптимальных решений вы должны использовать алгоритм аппроксимации. -1, пока вы не улучшите это.
- person IVlad; 02.02.2011
Вы могли бы использовать жадный алгоритм для TSP, если бы вы просто переходили к следующему ближайшему непосещенному городу на каждом шаге.
- person Martin Beckett; 02.02.2011
но зачем тебе это? В конце концов это может легко дать наихудшее решение. TSP — прекрасный пример того, где нельзя использовать жадный алгоритм. Я по-прежнему не согласен с вашей первой строкой - если оптимальное решение очень сложное, я думаю, лучше сказать, что вы будете использовать приближенный алгоритм, а не жадный алгоритм. Вы бы использовали жадные алгоритмы для задач, где вы можете доказать, что они всегда дают оптимальное решение. Но в любом случае меня беспокоил именно пример TSP, поэтому я удалил -1.
- person IVlad; 02.02.2011
Ну, это алгоритм, который я использую для TSP, когда делаю покупки в супермаркете!
- person Martin Beckett; 02.02.2011
@IVlad, можете ли вы объяснить, как алгоритм может дать быстрое и точное решение для коммивояжера? Я думал, что задача коммивояжера NP-полная.
- person Vlad the Impala; 23.12.2014
Я удивлен, что никто не указал кодировку Хаффмана/Шеннона...
person
Foo Bah
schedule
02.02.2011
Кроме того, я считаю, что шифрование LZW также жадно
- person Foo Bah; 02.02.2011
В чем польза жадных алгоритмов?
Жадные алгоритмы выбирают лучшее/оптимальное решение на каждом этапе. Посмотрите статью в Википедии.
Реальный пример?
Алгоритмы минимального связующего дерева являются жадными алгоритмами.
Знаменитый алгоритм Дейкстры также является жадным алгоритмом.
person
Community
schedule
01.02.2011
Реальным примером жадного алгоритма будет интервальное планирование.
Например, если вы хотите максимизировать количество клиентов, которые могут использовать конференц-зал, вы можете использовать алгоритм интервального планирования.
person
skndmx
schedule
24.02.2013
В чем польза жадных алгоритмов?
Мы используем жадный алгоритм для получения оптимального решения. Но не все задачи можно решить с помощью жадного алгоритма.
Свойство оптимальной подструктуры и свойство жадного выбора являются ключевыми компонентами. Если мы сможем продемонстрировать, что задача обладает этими свойствами, значит, мы на правильном пути к разработке для нее жадного алгоритма.
Реальные примеры?
- Проблема планирования активности
- Код Хаффмана
- Номинал монеты
- Задача о кратчайшем пути из одного источника (Дейкстра)
- Минимальное остовное дерево (алгоритм Прима, алгоритм Крускала)
- Дробная задача о рюкзаке.
Почти все проблемы, которые можно решить с помощью динамического подхода, можно решить с помощью жадного подхода.
person
Kavishka Gamage
schedule
12.07.2019
Здесь я перечислил некоторые жадные алгоритмы и их потенциальные варианты использования в реальном мире.
Алгоритм Дейкстры
- IP-маршрутизация для поиска кратчайшего пути.
- Протоколы сетевой маршрутизации
Узнайте больше о реальных приложениях алгоритма Дейкстры здесь
Алгоритм минимального связующего дерева Prim
Отслеживание и проверка лица в режиме реального времени (т. е. обнаружение человеческих лиц в видеопотоке).
Протоколы в информатике, чтобы избежать сетевых циклов.
Максимальное количество узких мест.
Дизеринг (добавление белого шума к цифровой записи для уменьшения искажений).
Задача коммивояжера
Планирование работы цеха без промежуточного хранения
Кластеризация массива данных
Маршрутизация транспортных средств
График — Цвет карты
Составление расписания/расписания
судоку
Присвоение частот мобильной радиосвязи
Подробнее об этом можно прочитать в этой статье.
Алгоритм минимального связующего дерева Крускала
Формирование телесети
Экскурсионные операции
Проблема с рюкзаком
Использование в реальном мире решения о том, что брать с собой в ограниченном пакете поездок
person
Sarangan
schedule
05.03.2020
