Vantage Point Tree / VP树

じ☆ve冰风

VP树是由Peter N. Yianilos 在1993年的论文Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces中提出的一种搜索度量空间(Metric Space)的二叉搜索树。

用途：
最邻近搜索。任何在度量空间的数据都可以生成VP树进行搜索。
度量空间定义（来自http://zh.wikipedia.org/wiki/%E5%BA%A6%E9%87%8F%E7%A9%BA%E9%97%B4）：
   1. d(x, y) ≥ 0 (非负性)
   2. d(x, y) = 0 当且仅当 x = y (不可区分者的同一性)
   3. d(x, y) = d(y, x) (对称性)
   4. d(x, z) ≤ d(x, y) + d(y, z) (三角不等式)。
在RM中可能的应用：
1. 坐标系就是度量空间，可用于给出一个点，寻找一定半径内的所有点（测试工程的测试就是这个）
2. 拼写纠错，词汇之间的编辑距离也是度量距离

优点：
搜索复杂度：O(log(N))，当然随着搜索半径的增加，复杂度会增加。例如你有一本10万字的词典，给你一个词，搜索所有只差一个字母的词，全部词遍历一次的话要访问10万个词，用VP树最优化的情况下只需要访问(log(100000)/log(2)约等于17)个词。

缺点：
由于VP树是静态的，无法在其身上实现插入和删除操作。
大量距离查询操作，所以最好能缓存距离查询。
更先进的最邻近搜索算法请参考下面的链接或Google。

扩展阅读：
http://en.wikipedia.org/wiki/Nearest_neighbor_search

下面是VP树的实现代码，不保证优化，仅供参考：

1. #==============================================================================# ■ VPTree#------------------------------------------------------------------------------#   用于metric space的搜索树  #==============================================================================class VPTreeNode  #--------------------------------------------------------------------------  # ● 实例变量  #--------------------------------------------------------------------------  attr_accessor :parent, :left, :right, :data, :threshold, :dist_proc  #--------------------------------------------------------------------------  # ● 初始化  #--------------------------------------------------------------------------  def initialize(args, &block)    # 如果传递了块    if block != nil      @dist_proc = block    # 没有传递块的话就用distance(other)    else      @dist_proc = Proc.new{|a, b|        a.distance(b)      }    end    # 大于两个数据的话，随机取一个数据为这个节点的data（这里取中间一个）    # 用其他数据到这个数据的距离的中位数作为threshold，    # 小于等于threshold加入左子树，大于threshold加入右子树    if args.size > 2      median = args.size / 2      @data = args.delete_at(median)      args.sort!{|a, b| @dist_proc.call(@data, a)   @dist_proc.call(@data, b)}      @threshold =  @dist_proc.call(@data, args[median - 1])      @left = VPTreeNode.new(args[0, median], &@dist_proc)      @left.parent = self      @right = VPTreeNode.new(args[median, args.size - median], &@dist_proc)      @right.parent = self    # 如果只剩2个数据的话    elsif args.size == 2      @data = args[0]      @threshold =  @dist_proc.call(@data, args[1])      @left =  VPTreeNode.new(args[1, 1], &@dist_proc)      @left.parent = self    # 只剩一个数据的话    elsif args.size == 1      @data = args[0]    end  end  #--------------------------------------------------------------------------  # ● 是否叶节点  #--------------------------------------------------------------------------  def leaf?    return (@left == nil && @right == nil)  end  #--------------------------------------------------------------------------  # ● 输出  #--------------------------------------------------------------------------  def inspect    return ""  end  #--------------------------------------------------------------------------  # ● 检查节点有效性  #--------------------------------------------------------------------------  def node_valid?    if @left != nil      @left.each{|child_data|        if @dist_proc.call(@data, child_data) > @threshold          return false        end      }    end    if @right != nil      @right.each{|child_data|      if @dist_proc.call(@data, child_data)  @threshold      @right.each_within(sample, dist, &block)    end  end  #--------------------------------------------------------------------------  # ● 迭代  #--------------------------------------------------------------------------  def each(&block)    yield(@data)    @left.each(&block) if @left != nil    @right.each(&block) if @right != nil  endend复制代码

复制代码

测试工程下载：

             本帖来自P1论坛作者veal，因Project1站服务器在国外有时候访问缓慢不方便作者交流学习，经联系P1站长fux2同意署名转载一起分享游戏制作经验，共同为国内独立游戏作者共同创造良好交流环境，原文地址：https://rpg.blue/forum.php?mod=viewthread&tid=130819  若有侵权，发帖作者可联系底部站长QQ在线咨询功能删除，谢谢。