贪婪最佳优先搜索¶
约 160 个字 预计阅读时间 1 分钟
贪婪最佳优先搜索，即 greedy best-first search，GBFS
- 优先扩展距离目标近的结点，即令 \(f(n) = h(n)\)
- 不排除环路的贪婪最佳优先搜索算法是不完备的
- 排除环路的贪婪最佳优先搜索是完备的，但不一定最优
- 最坏情况下的时间复杂度和空间复杂度均为 \(O(b^m)\)
- \(b\) 为分支因子（每个结点最大的分支数目）
- \(m\) 为最大深度，也就是搜索树中路径的最大可能长度
graph LR
A((A)) <--5--> B((B))
A <--3--> D((D))
A <--6--> E((E))
B <--5--> C((C))
D <--4--> F((F))
E <--3--> G((G))
E <--4--> H((H))
E <--7--> I((I))
F <--4--> G((G))
G <--3--> H((H))
G <--5--> K((K))
I <--5--> J((J))
H <--7--> J((J))
K <--6--> L((L))
J <--3--> K((K))
A->K
graph TB
A(((A))) ---> B((B = 10 ))
A ---> D((D = 12 ))
A ---> E(((E = 7 )))
E ---> G((G = 5))
E ---> H(((H = 3)))
E ---> I((I = 6))
H ---> J(((J = 3)))
H ---> L((G = 5))
J ---> K(((K = 0)))