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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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

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

Answer 11

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

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

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

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

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

Answer 12

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