В алгоритме A* отсутствует вычисление

Как мне пересчитать закрытый узел, чтобы сообщить моему алгоритму, что можно вернуться таким образом?

Нет, потому что это не нормально. Оптимальный путь никогда не включает в себя заход в тупик и выход обратно! Это по определению неоптимальный путь. Алгоритм A* находит оптимальный путь.

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

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

Эвристика, которую я использую...

Выглядит довольно запутанным.

У вас есть G — манхэттенское расстояние от начала до цели, H — манхэттенское расстояние от текущей точки до цели, а F — их сумма.

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

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

Судя по вашим вопросам, я думаю, что вы не понимаете алгоритм и почему он работает. Мой совет — понять, как работает алгоритм, прежде чем пытаться его реализовать. Вот алгоритм на английском:

The closed set is an empty set of points.
The queue is an empty queue of paths, ordered by path cost.
Enqueue a path from the start to the start with zero cost.
START: 
If the queue is empty, then there is no solution.
The current path is the cheapest path in the queue.
Remove that path from the queue.
If the last step on the current path is closed then 
    the current path is necessarily bad. (Do you see why?)
    Discard it and go back to the START of the loop.
Otherwise, if the last step on the current path is the destination then
    the current path is the optimal path to the destination, so we're done.
Otherwise, we have the cheapest path *to the last 
    point in that path*. (Do you see why?) 
Therefore, every other path that could possibly go through that point is worse.
Therefore, close off that point. Add it to the closed set so that we can 
    automatically discard any future path that goes through that point.
For each possible direction from the last point of the current path,
    make a new path that extends the current path in that direction.
    The estimated cost of that new path is the known cost to get 
    to its end from the start, plus the estimated cost to get from
    its end to the destination.
    Enqueue the new path with that cost.
Go back to the START of the loop.

Имеет ли это смысл?

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

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

http://www.cs.unh.edu/~ruml/papers/rtds-socs10.pdf

http://www.cs.unh.edu/~ruml/papers/rtds-socs10-talk.pdf

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

Ваша эвристика неприемлема. Вы должны найти другую эвристику.

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

Я решал аналогичную проблему в Matlab пару месяцев назад.

Г - твоя проблема. G говорит вам, в чем сложность перемещения из вашего начального местоположения по пути, это не эвристика. Это познаваемо, и вам не нужно его оценивать.

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

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

рассмотрим следующий пример, в котором вы пытаетесь перейти от A к B. Согласно вашему уравнению, местоположение T будет G = 4, H = 2 и F = 4 + 2 = 6.

00000
00X00
00X00
00XT0
A0X0B

Реальный путь A* будет представлен знаком + с G=10, H=2 и F=12.

0+++0
0+X+0
0+X+0
0+XT0
A+X0B

вычисление G таким образом должно решить проблему.