樹搜尋算法是計算機里的初始化算法。
基本介紹
- 中文名：樹搜尋算法
- 相關學科：計算機
- 實質：算法
- 1°：初始化
1° （初始化）
置B = ∞，L = 0（當前水平）， p = 0（當前結點）。
2° （當前結點展開）
把當前結點的直接子結點放入（當前水平的）一個目錄表（活動表）中，
對它們計算並存儲D（x,M）。
（注意：活動表在每個水平上一個，下文均指當前水平的活動表）
3° （檢驗）
對活動表中每個結點，若D(x,M) ＞ B + r，則從表中去掉。（規則1）
4° （回溯）
若活動表中已無結點，則回到上一級，置L=L−1 。
如L==0，則算法終止；
如L≠ 0，則轉3°；
若活動表中有結點，則繼續5°。
5° （選擇最近結點）
在目錄表中選擇最近結點（D(x,M) 最小），記為p′ ，以它為當前結點，若當前水平L 為最終水平，則轉6°。
否則，置L = L +1，轉2°。
6° （檢驗）
對當前結點p′ 中的每個 x[i] ，
若D(x,M) ＞ D(x[i],M)+B，則非最近鄰； （規則2）
否則，計算D(x,x[i])，
若D(x,x[i]) ＜B ，則置NN = i，B = D(x,x[i])
p′ 中所有i x 被檢驗過之後，轉3°。
算法終止時，輸出x 的最近鄰x[NN] 和D(x,x[NN])=B。
