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

103

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

уличный парад
источник
3
см. en.wikipedia.org/wiki/Heuristic_algorithm
Ник Дандулакис,
1
Если вы посмотрите на эвристический алгоритм как на своего рода древовидную структуру, я думаю, вы могли бы назвать его алгоритмом специального назначения.
Джеймс П.
Эвристика - это алгоритм, который (доказуемо) не работает.
JeffE

Ответы:

99

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

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

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

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

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

Крисс
источник
3
Еще одно распространенное использование эвристики - обнаружение вирусов, когда вы не можете быть уверены в том, что вирус существует, но можете искать определенные ключевые атрибуты вируса.
Дана Холт
Да, это правда, и для взламывающих программ
streetparade
1
@kriss, итак .. эвристика это разновидность алгоритма.
Pacerier 02
1
@Pacerier: да. Это алгоритм, помогающий ориентироваться в пространстве решения конкретной проблемы. Вы также можете рассматривать это как стратегию модификации алгоритма, чтобы сделать его практичным (метаалгоритм). Это все еще алгоритм, все методы, и эвристика определенно метод.
Крисс
33
  • Алгоритм обычно детерминирован и доказал, что дает оптимальный результат.
  • Эвристика не имеет доказательства правильности, часто включает случайные элементы и может не дать оптимальных результатов.

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

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

Майкл Боргвардт
источник
2
Я бы не сказал, что доказано, что алгоритм дает оптимальный результат: это зависит от алгоритма, применительно к какой проблеме.
nbro
Достижение оптимального результата - не главное качество алгоритмов, это точность, то есть точный результат, тогда как эвристика дает вам приблизительные результаты.
Марина Данст
22

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

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

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

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

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

Бухаке Синди
источник
8

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

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

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

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

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

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

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

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

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

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

Joost
источник
Я считаю, что ваше определение слова «алгоритм» слишком ограничительно. Подразумевает ли использование последовательности слов непараллельность? Алгоритмы Parallell сейчас хороши и даже обычны. А как насчет решения задачи с помощью нейронной сети? Или инструмент распространения ограничений? Алгоритмы? Мета-алгоритмы?
Крисс
У читателя возникает ощущение, что проблемы NP усугубляются. Это неправда. Существуют действительно сложные проблемы, требующие действительно плохих алгоритмов, таких как экспоненциальные или хуже. NP являются особенными, потому что если у нас есть решение, его легко и быстро проверить, а найти его очень сложно, если у нас его еще нет. Проверить, что у нас есть правильные инструкции, чтобы выбраться из лабиринта, несложно, гораздо труднее найти выход. Таким образом, NP являются одновременно легкими и сложными, если бы мы могли опробовать все возможные решения одновременно (недетерминированно), решить это было бы очень просто ... но мы не можем.
Крисс
Спасибо за ответ! Я немного обновил формулировку и подошел к ней иначе. На мой взгляд, распространение ограничений - это метод приближения к чему-то, но это еще не алгоритм, который описывает, как поэтапно прийти к решению, описанному в разделе распространения ограничений. Вы, конечно, правы насчет классов expspace и «хуже», я тоже добавил примечание по этому поводу. Кстати: напишите NP-Complete и / или NP-Hard полностью, так как подмножество NP также содержит «эффективно» решаемые проблемы, которые (предположительно не принадлежат) к тому же классу.
Joost
Конечно, вы правы, мне следовало написать NP-Complete. Виноват.
Крисс
Это намного лучше, чем то, что один из моих коллег называет: NP-ness (что звучит просто ужасно и немного мерзко ...)
Joost
6

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

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

Anthares
источник
4

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

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

dsm
источник
4

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

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

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

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

Слава
источник
3

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

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

Лазарь
источник
2

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

IVlad
источник
2

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

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

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

A_tanA
источник
ой !! орфографическая ошибка, это должно быть «Искусственный интеллект»
A_tanA
2

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

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

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

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

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

Эдвин Далорцо
источник
Утверждать, что существует разница между алгоритмом и эвристикой, - все равно что утверждать, что есть разница между птицей и курицей. Эвристика - это разновидность алгоритма.
Joost
0

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

кафка
источник