OCAML Derinlik-İlk Arama

Question

OCaml'da bir eğitim yapıyorum (bana neden sorma, sadece dil bilgimi genişletmeye karar verdim, sanırım) ve ben nerede olduğumu anladım. grafiklerle çalışmak. Öğretici bana, iyi bir şekilde uygulayabileceğim bir grafikte nasıl geniş kapsamlı bir ilk arama yapmam gerektiğini öğretti. Ancak, derinlemesine ilk arama için bir algoritma ile uğraşıyorum, bu da öğreticinin gittiği şeylerden biri, "Bunu ilk önce derin bir yöntemle denemenizi öneririz, ancak size nasıl yap."

Bunu şu şekilde uygulamaya çalışıyorum: let rec dfs graph start end. Diğer bir deyişle, bir kenarlar(), bir başlangıç ​​düğümü (start) ve bir bitiş düğümü (end) listesinde yaptığım yerde yapmaya çalışıyorum.

Ben kenar listesinin kullanarak Grafiğimi oluşturduk ... Ancak

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

, ben tamamen buradan nereye hakkında kayboldum. Beni nasıl süreceğine dair bir tavsiye var mı? Teşekkürler.

Answer 1

Öyleyse yaptım ama eğer aramak zorunda iseniz, bir grafiği bir liste olarak göstermeniz garip gelebilir. Bir harita çok daha iyi olurdu. Neyse, işte işler böyle yürüyor:

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() 

ilk şey, size bir düğümün her direkt halefi verecek bir successors işlevlerini define (List.filter bölüm List.map bölüm iki kısımdan sonuçlanan kenarları bölmek, teşekkür kenarları alır ve yalnızca ikincisini koruyun (birincisi, ardılları aradığınız düğümdür).

dfs işlevi, üzerinde çalıştığımız düğümün zaten ziyaret edilip edilmediğini kontrol eden iki işlevi olan bir iç işlevi tanımlar. veya değil

• Evet, hiçbir şey değişmezse, yalnızca ziyaret edilen düğümlerin aynı listesini (ve belki de aramanızla ne yapmak istediğinize bağlı olarak başka şeyler) geri göndeririz.
• Biz ziyaret düğümlere bu düğüm eklemek sonra

• Hayır ise, biz şimdiki düğüme dfs verdi fonksiyonunu uygulamak

  • , Biz onun halefleri almak
  • ,

  • Her biri için işlevi uygularız, (burada, küçük bir hile var, çünkü biz

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

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

    yazma

    ve

    rdfs : string list -> string -> string list

    yerine

    biz Lambda Matematik ve bazı denen bu tuhaf şeyle yapmak

    List.fold_left rdfs ...

    (bir şey yazabilir

    λ x · ux η u (x ∉ fv(u)) Eğer fun x -> f x yazarsanız o OCaml içinde, bunun yerine yazma f olabilir eğer ne anlama geldiğini :-p) ((fv(u) u serbest değişkenler olmak üzere), öyle: belirtiyor kuralı denilen eta dönüşüm kesinlikle eşdeğer.)

  Hepimiz ziyaret düğümler ilave edildiği ziyaret düğümler listesini döndürür

H Ben yardımcı oldum.