Kd缺陷K近邻

Question

免责声明:下面的代码中有一些不好的做法

你好，我只是有几个问题，如何正确格式化我的KD树K最近的邻居搜索。这里是我的函数的一个例子。

void nearest_neighbor(Node *T, int K) {
  if (T == NULL) return;
  nearest_neighbor(T->left, K); 
  //do stuff find dist etc
  if(?)nearest_neighbor(T->right, K);  
 }

这段代码很混乱，所以我会尝试解释它。我的函数只取k值和一个节点T。我要做的是找出当前节点与结构中所有其他值之间的距离。所有这些都很有效，我的问题是理解何时以及如何调用递归调用nearest_neighbor(T->左/T->右，K) --我知道我应该把调用修剪到右边，但我不知道如何做到这一点。顺便说一下，这是一棵多维KD树。对更好的例子提供任何指导将是非常感谢的。

Answer 1

我建议你像维基百科说的那样实现，对于你的具体问题，这里：

从根节点开始，算法递归地向下移动，就像插入搜索点时一样(即，它向左或向右移动，取决于该点在拆分维度中是否小于或大于当前节点)。

回答问题。当然，您可以将此图像记在心上：

​

​

如果你有更多的两个维度，比如在这个例子中，你只是在第一个维度中分裂，然后在第二个，第三个，然后第四个等等，然后你遵循一个循环策略，所以当你到达最后一个维度时，你再次从第一个维度开始。

Answer 2

一般的想法是保持全局点离目标最近，用新发现的点进行更新，永远不要降到不可能包含比目标最近的点更近的n个顶点中。我将用C而不是C++展示它。您可以轻松地转换为面向对象的形式。

#define N_DIM <k for the k-D tree>

typedef float COORD; 

typedef struct point_s {
  COORD x[N_DIM];
} POINT;

typedef struct node_s {
  struct node_s *lft, *rgt;
  POINT p[1];
} NODE;

POINT target[1];    // target for nearest search
POINT nearest[1];   // nearest found so far
POINT b0[1], b1[1]; // search bounding box

bool prune_search() {
  // Return true if no point in the bounding box [b0..b1] is closer
  // to the target than than the current value of nearest.
}

void search(NODE *node, int dim);

void search_lft(NODE *node, int dim) {
  if (!node->lft) return;
  COORD save = b1->p->x[dim];
  b1->p->x[dim] = node->p->x[dim];
  if (!prune_search()) search(node->lft, (dim + 1) % N_DIM);
  b1->p->x[dim] = save; 
}

void search_rgt(NODE *node, int dim) {
  if (!node->rgt) return;
  COORD save = b0->p->x[dim];
  b0->p->x[dim] = node->p->x[dim];
  if (!prune_search()) search(node->rgt, (dim + 1) % N_DIM);
  b0->p->x[dim] = save; 
}

void search(NODE *node, int dim) {
  if (dist(node->p, target) < dist(nearest, target)) *nearest = *node->p;
  if (target->p->x[dim] < node->p->x[dim]) {
    search_lft(node, dim);
    search_rgt(node, dim);
  } else {
    search_rgt(node, dim);
    search_lft(node, dim);
  }
}

/** Set *nst to the point in the given kd-tree nearest to tgt. */
void get_nearest(POINT *nst, POINT *tgt, NODE *root) {     
  *b0 = POINT_AT_NEGATIVE_INFINITY;
  *b1 = POINT_AT_POSITIVE_INFINITY;
  *target = *tgt;
  *nearest = *root->p;
  search(root, 0);
  *nst = *nearest;
}

注意，这不是最经济的实现。为了简单起见，它做了一些不必要的最近的更新和剪枝比较。但其渐近性能与kd-树神经网络的期望一致.在完成这个操作之后，您可以使用它作为一个基本实现来挤出额外的比较。