В чем разница между алчным и эвристическим алгоритмом?

Question

В чем разница между алхимическим и эвристическим алгоритмом?

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

Answer 1

То, как эвристика была описана мной, заключается в том, что они являются «эмпирическими правилами». Их способность создавать глобально оптимальное решение не может быть напрямую доказана, но, как правило, они выполняют хорошую работу. Они часто используются, когда стоимость определения оптимального решения слишком высока. Кроме того, эвристика часто кодирует определенный опыт в отношении того, как проблема была решена в прошлом. Лучший способ описать эвристику - это «Стратегия решения».

Алгоритм Жадный - это тот, который делает выбор на основе того, что выглядит лучше всего на данный момент. Другими словами, выбор является локально оптимальным, но не обязательно глобально оптимальным (может быть, если повезет, но вы не можете это доказать). Кроме того, алгоритм Greedy обычно не уточняет свое решение на основе новой информации. Это всего лишь одна стратегия решения (a.k.a эвристика).

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

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

Завершая ...

• ли все эвристики, жадные алгоритмы - Нет

• не являются все жадные алгоритмы, Эвристика - В общем, да.

Чтобы обеспечить некоторый фон, один из первых проблем, я преподавал в классе алгоритмов в университете был Traveling Salesman Problem. Он относится к NP-полному классу проблем, означающему отсутствие эффективных средств решения. То есть, по мере роста размера проблемы, время, затрачиваемое на поиск решения, существенно возрастает. Существует ряд доказанных алгоритмов, но их производительность невелика и в реальных приложениях мы склонны к эвристике (в том числе Greedy Algorithms - см. Ссылку).

Answer 2

Это две разные вещи: жадные алгоритмы пытаются взять «лучший выбор» на каждой итерации (например, если вы выберете края по графику по их длине, он будет выбирать самый длинный/самый короткий край в каждом итерация). Жадные алгоритмы обеспечивают точное решение!

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

Answer 3

их основной характеристикой является выбор (локальный) параметр лучший на каждой итерации

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

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

Жадный - пример эвристики (сделать лучший выбор и надеяться на оптимальный глобальный результат), но это не значит, что эвристика жадна. Есть много эвристик, совершенно не связанных с жадными, например. genetic algorithms are considered heuristic:

В области информатики искусственного интеллекта генетический алгоритм (GA) является эвристикой поиска, которая имитирует процесс естественного отбора.

Answer 4

Примечание: Я не уверен, что следует относится ко мне и моему «социальному кругу» или стандартный - глобальная концепция.

На мой взгляд, эвристический алгоритм, так как Википедия выразился:

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

С другой стороны, алчный алгоритм - это то, что вы описали: алгоритм, который пытается найти лучшее решение, выбрав лучший вариант на каждом шагу. Это в значительной степени. Это не означает ничего о решении: иногда жадный алгоритм обеспечивает идеальное и оптимальное решение, в то время как в некоторых других случаях это может быть просто эвристическое -> приблизительное (не идеальное), но более быстрое решение.

Answer 5

Жадный, когда вы объединяете элементы один за другим в решение (следуя некоторой стратегии выбора) и никогда не возвращаетесь назад. Пример: прямой выбор сортировки можно считать жадной процедурой.

Эвристика - это общий термин, который обозначает любое ad-hoc/интуитивное правило, используемое с надеждой на улучшение поведения алгоритма. Пример: правило медианного троих используется, чтобы выбрать точку опоры в Quicksort.