Lotplace

本人於該blog的全部文章轉移至[Algorithm] Best-First Search – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

不同於BFS、DFS以廣度或深度進行搜尋，best-first search則是以路徑的權重優先做搜尋

pseudocode:
    建立一個Pirority queue = pq
  將起點放入pq
    while(pq不為空)
      從pq取出一個節點node並從pq刪除該節點
      if(node是終點)
        結束迴圈
      else
        for 每個node的相鄰節點
          if(相鄰節點未走訪)
            將相鄰節點讓入pq
            相鄰節點設為已走訪
範例:
以文首的圖做舉例
start = A,goal = H,pq{A}
1.node = A pq{}  =>  pq{BCD}
2.node = B pq{CD}  =>  pq{CED}
3.node = C pq{ED}  =>  pq{EDF}
4.node = E pq{DF}  =>  pq{DFG}
5.node = D pq{FG}  =>  pq{FG}
6.node = F pq{G}  => pq{HG}
7.node = H pq{G}  => goal was found

Source code:Ghosts381937/Best-First-Search (github.com)

---

Filed under: 演算法 - @ 2021 年 7 月 22 日 上午 10:38

標籤: algo