‘壹’ KNN算法-4-算法优化-KD树
KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作时，可以使用kd树对查询操作进行优化。
Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想象一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：
首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。
常规的k-d tree的构建过程为：
对于构建过程，有两个优化点：
例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：
如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。
如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：
kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。
如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。
首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。
以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。
接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。
以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。
遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。
举例：查询点（2.1,3.1）
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。
举例：查询点（2，4.5）
一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：
上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。
一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：
但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：
研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。
同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。
Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。
‘贰’ 怎样才能快速搜索路由表有哪些着名的搜索算法
有三个路由器，a，b和c。路由器a的两个网络接口f0和s0
分别连接在
10.1.0.0和10.2.0.0网段上；路由器b的两个网络接口s0和s1
分别连接在
10.2.0.0和10.3.0.0网段上；路由器c的两个网络接口s0和e0
分别连接在
10.3.0.0和10.4.0.0网段上；
如上图中各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网
络的网络连接，其向量距离设置为0。这即是最初的路由表。
当路由器b和a以及b和c之间相互交换路由信息后，它们会更新各自的路由表。
例如，路由器b通过网络端口s1收到路由器c的路由信息（10.3.0.0,s0,0）和(10.4.0.0,e0,0)后，在自己的路由表中增加一条(10.4.0.0,s1,1)路由信息。该信息表示：通过路由器b的网络接
口s1可以访问到10.4.0.0网段，其向量距离为1,该向量距离是在路由器c的基础上加1获得的。
同样道理，路由器b还会产生一条(10.1.0.0,s0,1)路由，这条路由是通过网络端口s0从路由器a
获得的。如此反复，直到最终收敛，形成图中所示的路由表。
概括地说，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其它路由
器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路
由器从它的相邻处收到更新信息时，它会将更新信息与本身的路由表相比较。如果该路由器比较出一条
新路由或是找到一条比当前路由更好的路由时，它会对路由表进行更新：将从该路由器到邻居之间的
向量距离与更新信息中的向量距离相加作为新路由的向量距离。