Поиск в ширину в F # (BFS) - PullRequest
Новая
       4

Поиск в ширину в F # (BFS)

1 голос
/ 19 мая 2011

Я хочу реализовать поиск, используя BFS .Алгоритм говорит, что я должен использовать очередь, чтобы получить эффект FIFO.Я прочитал книгу Чисто-функциональные структуры данных Криса Окасаки и нашел, как создать очередь (я написал, используя 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

(хочу объединить эти два кода)

1 Ответ

3 голосов
/ 20 мая 2011

алгоритм 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

Надеюсь, это поможет.

...