グリッド（2Dアレイ）を使用してGBFSとA*を実装しようとしています。先に進む前に...両方のアルゴリズムが以前の場所を覚えているかどうかを考えます。そうであれば、ヒューリスティックが優れている場合、つまり兄弟の子のノードにジャンプする場合、その場所にジャンプすることを意味しますか？兄弟の子は、現在のノードの子よりも優れたヒューリスティックを持っていますか？たとえば、8x8グリッドがあり、座標7,7にいて、その隣のセルをチェックした場合、PriorityQueueには、次のセルよりもヒューリスティックが優れた座標3,5があります。 7,7に...3,5にジャンプしますか？
答えが「はい」の場合、私の問題は、ある場所から別の場所にジャンプできる場合、PriorityQueueから削除された返されたノードから正しいパスをどのように作成するかです。つまり、実際のパスを作成するためにノードをどのようにトリミングしますか？
両方のアルゴリズムが以前の場所を記憶していますか？そうであれば、ヒューリスティックが優れている場合はその場所にジャンプします。つまり、兄弟の子が現在のノードよりも優れたヒューリスティックを持っている場合は、兄弟の子のノードにジャンプします。子供？
はい、両方に。
ノードを優先キューに挿入するときは、ノードの「親」ノード、つまりノードの前にあるノードを追跡する必要があります。たとえば、7,7にいて、8,7をキューに追加する場合は、8,7の親を7,7に設定する必要があります。
このようにして、親のチェーンをたどることにより、任意のノードから開始ノードに戻ることができます。
8x8グリッドがあり、座標7,7を使用していて、その隣のセルを確認した場合、PriorityQueueには、7,7の隣のセルよりもヒューリスティックが優れた座標3,5があります... 3.5にジャンプしますか？
はい。7,7の後に3,5を考慮しても、プレーヤーが3,5に「ジャンプ」しているわけではありません。これは、少なくとも一時的に、3,5を通過するパスの方が、7,7を通過するパスよりも有望であると思われるため、彼は現在、代替パスを検討していることを意味します。
PriorityQueueから削除された返されたノードから正しいパスを作成するにはどうすればよいですか？
最終的には、ゴールノードに到達します。ゴールノードが6,6で、6,5からそこに到達したとします。そこにたどり着いた道をどのように再構築しますか？
これにより、最終的には開始ノードに戻り、それが（逆の）パスになります。
前の質問に基づいて、このサンプル画像を見てください。各矢印は、使用する親ポインターの1つを表します。検索が1つのパスから別のパスに「ジャンプ」するたびに、色を変更しました。検索中にアクセスしたノードから開始し、矢印に従って開始ノードに戻る方法に注目してください。