投稿を明確にするために、コメントに基づいて編集しました。
エッジコストが非対称の場合に、最近傍探索を効率的に実装する方法を考えていました。100から12000のような都市の範囲を考えています。
より詳細には、例として、都市Aから都市Bへの移動（徒歩など）にはコストCOST 1がかかり、 BからAへの移動（電車など）にはコストCOST1 /10がかかります。言い換えれば、ここで私が見ている問題は、移動する都市間のコストを表す非対称行列Cがあり、1つのポイントAを選択した場合、たとえば、最も近い3つの隣接する都市B 1、B 2、B3を効率的に検出する方法です。旅費の面で？クエリを繰り返し実行したい。前処理時間は、膨大ではないにしても大丈夫です。
効率を熟考することで、都市間のコストが対称であるO（lg（n））時間でk最近傍を見つけるのを容易にするkdツリーのようなものを考えることができました。私の場合、これは基本的なkdツリーだけの問題です。これは、2つの都市間での移動コストが両方向で一般的に同じではないためです。問題の要点は、非対称の場合にk最近傍法のようなことをどのように行うことができるかということのようです。
前述の対称性の仮定を修正するために、1本の木ではなく、2本の木を構築してコストを両方向に計算することを考え、両方の木を検索しました。それから私は疑問に思いました、非対称のコストのために特別に何かがすでにあるかどうか、そして/またはアイデアとして2本の木を使用することは完全に間違っているかどうか誰かが知っていますか？
また、2次元のkd木が、必ずしも最適なソリューションであるとは限りません。したがって、他のデータ構造やアルゴリズムへのポインタも歓迎します。特に誰かが私の問題の大きさに関して実際的な経験を持っているなら。ウィキペディアにはかなりの数のアプローチがリストされており、おそらくおおよその解決策でさえ、私がやろうとしていることに適しています（これは学習目的の小さなゲーム用です）。