А * График

Question

Учитывая эвристические значения Н (А) = 5, Н (В) = 1, с использованием поиска * графа, это поставит А и В на границе с F (A) = 2 + 5 = 7, f (B) = 4 + 1 = 5, затем выберите B для расширения, затем поместите G на границу с f (G) = 4 + 4 = 8, затем он выберет A для расширения, но ничего не сделают, так как S и B уже расширены, а не на границе, и поэтому он будет выбирать G next и возвращать неоптимальное решение.

Является ли мой аргумент правильным?

Answer 1

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

Звезда - это всего лишь способ найти разумный путь, но не находит оптимальный по всему миру путь.

Answer 2

Есть два эвристические понятия здесь:

1. Допускаемое эвристический: Когда для каждого узла п в графе, ч (п)никогда не переоценивает стоимость достижения цели ,

2. Последовательный эвристический: Когда для каждого узла п в графе и каждый узел м его наследников, ч (п) < = H (M) + с (п, м), где c (n, m) - стоимость дуги от n до m.

эвристическая функция является допустимой, но не соответствует, так как вы показали:

ч (А)> Н (В) + с (А, Б), 5> 2.

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

f (A) = g (A) + h (A) = 7> f (B) = g (B) + h (B) = 5,

эта эвристическая функция не удовлетворяет этому свойству.

Что касается A *:

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

Итак, отвечая на ваш вопрос, алгоритм A * должен быть реализован для повторного открытия узлов при обнаружении более короткого пути к узлу (обновление также новой стоимости пути), и этот новый путь будет добавлен к открытому set или frontier, поэтому ваш аргумент неверен, , так как B должен быть добавлен снова к границе (теперь с дорожкой S-> A-> B и стоимостью 3).

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