我想使用 BFS 实现搜索。该算法说我必须使用队列才能获得 FIFO 效果。 我读了克里斯·冈崎的Purely Functional Data Structures书并找到了如何创建队列(我使用 F# 编写):
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
(想要合并这两个代码)
最佳答案
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
希望这有帮助。
关于algorithm - F# 中的广度优先搜索 (BFS),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6061843/