任意のポイントが最大4つの他のポイント（北東〜西南地区）に接続されている単純なグリッドを考えてみましょう。A-star：複数目標のヒューリスティック
私は、選択された初期ポイントからのいずれかののゴールポイントまでの最小ルートを計算するプログラムを書く必要があります（いずれの2つのゴール間にもゴールポイントからなるルートがあります）。もちろん、グリッドには障害が存在する可能性があります。
私のソリューションは非常にシンプルです。私は変数ヒューリスティック関数h（x） - xから最も近いゴールポイントまでのマンハッタン距離を持つA *アルゴリズムを使用しています。最寄りのゴールポイントを見つけるには、直線探索（O（n）でn個のゴールポイントが必要）をしなければなりません。ここに私の質問があります：ダイナミックに最も近いゴールポイント（時間< O（n））を動的に見つけるための効率的なソリューション（ヒューリスティック関数）がありますか？
または、おそらくA *は問題を解決するには良い方法ではありませんか？
目標、数十、または千の数はいくつですか？何十万人ものあなたのやり方がうまくいくならば、何千もの人がnearest neighbor searchの場合、すぐにデータを検索するためのアイデアが得られます。
このようなトレードオフは空間的にデータを整理して検索するのに時間がかかり、小規模な設定では管理が簡単になります。あなたが絶えず評価しているので、私は、データを構造化することは、非常に低い点で価値があると思う。
これを行うもう1つの方法は、変更されたフラッドフィルアルゴリズムで、フラッド中に宛先ポイントに到達すると停止します。
まず、最適化によってコードが複雑になるため、最適化する必要があるかどうかを判断します。少数のゴールでは、現在のソリューションはマンハッタンのような単純なヒューリスティックに適しています。
最初の手順を実行する前に、各目標のヒューリスティックを計算します。最も近い目標を現在選択されている目標と覚えて、それに向かって移動するが、他のすべての距離から目標に向かって可能な最大限の進捗を差し引く。この第2の値を「メタヒューリスティック」と考えることができます。それは他の目標のためのヒューリスティックの楽観的な見積もりです。
以降の手順では、現在のゴールのヒューリスティック、およびヒューリスティック以下の "メタヒューリスティック"のゴールを計算します。他の目標は、おそらくより良いヒューリスティックを持つことができないので、それらを計算する必要はありません。最も近い目標が新しい現在の目標になります。可能な限り進歩を差し引いて、他のものから進んでいく。あなたが目標に達するまで繰り返す。
私の問題は大規模なグリッド（約10^5×10^5）と多数の目標のためです。ご回答ありがとうございました。 – ThereIsElse
多くのゴールをお持ちの場合は、A *を開始する前にゴールについてボロノイ図を計算することを検討してください。次に、ダイアグラムを見て、特定のポイントに最も近いゴールを確認します。 – erickson
Dijkstraのアルゴリズムを使用してください。アルゴリズムは、すべての到達可能ポイントに最小コストを出力します。次に、出力からゴールポイントを選択するだけです。
ありがとう、NNSは私が必要なものです:)。 – ThereIsElse