Vantage Point Tree / VP树

veal

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. #==============================================================================
   
2. # ■ VPTree
   
3. #------------------------------------------------------------------------------
   
4. #   用于metric space的搜索树  
   
5. #==============================================================================
   
6. 
   
7. class VPTreeNode
   
8.   #--------------------------------------------------------------------------
   
9.   # ● 实例变量
   
10.   #--------------------------------------------------------------------------
    
11.   attr_accessor :parent, :left, :right, :data, :threshold, :dist_proc
    
12.   #--------------------------------------------------------------------------
    
13.   # ● 初始化
    
14.   #--------------------------------------------------------------------------
    
15.   def initialize(args, &block)
    
16.     # 如果传递了块
    
17.     if block != nil
    
18.       @dist_proc = block
    
19.     # 没有传递块的话就用distance(other)
    
20.     else
    
21.       @dist_proc = Proc.new{|a, b|
    
22.         a.distance(b)
    
23.       }
    
24.     end
    
25.     # 大于两个数据的话，随机取一个数据为这个节点的data（这里取中间一个）
    
26.     # 用其他数据到这个数据的距离的中位数作为threshold，
    
27.     # 小于等于threshold加入左子树，大于threshold加入右子树
    
28.     if args.size > 2
    
29.       median = args.size / 2
    
30.       @data = args.delete_at(median)
    
31.       args.sort!{|a, b| @dist_proc.call(@data, a) <=>  @dist_proc.call(@data, b)}
    
32.       @threshold =  @dist_proc.call(@data, args[median - 1])
    
33.       @left = VPTreeNode.new(args[0, median], &@dist_proc)
    
34.       @left.parent = self
    
35.       @right = VPTreeNode.new(args[median, args.size - median], &@dist_proc)
    
36.       @right.parent = self
    
37.     # 如果只剩2个数据的话
    
38.     elsif args.size == 2
    
39.       @data = args[0]
    
40.       @threshold =  @dist_proc.call(@data, args[1])
    
41.       @left =  VPTreeNode.new(args[1, 1], &@dist_proc)
    
42.       @left.parent = self
    
43.     # 只剩一个数据的话
    
44.     elsif args.size == 1
    
45.       @data = args[0]
    
46.     end
    
47.   end
    
48.   #--------------------------------------------------------------------------
    
49.   # ● 是否叶节点
    
50.   #--------------------------------------------------------------------------
    
51.   def leaf?
    
52.     return (@left == nil && @right == nil)
    
53.   end
    
54.   #--------------------------------------------------------------------------
    
55.   # ● 输出
    
56.   #--------------------------------------------------------------------------
    
57.   def inspect
    
58.     return "<Node: #{@data.inspect}, @threshold = #{@threshold}>"
    
59.   end
    
60.   #--------------------------------------------------------------------------
    
61.   # ● 检查节点有效性
    
62.   #--------------------------------------------------------------------------
    
63.   def node_valid?
    
64.     if @left != nil
    
65.       @left.each{|child_data|
    
66.         if @dist_proc.call(@data, child_data) > @threshold
    
67.           return false
    
68.         end
    
69.       }
    
70.     end
    
71.     if @right != nil
    
72.       @right.each{|child_data|
    
73.       if @dist_proc.call(@data, child_data) <= @threshold
    
74.         return false
    
75.       end
    
76.       }
    
77.     end
    
78.     return true
    
79.   end
    
80.   #--------------------------------------------------------------------------
    
81.   # ● 检查树有效性
    
82.   #--------------------------------------------------------------------------
    
83.   def valid?
    
84.     each{return false if !node_valid?}
    
85.     return true
    
86.   end
    
87.   #--------------------------------------------------------------------------
    
88.   # ● 迭代小于等于dist的所有data
    
89.   #--------------------------------------------------------------------------
    
90.   def each_within(sample, dist, &block)
    
91.     # 获得sample到data的距离
    
92.     sample_dist = @dist_proc.call(@data, sample)
    
93.     # 如果这个距离小于dist，就迭代data
    
94.     if sample_dist <= dist
    
95.       yield(@data)
    
96.     end
    
97.    
    
98.     # 需要迭代左子树的情况
    
99.     if @left != nil && @threshold + dist >= sample_dist
    
100.       @left.each_within(sample, dist, &block)
     
101.     end
     
102.     # 需要迭代右子树的情况
     
103.     if @right != nil && sample_dist + dist  > @threshold
     
104.       @right.each_within(sample, dist, &block)
     
105.     end
     
106.   end
     
107.   #--------------------------------------------------------------------------
     
108.   # ● 迭代
     
109.   #--------------------------------------------------------------------------
     
110.   def each(&block)
     
111.     yield(@data)
     
112.     @left.each(&block) if @left != nil
     
113.     @right.each(&block) if @right != nil
     
114.   end
     
115. end

复制代码

测试工程下载：
VPTree.rar (729.91 KB, 下载次数: 123)

2009-8-7 02:41 上传

点击文件名下载附件

DeathKing

在考虑受到启发写华容道的最优路径算法（虽然有一大群人比我还挨球早就有研究{:nm_7:}）

veal

就是因为Ruby令人发指的速度才需要优化的数据结构=v=
当然一般的游戏是用不上这个的。例子那里已经说了：坐标查询和拼写检查。

dbshy

时间复杂度确实很低，不过在下觉得RM有点用不上比较NB的数据结构
因为本身RM的数据范围很小