BEST FIRST SEARCH算法
**BEST FIRST SEARCH算法**
Korf illustrated the workings of this algorithm with a binary tree where f(N) = the depth of node N. What follows is a brief, structured description of how the algorithm works in this case. It is best to try to work the algorithm on your own on paper and use this as a reference to check your work. Nodes in the binary tree are named A, B, C, … from left-to-right, top-to-bottom. Assume the tree is infinite and has no goal. Note that the stored value F(N) is different from f(N). When sorted children are listed (e.g. “B(1) C(1)”), the number inside the parentheses is the stored value. Recursive calls are indented; the first line is the initial call on the root.
代码块:
RBFS (node: N, value: F(N), bound: B)
IF f(N)>B, RETURN f(N)
IF N is a goal, EXIT algorithm
IF N has no children, RETURN infinity
FOR each child Ni of N,
IF f(N)<F(N), F[i] := MAX(F(N),f(Ni))
ELSE F[i] := f(Ni)
sort Ni and F[i] in increasing order of F[i]
IF only one child, F[2] := infinity
WHILE (F[1] <= B and F[1] < infinity)
F[1] := RBFS(N1, F[1], MIN(B, F[2]))
insert Ni and F[1] in sorted order
RETURN F[1]
## 分割线
RBFS(A, 0, 4)
f(A)=F(A), so F(B)=f(B)=1, F(C)=f(C)=1
Sorted children: B(1) C(1)
F(B)< 4, so
RBFS(B, 1, 1)
f(B)=F(B), so F(D)=f(D)=2, F(E)=f(E)=2
Sorted children: D(2) E(2)
F(D)>1, so return 2
F(B)=2
Sorted children: C(1) B(2)
F(C)< 4, so
RBFS(C, 1, 2)
f(C)=F(C), so F(F)=f(F)=2, F(G)=f(G)=2
Sorted children: F(2) G(2)
F(F)<=2, so
RBFS(F, 2, 2)
… search F’s children to 2 returning min cost beyond …
return 3
F(F)=3
Sorted children: G(2) F(3)
F(G)<=2, so
RBFS(G, 2, 2)
… search G’s children to 2 returning min cost beyond …
return 3
F(G)=3
Sorted children: F(3) G(3)
F(F)>2, so return 3
F(C)=3
Sorted children: B(2) C(3)
F(B)< 4, so
RBFS(B, 2, 3)
f(B)<F(B), so F(D)=MAX(F(B),f(D))=2,
F(E)=MAX(F(B),f(E))=2
Sorted children: D(2) E(2)
F(D)<=3, so
RBFS(D, 2, 2)
… search D’s children to 2 returning min cost beyond …
return 3
F(D)=3
Sorted children: E(2) D(3)
F(E)<=3, so
RBFS(E, 2, 3)
… search E’s children to 3 returning min cost beyond …
return 4
F(E)=4
Sorted children: D(3) E(4)
F(D)<=3, so
RBFS(D, 3, 3)
… search D’s children to 3 returning min cost beyond …
return 4
F(D)=4
Sorted children: E(4) D(4)
F(E)>3, so return 4
F(B)=4
Sorted children: C(3) B(4)
F(C)< 4, so
RBFS(C, 3, 4)
… search C’s children to 4 returning min cost beyond …
return 5
F(C)=5
Sorted children: B(4) C(5)
F(B)< 4, so
RBFS(B, 4, 5)
… search B’s children to 5 returning min cost beyond …
return 6
F(B)=6
Sorted children: C(5) B(6)
**and so on。。。。**
上一篇: springboot的gradle项目转换成maven项目
下一篇: 深度优先搜索(depth first search(dfs)) 和 广度/宽度优先搜索(breath first search(bfs))
推荐阅读
-
查找算法(1)--Sequential search--顺序查找
-
查找算法(1)--Sequential search--顺序查找
-
选择性搜索 Selective Search -- 算法详解+源码分析
-
选择性搜索算法(Select search, SS) 算法详解
-
PHP实现广度优先搜索算法(BFS,Broad First Search)详解
-
PHP实现深度优先搜索算法(DFS,Depth First Search)详解
-
广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search,BFS)
-
HDU 6338 2018HDU多校赛 第四场 Depth-First Search(组合数学+平衡树/pbds)
-
【氦图笔试和面试的笔试题】两个算法题1.双栈仿队列 .2布尔搜索(Boolean search is powerful in sourcing and recruiting.)
-
深度优先搜索 DFS(Depath First Search, DFS)