В чем разница между эвристикой и алгоритмом?
algorithm
definition
heuristics
nomenclature
уличный парад
источник
источник
Ответы:
Алгоритм - это описание автоматизированного решения проблемы . То, что делает алгоритм, точно определено. Решение могло быть или не могло быть наилучшим из возможных, но вы с самого начала знаете, какой результат вы получите. Вы реализуете алгоритм, используя некоторый язык программирования, чтобы получить (часть) программы .
Теперь некоторые проблемы являются сложными, и вы не сможете получить приемлемое решение в приемлемые сроки. В таких случаях вы часто можете получить неплохое решение намного быстрее, применяя произвольный выбор (обоснованные предположения): это эвристика .
Эвристика по-прежнему представляет собой своего рода алгоритм, но он не будет исследовать все возможные состояния проблемы или начнет с изучения наиболее вероятных из них.
Типичные примеры взяты из игр. При написании программы для игры в шахматы вы можете представить себе, как пробуете каждый возможный ход на некотором уровне глубины и применяете к доске некую оценочную функцию. Эвристика исключает полные ветви, начинающиеся с заведомо плохих ходов.
В некоторых случаях вы ищете не лучшее решение, а любое решение, удовлетворяющее некоторым ограничениям. Хорошая эвристика поможет найти решение за короткое время, но также может не найти его, если единственные решения находятся в состояниях, которые он решил не пробовать.
источник
Многие задачи, для которых не известен ни один эффективный алгоритм поиска оптимального решения, имеют эвристические подходы, которые очень быстро дают результаты, близкие к оптимальным.
Есть некоторые совпадения: «генетические алгоритмы» - общепринятый термин, но, строго говоря, это эвристики, а не алгоритмы.
источник
Короче говоря, эвристика - это «обоснованное предположение». Википедия прекрасно это объясняет. В конце концов, за оптимальное решение указанной проблемы принимается метод «всеобщего признания».
А алгоритм - это метод, содержащий конечный набор инструкций, используемых для решения проблемы. Математически или научно доказано, что этот метод работает для решения этой проблемы. Есть формальные методы и доказательства.
источник
Алгоритм является самодостаточным шаг за шагом набором операций, подлежащий выполнению 4 , как правило , интерпретируются как конечная последовательность (компьютер или человек) инструкция для определения решения проблемы , такие как: существует путь от А до B, или наименьший путь между A и B. В последнем случае вы также можете удовлетвориться «достаточно близким» альтернативным решением.
Существуют определенные категории алгоритмов, одной из которых является эвристический алгоритм. В зависимости от (доказанных) свойств алгоритма в этом случае он попадает в одну из этих трех категорий (примечание 1):
Обратите внимание, что алгоритм приближения также является эвристическим, но с более сильным свойством, заключающимся в том, что существует доказанная связь с решением (значением), которое он выводит.
Для некоторых проблем никто никогда не нашел «эффективного» алгоритма для вычисления оптимальных решений (примечание 2). Одна из таких проблем - хорошо известная проблема коммивояжера. Например, алгоритм Кристофидеса для задачи коммивояжера раньше назывался эвристическим , поскольку не было доказано, что он находится в пределах 50% от оптимального решения. Однако, поскольку это было доказано, алгоритм Кристофидеса более точно называется приближенным алгоритмом.
Из - за ограничения на то , что компьютеры могут сделать, это не всегда можно эффективно найти лучшее решение возможно. Если в задаче достаточно структуры, может быть эффективный способ пересечь пространство решений, даже если пространство решений огромно (то есть в задаче кратчайшего пути).
Эвристика обычно применяется для сокращения времени работы алгоритмов путем добавления «экспертной информации» или «обоснованных предположений», которые определяют направление поиска. На практике эвристика также может быть подпрограммой для оптимального алгоритма, чтобы определить, где искать в первую очередь .
(примечание 1) : Кроме того, алгоритмы характеризуются тем, включают ли они случайные или недетерминированные элементы. Алгоритм, который всегда выполняется одинаково и дает одинаковый ответ, называется детерминированным.
(примечание 2) : это называется проблемой P vs NP, и проблемы, которые классифицируются как NP-полные и NP-сложные, вряд ли будут иметь «эффективный» алгоритм. Заметка; как @Kriss упомянул в комментариях, есть еще «худшие» типы проблем, для вычисления которых может потребоваться экспоненциальное время или пространство.
Есть несколько ответов, которые частично отвечают на вопрос. Я посчитал их менее полными и недостаточно точными и решил не редактировать принятый ответ @Kriss
источник
На самом деле я не думаю, что между ними много общего. Некоторые алгоритмы используют эвристику в своей логике (часто для того, чтобы производить меньше вычислений или получать более быстрые результаты). Обычно эвристика используется в так называемых жадных алгоритмах.
Эвристика - это некое «знание», которое, как мы полагаем, полезно использовать, чтобы получить лучший выбор в нашем алгоритме (когда выбор должен быть сделан). Например ... в шахматах может быть эвристика (всегда берите ферзя оппонента, если можете, так как вы знаете, что это более сильная фигура). Эвристика не гарантирует, что вы получите правильный ответ, но (если предположения верны) часто получаете ответ, близкий к наилучшему, за гораздо более короткое время.
источник
Эвристики - это алгоритмы, поэтому в этом смысле их нет, однако эвристики используют «догадочный» подход к решению проблем, давая «достаточно хороший» ответ, а не находя «наилучшее возможное» решение.
Хорошим примером является ситуация, когда у вас есть очень сложная (читай NP-полная) проблема, которую вы хотите решить, но у вас нет времени, чтобы ее решить, поэтому вам нужно использовать достаточно хорошее решение, основанное на эвристическом алгоритме, таком как поиск решения задачи коммивояжера с помощью генетического алгоритма.
источник
Алгоритм - это последовательность некоторых операций, которые при заданных входных данных что-то вычисляют (функцию) и выдают результат.
Алгоритм может выдавать точные или приблизительные значения.
Он также может вычислить случайное значение, которое с высокой вероятностью близко к точному значению.
Эвристический алгоритм использует некоторую информацию о входных значениях и вычисляет не точное значение (но может быть близким к оптимальному). В некоторых особых случаях эвристика может найти точное решение.
источник
Алгоритм - это четко определенный набор инструкций для решения проблемы. Эвристика предполагает использование подхода обучения и открытия для достижения решения.
Итак, если вы знаете, как решить проблему, используйте алгоритм. Если вам нужно разработать решение, то это эвристика.
источник
Эвристика - это обычно оптимизация или стратегия, которая обычно дает достаточно хороший ответ, но не всегда и редко лучший ответ. Например, если вам нужно было решить задачу коммивояжера с помощью грубой силы, отказ от частичного решения, если его стоимость превышает стоимость текущего лучшего решения, является эвристикой: иногда это помогает, иногда нет, и это определенно не помогает. t улучшить теоретическое время работы алгоритма
источник
Я думаю, что эвристика - это скорее ограничение, используемое в модели, основанной на обучении в искусственном интеллекте, поскольку будущие состояния решения трудно предсказать.
Но затем я сомневаюсь после прочтения ответов выше: «Как можно успешно применить эвристику с использованием методов стохастической оптимизации? Или они могут работать как полноценные алгоритмы при использовании со стохастической оптимизацией?»
http://en.wikipedia.org/wiki/Stochastic_optimization
источник
Одно из лучших объяснений, которые я прочитал, содержится в замечательной книге Code Complete , которую я сейчас цитирую:
источник
Они находят решение субоптимально без каких-либо гарантий относительно качества найденного решения, очевидно, что для развития эвристики имеет смысл только полиномиальный. Применение этих методов подходит для решения реальных проблем или больших задач, настолько неудобных с вычислительной точки зрения, что для них нет даже алгоритма, способного найти приближенное решение за полиномиальное время.
источник