前面讲解了KD树的实现以及在KD树的基础之上进行的最近近邻查找，但是KD树上的最近邻查找有一个问题，在我系列中第一篇的提到的参考文章中就讲到KD树搜索最近邻节点的问题。在进行回溯查找的过程是一直到根节点才结束，并且还对一些不必要的节点进行了计算，这在多维空间中查找的时候，将面对效率下降的问题。针对这么问题就提出了BBF改进算法，实在KD树最近邻搜索算法的基础之上进行的改进算法。他加入了优先队列，在形成搜索路径的同时也形成了优先队列，在回溯查找的过程主要按照优先队列来进行查找，从而避免了重复路径的搜索过程。这个优先的队列的形成过程，有很多实现方法，如大顶堆，通过维护一个大顶堆，，在回溯的过程中，总是从这个优先级队列中取优先级最高的进行回溯。这个优先级的定义是目标点与搜索点在分割维度方向上的距离，这个距离通常来说都是取绝对值的。
在我的实现过程，没有使用大顶堆来实现优先队列，主要使用的Lis数据的Insert（）方法，每次在插入的时候就遍历优先队列，找到合适的位置后插入队列即可。
下面是BBF算法的代码：
1、优先队列的维护代码
#region 优先队列的添加和删除private void InsertPriorityList(Node node, float priority){PriorityList pl = new PriorityList() { node = node, priority = priority };if (priorityList.Count==0){priorityList.Insert(0, pl);return;}for (int i = 0; i < priorityList.Count; i++){if (priorityList[i].priority >= priority){priorityList.Insert(i, pl);break;}}}private void RmovePriority(Node node){foreach (var tmp in priorityList){if (tmp.node == node){priorityList.Remove(tmp);break;}}}#endregion2、优先级的计算private float CalPriority(Node node, Train target,int split){//计算目标点和分割点之间的距离，即优先级if (split == 0){return Math.Abs(target.positionX – node.point.positionX);}else if (split == 1){return Math.Abs(target.positionY – node.point.positionY);}elsereturn Math.Abs(target.positionZ – node.point.positionZ);}3、BBF算法private Node BBFFindNearest(Node tree, Train target){Node nearest = new Node();//最近邻节点nearest = tree;float priority = -1; //优先级//计算优先级priority = this.CalPriority(nearest, target,tree.split);this.InsertPriorityList(nearest, priority);//将根节点加入优先队列中Node topNode = null; //优先级最高的节点Node currentNode=null;double dist = 0;while (priorityList.Count > 0){topNode = priorityList[0].node; //优先队列中的第一个总是优先级最高的this.RmovePriority(topNode);while (topNode != null){//当前节点不是叶子节点if (topNode.leftNode != null || topNode.righNode != null){int split = topNode.split;if (split == 0){if (target.positionX <= topNode.point.positionX){//current = topNode.point;//若右节点不为空，将右子树节点添加到优先队列中if (topNode.righNode!=null){priority = this.CalPriority(topNode.righNode, target, split);this.InsertPriorityList(topNode.righNode, priority);}topNode = topNode.leftNode;}else{//current = topNode.point;//将左子树节点添加到优先级队列中if (topNode.leftNode!=null){priority = this.CalPriority(topNode.leftNode, target, split);this.InsertPriorityList(topNode.leftNode, priority);}topNode = topNode.righNode;}currentNode = topNode;}else if (split == 1){if (target.positionY <= topNode.point.positionY){//current = topNode.point;//将右子树节点添加到优先队列中if (topNode.righNode!=null){priority = this.CalPriority(topNode.righNode, target, split);this.InsertPriorityList(topNode.righNode, priority);}topNode = topNode.leftNode;}else{//current = topNode.point;//将左子树节点添加到优先级队列中if (topNode.leftNode!=null){priority = this.CalPriority(topNode.leftNode, target, split);this.InsertPriorityList(topNode.leftNode, priority);}topNode = topNode.righNode;}currentNode = topNode;}else{if (target.positionZ <= topNode.point.positionZ){//current = topNode.point;//将右子树节点添加到优先队列中if (topNode.righNode!=null){priority = this.CalPriority(topNode.righNode, target, split);this.InsertPriorityList(topNode.righNode, priority);}topNode = topNode.leftNode;}else{//current = topNode.point;//将左子树节点添加到优先级队列中if (topNode.leftNode!=null){priority = this.CalPriority(topNode.leftNode, target, split);this.InsertPriorityList(topNode.leftNode, priority);}topNode = topNode.righNode;}currentNode = topNode;}}else{currentNode = topNode;topNode = null;//叶子节点}if (currentNode!=null && Distance(nearest.point,target)>Distance(currentNode.point,target)){nearest = currentNode;dist = Distance(currentNode.point, target);}}}return nearest;}注：其中用的计算节点之间的距离函数Distance（）；这里计算的是欧几里德距离。private double Distance(Train trainFirst, Train trainSecond){double tmp = double.MaxValue;//初始化节点间距离为无穷大tmp = Math.Sqrt(Math.Pow(trainFirst.positionX – trainSecond.positionX, 2) +Math.Pow(trainFirst.positionY – trainSecond.positionY, 2) +Math.Pow(trainFirst.positionZ – trainSecond.positionZ, 2));return tmp;}BBF搜索算法结束。
暂时告一段落，虽然后面还有K近邻算法，那是在BBF的基础之上进行的改进，只需要在添加一个队列，主要存放的就是找到的临近点，在这个队列中，对找到的近邻节点进行排序，K近邻就是前K个节点。K近邻的实现参考文档中有实现，大家可以去研究一下即可，有时间我也会实现一下K近邻搜索的实现部分。
代码下载
比天才难得，许多天赋差的人经过过勤学苦练也取得了很大的成功。
