F＃中的廣度優先搜索（BFS）

我想使用BFS執行搜索。該算法說我必須使用一個隊列來獲得FIFO效果。我讀克里斯·奧卡薩基的Purely Functional Data Structures書找到了如何做一個隊列（我寫使用F＃）：F＃中的廣度優先搜索（BFS）

type 'a queue = 'a list * 'a list 
let emtpy = [],[] 
let isEmpty = function 
    | [],_ -> true 
    | _ -> false 

let checkf = function 
    | [],r -> List.rev r,[] 
    | q -> q 

let snoc (f,r) x = checkf (f,x :: r) 

let head = function 
    | ([],_) -> failwith "EMPTY" 
    | (x::f,r) -> x 

let tail = function 
    | ([],_) -> failwith "EMPTY" 
    | (x::f,r) -> checkf (f,r)

人知道如何實現這BFS？

和我有這個代碼，以使一棵樹從列表：

let data = [4;3;8;7;10;1;9;6;5;0;2] 

type Tree<'a> = 
    | Node of Tree<'a> * 'a * Tree<'a> 
    | Leaf 

let rec insert tree element = 
    match element,tree with 
    | x,Leaf  -> Node(Leaf,x,Leaf) 
    | x,Node(l,y,r) when x <= y -> Node((insert l x),y,r) 
    | x,Node(l,y,r) when x > y -> Node(l,y,(insert r x)) 
    | _ -> Leaf 

let makeTree = List.fold insert Leaf data

（希望這兩個代碼結合）

來源

2011-05-19 Yabert Yanuar

BFS比隊列更多。您必須有一種方法來移動圖形，並跟蹤哪些節點已被訪問。我喜歡功能性數據結構，但是BFS可能更容易首先使用命令式代碼進行學習。 – 2011-05-19 17:17:35

BFS不是用於圖形還是Tree數據結構？ – Ankur 2011-05-20 04:27:53

的BFS算法是這樣的：

Initialise the search by placing the starting vertex in the queue. 
While the queue is not empty. 
    Remove the front vertex from the queue. 
    If this is a solution then we're finished -- report success. 
    Otherwise, compute the immediate children of this vertex and enqueue them. 
Otherwise we have exhausted the queue and found no solution -- report failure.

我F＃的語法有點搖擺不定，但這裏是我如何勾畫出解決方案：

bfs start = bfsLoop ([start], []) 

bfsLoop q0 = 
    if isEmpty q0 
    then failWith "No solution" 
    else v = head q0 
     if isSolution v 
     then v 
     else q1 = tail q0 
      vs = childrenOf v 
      q = foldl snoc vs q1 
      bfsLoop q

希望這有助於。

來源

2011-05-20 06:31:20 Rafe

F＃中的廣度優先搜索（BFS）

回答

相關問題