OCAML Depth-First Search

Question

Ho fatto un tutorial in OCaml (non chiedermi perché, ho appena deciso di espandere la mia conoscenza delle lingue, credo) e sono arrivato al punto in cui sono lavorare con i grafici. Il tutorial mi ha insegnato come eseguire una ricerca in ampiezza su un grafico, che posso implementare correttamente. Tuttavia, ho lottato con un algoritmo per una ricerca approfondita, che è una di quelle cose in cui il tutorial va, "Ti suggeriamo di provare questo metodo in profondità, ma non ti diremo come fallo."

Sto cercando di implementarlo in questo modo: let rec dfs graph start end. Vale a dire, ho cercato di farlo in un elenco di spigoli(), un nodo iniziale (start) e un nodo finale (end).

ho creato il mio grafico utilizzando un elenco di bordi ...

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

Tuttavia, io sono totalmente perso su dove andare da qui. Qualche consiglio su come farmi andare? Grazie.

Answer 1

Così, l'ho fatto ma trovo strano che tu rappresenti un grafico come una lista se devi cercare in esso. Una mappa sarebbe molto meglio. In ogni caso, ecco come è fatto:

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

let successors n e = 
    List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e) 

let dfs graph start f = 
    let rec rdfs visited node = 
    if not (List.mem node visited) then 
     begin 
     f node; 
     let s = successors node graph in 
     List.fold_left rdfs (node::visited) s 
     end 
    else visited 
    in rdfs [] start 

let() = let _ = dfs edges "a" print_string in() 

prima cosa, definire un successors funzioni che vi darà ogni diretto successore di un nodo (la parte List.filter i bordi ottiene, la parte List.map dividere i bordi risultanti in due parti e mantieni solo il secondo (il primo è naturalmente il nodo per il quale stai cercando i successori)

La funzione dfs definisce una funzione interna che fa due cose, controllando se il nodo su cui stiamo lavorando era già visitato oppure no

• Se sì, non cambia nulla, restituiamo solo la stessa lista di nodi visitati (e forse alcune altre cose a seconda di cosa vuoi fare con la tua ricerca).

• Se no, allora

  • Noi applichiamo la funzione che abbiamo dato al dfs al nodo corrente,
  • Aggiungiamo questo nodo per i nodi visitati,
  • Prendiamo i suoi successori,

  • Applichiamo la funzione a ciascuno di essi, (qui, c'è un piccolo trucco, dal momento che abbiamo

    List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

    e

    rdfs : string list -> string -> string list

    invece di scrivere

    List.fold_left (fun visited node -> rdfs visited node) ...

    possiamo scrivere

    List.fold_left rdfs ...

    (qualcosa a che fare con questa strana cosa chiamata Lambda Calcolo e un po 'regola denominata eta conversione cui si afferma che:

    λ x · ux η u (x ∉ fv(u)) (fv(u) essendo le variabili libere di u) :-p) (che cosa significa se che in OCaml, se si scrive fun x -> f x si potrebbe avere scrittura f invece, è rigorosamente equivalenti.)

  • torniamo alla lista nodi visitato in cui sono stati aggiunti tutti i nodi visitati

H Ho aiutato.