为了澄清我的帖子，我根据评论对其进行了编辑。
我在考虑如何在边缘成本不对称时有效地实现最近邻搜索。我正在考虑一系列城市，例如从 100 到 12000。
更详细地，作为示例，从城市A到城市B的旅行（例如步行）的成本为 COST 1，而从B到 A 的旅行（例如乘火车）的成本为COST 1 /10 。换句话说，我在这里看到的问题是，如果我有一个代表旅行城市之间成本的不对称矩阵C并且我选择一个点A，那么如何有效地发现三个最近的相邻城市B 1、B 2和B 3在旅行费用方面？我想重复运行查询。预处理时间，即使不是很长，也可以。
效率思考让我想到了类似kd 树的东西，当城市之间的成本是对称的时，它有助于在O(lg(n))时间内找到k个最近邻居。在我的情况下，这是一个只有基本 kd 树的障碍，因为在任何两个城市之间的两个方向上的旅行成本通常都不相同。事情的要旨似乎是，在不对称的情况下，我怎么能做类似 k 近邻的事情？
为了纠正上述对称性假设，我认为我不只是一棵树，而是构建了两棵树，以便在两个方向上计算成本，然后我对这两棵树进行搜索。然后我开始怀疑，有没有人知道是否已经有专门用于不对称成本的东西和/或使用两棵树作为一个想法完全误入歧途？
它也可能是二维的 kd 树不一定是最合适的解决方案。所以也欢迎指向其他数据结构和算法的指针。特别是如果有人对我的问题大小有实践经验。维基百科列出了很多方法，甚至可能近似的解决方案对我正在尝试做的事情有好处（这是一个用于学习目的的小型游戏）。