更新時間:2022-04-26 來源:黑馬程序員 瀏覽量:
假設標記為星星的點是 test point， 綠色的點是找到的近似點，在回溯過程中，需要用到一個隊列，存儲需要回溯的點，在判斷其他子節點空間中是否有可能有距離查詢點更近的數據點時，做法是以查詢點為圓心，以當前的最近距離為半徑畫圓，這個圓稱為候選超球(candidate hypersphere)，如果圓與回溯點的軸相交，則需要將軸另一邊的節點都放到回溯隊列里面來。
樣本集{(2,3),(5,4), (9,6), (4,7), (8,1), (7,2)}。
查找點(2.1,3.1)
在(7,2)點測試到達(5,4)，在(5,4)點測試到達(2,3)，然后search_path中的結點為<(7,2),(5,4), (2,3)>，從search_path中取出(2,3)作為當前最佳結點nearest, dist為0.141;
然后回溯至(5,4)，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓，并不和超平面y=4相交，如上圖，所以不必跳到結點(5,4)的右子空間去搜索，因為右子空間中不可能有更近樣本點了。
于是再回溯至(7,2)，同理，以(2.1,3.1)為圓心，以dist=0.141為半徑畫一個圓并不和超平面x=7相交，所以也不用跳到結點(7,2)的右子空間去搜索。
至此，search_path為空，結束整個搜索，返回nearest(2,3)作為(2.1,3.1)的最近鄰點，最近距離為0.141。
