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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

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

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

Answer 8

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

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

Answer 9

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

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

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

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

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

Answer 10

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

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

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