閉じたノードを再計算して、その方法で戻ってもよいことをアルゴリズムに伝えるにはどうすればよいですか?
それはOKではないので、あなたはしません。最適なパスには、行き止まりに足を踏み入れてから再び戻ることは含まれません。これは定義上、次善のパスです。A* アルゴリズムは、最適なパスを見つけます。
アルゴリズムに自分自身に戻るように指示した場合、元のより良いノードに再び戻るのを止めるにはどうすればよいですか。効果的に 2 つのノード間を繰り返し行き来します。
それを止めるものは何もありません。だからこそ、あなたが説明していることをするのは悪い考えです。それをするときに痛い場合は、それをしないでください。
私が使用しているヒューリスティック....
かなりめちゃくちゃに見える。
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.
それは理にかなっていますか？