Я не понимаю, как следующий график дает субоптимальное решение с поиском A *. 
Субоптимальное решение, данное A * search
График выше был приведен в качестве примера, где поиск A * дает субоптимальное решение, то есть эвристика допустима, но не является последовательной. Каждому узлу соответствует эвристическое значение, соответствующее ему, и дается вес прохождения объекта. Я не понимаю, как поиск A * будет расширять узлы.
Честно говоря, я не вижу, как A * может вернуть неоптимальное решение с заданной эвристикой. Это по простой причине: данная эвристика допустима (и даже монотонна/согласована).
h(s) <= h*(s) for each s in the graph
Вы можете проверить это самостоятельно, сравнивая значение h в каждом узле с стоимостью кратчайшего пути до g.
Учитывая свойство оптимальности A *, я не вижу, как он может вернуть неоптимальное решение, которое должно быть S -> A -> G, конечно.
Единственный способ вернуть субоптимальное решение - если он остановится после того, как действие с узла на границе, ведущее к цели, будет найдено (так, чтобы было путь к цели), , но это не было бы A *.
Эвристика h (n) несовместима.
Позвольте мне сначала определить, когда эвристическая функция считается последовательной.
h(n) is consistent if
– for every node n
– for every successor n' due to legal action a
– h(n) <= c(n,a,n') + h(n')
Здесь явно «А» является правопреемником к узлу «B» но h(B) > h(A) + c(A,a,B)
Поэтому эвристическая функция не соответствует/монотонной, и поэтому А * не обязательно должен дать оптимальное решения.
Только A * с «графическим поиском» вернет неоптимальное решение. См. Http://stackoverflow.com/questions/10680180/graph-search-vs-tree-search/15281447#15281447. – ziggystar
Imho псевдо-реализация «диаграммы A *» является действительно плохим, но это может быть единственной причиной для решения субоптима. – Demplo