欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BEST FIRST SEARCH算法

程序员文章站 2022-05-22 20:56:49
...

**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。。。。**