A* アルゴリズムを使用して家の中のパスを見つけているとします。これで、実行時間は O(n^2) になる可能性があります。
どのドアに従うべきかを知っていれば、パフォーマンスが向上するのではないかと考えていました。それに応じて A* を適用します。つまり、開始位置Sと最終位置Fが私がA *を適用した場合、より良くなる
`S` and `A1`
`A1` and `A2`
`A2` and F.
A1 と A2 は、最短経路をたどる必要がある私の中間 (ドア) はどこですか? 中間体を見つけてパスをたどり、開始時と終了時に A* を直接適用するだけでなく、改善する価値がありますか。
中間体を見つけるのに線形時間がかかることを考慮してください。
O(n^2)はい、アルゴリズムが実行時に動作する場合、これは非常に役立ちます。1 つの大きな問題の代わりに、2 つの小さな問題が発生し、それぞれの計算コストが 1/4 になります。
役に立たない、または害さえある病理学的なケースがあると確信していますが、あなたのシナリオ（家）では、おそらく大いに役立つでしょう.
フロアを移動するにはエレベーターや階段を上らなければならないという事実を利用していると思います。コスト関数は単一のフロア内でのみ機能する必要があるため、これは A* にとって非常に役立ちます。これは、実際のコストを非常によく表しています。それとは対照的に、同じ部屋で 1 階高い階に移動したい場合、コスト関数は距離を大幅に過小評価します。その場合、ユークリッド距離は完全に失敗します (そして、アルゴリズムは徹底的な検索に劣化します)。最初に階段に移動してから、階段から目的の部屋に移動すると、はるかにうまく機能します。