Эвристический и A * алгоритм

Question

Я читал об алгоритме Дейкстры и алгоритме * звезды.Я знаю, что разница заключается в эвристическом использовании.Но что такое эвристика и как это влияет на алгоритмы?Эвристика это просто способ измерить расстояние?Но дейкстра тоже считает расстояние?Извините, но мой вопрос касается эвристики, что это значит и зачем их использовать ... (я читал об этом, но не постоянно) Другой вопрос: когда следует использовать каждый из них?

Спасибовы

Answer 1

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

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

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

Что касается того, когда вам следует использовать каждый из них, это действительно зависит от приложения.Однако использование алгоритма A * требует допустимой эвристики, поэтому это может быть неприменимо в ситуациях, когда такая информация недоступна для алгоритма.

Answer 2

Dijkstra решает проблему маршрутизации из одного источника, т. Е. Дает вам стоимость перехода из одной точки в любую другую точку пространства.

A * решает проблему из одного источника из одного источника.Это дает вам минимальное расстояние пути от данной точки до другой данной точки.

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

Answer 3

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