『壹』 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
獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。
概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由
器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路
由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條
新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的
向量距離與更新信息中的向量距離相加作為新路由的向量距離。