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

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

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

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

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

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

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

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

Есть некоторые совпадения: «генетические алгоритмы» — общепринятый термин, но, строго говоря, это эвристика, а не алгоритмы.

Эвристика, в двух словах, - это «Обоснованная догадка». Википедия хорошо объясняет. В итоге в качестве оптимального решения указанной проблемы принимается метод «общего признания».

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

Говоря более точно, эвристики означают стратегии, использующие легкодоступную, хотя и слабо применимую информацию, для управления решением проблем людьми и машинами.

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

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

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

Существуют определенные категории алгоритмов, одной из которых является эвристический алгоритм. В зависимости от (доказанных) свойств алгоритма в этом случае он попадает в одну из этих трех категорий (примечание 1):

• Точное: доказано, что решение является оптимальным (или точное решение) входной задачи
• Аппроксимация: доказано, что отклонение значения решения больше никогда не увеличивается от оптимального значения, чем некоторая заранее определенная граница (например, никогда не более чем на 50% больше, чем оптимальное значение)
• Эвристика: эффективность алгоритма не доказана. оптимальным, ни в пределах заранее определенной границы оптимального решения

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

Для некоторых задач никто так и не нашел «эффективного» алгоритма для вычисления оптимальных решений (примечание 2). Одной из таких задач является известная задача коммивояжера. Алгоритм Кристофидеса для задачи коммивояжера, например, раньше назывался эвристикой, поскольку не было доказано, что его решение находится в пределах 50 % от оптимального. Однако, поскольку это было доказано, алгоритм Кристофидеса правильнее называть алгоритмом аппроксимации.

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

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

(примечание 1). Кроме того, алгоритмы характеризуются тем, включают ли они случайные или недетерминированные элементы. Алгоритм, который всегда выполняется одинаково и дает один и тот же ответ, называется детерминированным.

(примечание 2): это называется проблемой P vs NP, и задачи, которые классифицируются как NP-полные и NP-сложные, вряд ли будут иметь "эффективный" алгоритм. Примечание; как @Kriss упомянул в комментариях, есть еще «худшие» типы проблем, для вычисления которых может потребоваться экспоненциальное время или пространство.

Есть несколько ответов, которые отвечают на часть вопроса. Я посчитал их менее полными и недостаточно точными и решил не редактировать принятый ответ @Kriss

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

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

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

Итак, если вы знаете, как решить проблему, используйте алгоритм. Если вам нужно разработать решение, то это эвристика.

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

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

Алгоритм — это последовательность некоторых операций, которые при наличии входных данных что-то вычисляют (функцию) и выводят результат.

Алгоритм может давать точные или приблизительные значения.

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

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

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

Я думаю, что эвристика - это скорее ограничение, используемое в модели на основе обучения в искусственном интеллекте, поскольку будущие состояния решения трудно предсказать.

Но тогда я сомневаюсь после прочтения приведенных выше ответов: «Как эвристика может быть успешно применена с использованием методов стохастической оптимизации? Или они могут функционировать как полноценные алгоритмы при использовании со стохастической оптимизацией?»

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

Одно из лучших объяснений, которые я читал, взято из замечательной книги Code Завершить, которое я сейчас цитирую:

Эвристика — это метод, который помогает вам искать ответ. Его результаты зависят от случая, потому что эвристика говорит вам только, как искать, а не что найти. Он не говорит вам, как добраться прямо из пункта А в пункт Б; он может даже не знать, где находятся точка А и точка Б. По сути, эвристика — это алгоритм в клоунском костюме. Это менее предсказуемо, это веселее и не дает 30-дневной гарантии возврата денег.

Вот алгоритм проезда к чьему-то дому: Двигайтесь по шоссе 167 на юг до Пюи-аллапа. Выйдите из торгового центра South Hill и проедьте 4,5 мили в гору. Поверните направо на светофоре у продуктового магазина, а затем поверните на первом повороте налево. Сверните на подъездную дорожку к большому коричневому дому слева, по адресу 714 North Cedar.

Вот эвристика, как добраться до чьего-то дома: найдите последнее письмо, которое мы вам отправили. Поездка в город по обратному адресу. Когда доберетесь до города, спросите у кого-нибудь, где наш дом. Нас все знают — кто-то будет рад вам помочь. Если вы не можете никого найти, позвоните нам по общественному телефону, и мы приедем за вами.

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

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