扫描二维码关注官方公众号
返回列表
+ 发新帖
查看: 139|回复: 0

[转载发布] Vantage Point Tree / VP树

[复制链接]
累计送礼:
0 个
累计收礼:
0 个
  • TA的每日心情
    开心
    昨天 18:01
  • 签到天数: 114 天

    连续签到: 4 天

    [LV.6]常住居民II

    2338

    主题

    403

    回帖

    1万

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    VIP
    6
    卡币
    10622
    OK点
    16
    推广点
    0
    同能卷
    0
    积分
    13391

    灌水之王

    发表于 2024-4-19 17:24:52 | 显示全部楼层 |阅读模式
    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在线咨询功能删除,谢谢。

    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有账号?立即注册

    x
    天天去同能,天天有童年!
    回复 送礼论坛版权

    使用道具 举报

    文明发言,和谐互动
    文明发言,和谐互动
    高级模式
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    幸运抽奖

    社区每日抽奖来袭,快来试试你是欧皇还是非酋~

    立即查看

    聊天机器人
    Loading...

    QQ|Archiver|手机版|小黑屋|同能RPG制作大师 ( 沪ICP备12027754号-3 )

    GMT+8, 2025-3-15 00:02 , Processed in 0.074740 second(s), 55 queries .

    Powered by Discuz! X3.4

    Copyright © 2001-2020, Tencent Cloud.

    快速回复 返回顶部 返回列表