Я читал это: http://en.wikipedia.org/wiki/A*_search_algorithm
В нем сказано, что A * быстрее, чем использование dijkstra, и использует наилучший-первый поиск, чтобы ускорить процесс.
Если мне нужен алгоритм для запуска в миллисекундах, когда A * станет самым заметным выбором.
Из того, что я понимаю, это не обязательно возвращает наилучшие результаты.
Если мне нужны быстрые результаты, лучше ли предварительно вычислять пути? Для их хранения может потребоваться мегабайт.
Он говорит, что A * быстрее, чем использование dijkstra, и использует поиск наилучшего поиска ускоряйте процесс.
A * - это, в основном, информированное изменение Dijkstra.
A * считается "лучшим первым поиском", потому что он с жадностью выбирает, какую вершину исследовать дальше, в соответствии со значением f(v) [f(v) = h(v) + g(v)] - где h - эвристика, а g - это стоимость пока.
Обратите внимание, что если вы используете неинформативную эвристическую функцию: h(v) = 0 для каждого v: вы получаете, что A * выбирает, какая вершина должна развиваться следующей в соответствии с "пока стоимостью" (g(v)), как алгоритм Дейкстры, поэтому, если h(v) = 0, A * по умолчанию используется алгоритмом Дейкстры.
Если мне нужен алгоритм для запуска в миллисекундах, когда A * станет самый выдающийся выбор.
Не совсем, это зависит от многих вещей. Если у вас есть эвристическая функция спуска - из моего личного опыта, жадный лучше всего (выбор в соответствии с эвристической функцией в одиночку) - обычно значительно быстрее, чем A * (но даже не близок к оптимальному).
Из того, что я понимаю, это не обязательно возвращает лучшее Результаты.
A * является полным (находит путь, если он существует) и оптимальный (всегда находит кратчайший путь), если вы используете допустимая эвристическая функция. Если ваша функция недопустима - все ставки отключены.
Если мне нужны быстрые результаты, лучше ли предварительно вычислять пути? Это может возьмите мегабайты пространства для их хранения.
Это обычная оптимизация для некоторых проблем, например, в проблема с 15 головоломками, но она более продвинута. Путь от точки A до точки B называется макросом. Некоторые пути очень полезны и их следует помнить. Компонент Machine Learning добавлен в алгоритм, чтобы ускорить процесс, помня эти макросы.
Обратите внимание, что путь от точки A до точки B здесь обычно не находится на графике состояний, а в самой проблеме (например, как перемещать квадрат от нижней строки до верхней строки...)
Чтобы ускорить работу:
Если у вас есть эвристика, и вы находите ее слишком медленной, и вам нужно более быстрое решение, даже если оно не оптимально - A * Epsilon обычно быстрее, чем A *, давая вам оценку оптимальности пути (насколько он близок к оптимальному).
Dijkstra - частный случай для A * (когда эвристики равны нулю).
A * поиск:
Он имеет две функции стоимости.
g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.
Общая стоимость каждого node вычисляется по формуле f (n) = g (n) + h (n)
Дейкстры:
Он имеет одну функцию затрат, которая представляет собой реальное себестоимость от источника к каждому node: f (n) = g (n) Он находит кратчайший путь от источника ко всем другим node, рассматривая только реальную стоимость.
A * похож на Dijkstra, единственное отличие состоит в том, что A * пытается найти лучший путь, используя эвристическую функцию, которая дает приоритет узлам, которые должен быть лучше других, в то время как Дейкстра просто исследует все возможные пути.
Его оптимальность зависит от используемой эвристической функции, поэтому да, она может вернуть не оптимальный результат из-за этого и в то же время улучшить эвристику для вашего конкретного макета, и лучше будет результат (и, возможно, скорость).
Он должен быть быстрее Dijkstra, даже если он требует больше памяти и больше операций на node, так как он исследует намного меньше узлов, и выигрыш хорош в любом случае.
Предварительная вычисление путей может быть единственным способом, если вам нужны результаты в реальном времени, а график довольно велик, но обычно вы хотите, чтобы маршрут был менее вероятным (я предполагаю, что вы хотите рассчитать его часто).
Эти алгоритмы могут использоваться для поиска путей и обхода графика, процесса построения эффективного направления между несколькими точками, называемыми узлами.
Формула для a* is f =g + h., g означает фактическую стоимость, а h означает эвристические затраты.
Формула для Dijktras f = g. нет эвристической стоимости. когда мы используем a*, и если эвристическая стоимость 0, то она будет равна Dijktras algorithem.
Короткий ответ: A * использует эвристику для оптимизации поиска. То есть вы можете определить функцию, которая в некоторой степени может оценить стоимость от одного node до цели. Это особенно полезно, если вы ищете путь по географическому представлению (карте), где вы можете, например, угадать расстояние до цели из заданного графа node. Следовательно, обычно A * используется для поиска пути в играх и т.д. Где Djikstra используется в более общих случаях.
Нет, A * не всегда даст лучший путь. Если эвристика является "географическим" расстоянием, следующий пример может дать не оптимальный путь.
[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
|----------------------------------------------------------------|