Bu durumda dairesel referans kontrolü için iyi bir algoritma ne olurdu?

Question

Eğer aşağıdaki sınıf var Verilen (kötü C#, ama drift olsun):

public abstract class AmICircular 
{ 
    // assume Children is never null 
    private List<AmICircular> Children {get;set;} 

    // assume target is never null 
    public void Add(AmICircular target) 
    { 
    target.PerformCircularReferenceCheck(this); 
    Children.Add(target); 
    } 

    // throws when a circular reference is detected 
    protected abstract void PerformCircularReferenceCheck(AmICircular target); 
} 

nasıl PerformCircularReferenceCheck uygulamak? Ve hayır, bu ev ödevi değil.

naif uygulanması, imo, this geçen zaman, this ve tüm çocuklar üzerinde bir referans kontrol yapmak target tarihinde PerformCircularReferenceCheck çağırmak olacaktır. Ama ben daha iyi, kanıtlanmış etkili, bu yolu, this ve target için referanslar tüm çocuk ağacı daraltmak için bir yöntem eklemek ve daha sonra sonuçları (yığın üzerinde daha az basınç?), Veya Muhtemelen çeki tamamen List < T> dışında farklı bir (belki de kendi kendine kontrol!) koleksiyonu kullanarak kaçının!

Bunu nasıl yapardın?

düzenleme: Stefan belirttiği gibi, bu hedef yinelemeli solüsyonu (ulaşılabilir) ve CR bir dizi R (ulaşılabilir çocukları) tanımlamaktır

Answer 1

Kendi kendini referanslama (daha sonra tanımlanacak) nesneleri eklemediğiniz durumda, veri yapınız, yöneltilmiş bir asiklik grafiği (http://en.wikipedia.org/wiki/Directed_acyclic_graph) açıklar; burada IAmCircular sınıfının her örneği, bir dizi doğrudan halef düğümleri = Çocuklar.

Bu ana kadar olan önkoşul varsayarsak, herhangi bir döngü oluşturulmadı, istediğiniz işlev, PerformCircularReferenceCheck, "bu" seçeneğinin "hedef" konumundan ulaşılabilir olup olmadığını kontrol etmek için yeterlidir. Öyleyse, bir istisna döndürmelidir.

Karmaşıklık teorisi bilge, bu sorun ST-bağlanırlığı (http://en.wikipedia.org/wiki/St-connectivity) ve girdiyi asiklik grafiklerle (sizin durumunuz olan) kısıtladığınızda bile NL (http://en.wikipedia.org/wiki/NL_(complexity)) sınıfı için tamamlandı. Özellikle, Savitch teoremi (http://en.wikipedia.org/wiki/Savitch%27s_theorem), bir O (log^2 n) uzay algoritması oluşturmak için yapıcı bir yol sunar (o zaman O (n^2)), bunun için n, düğüm sayısıdır. Ayrıca, NL-complete olarak, O (log n) uzayında (yani düğümlere yalnızca sabit sayıda işaretçiyi kullanın) çalışan bir algoritmanın mevcut olması olası değildir, çünkü bu olasılıkla NL = L DÜZENLEME: Özellikle, birisinin önerdiği tavşan ve kaplumbağa algo küçük varyasyonları işe yaramaz (çünkü çok az yer kullanacaklar).

"Ardışık" dizisini "yinelemeli" olarak üreten ve bu kümede "bu" ifadesinin görünüp görünmediğini doğrulayan önemsiz O (n) zaman, O (n) uzay algoritmasını uygulamanızı öneririm.

Dikkatli olun, kümenin açık yapısı önemlidir. Aksi takdirde, "bu" bir "hedef" ardılı tarafından erişilip erişilemeyeceğini sadece yinelemeli olarak doğrularsanız, üstel zamanda koşma riskiyle karşı karşıya kalırsınız.

O (n) time/O (n) uzay algoritmasını tavsiye ederim çünkü zaman açısından en iyi şekilde en iyi şekilde yapabildiğiniz ve veri yapınız için O (n) alanını zaten kullanıyorsunuz.

Answer 2

ulaşılabilir olup olmadığını belirlemek için gereklidir.

ve CR = {this.children} ile başlayabilirsiniz.

Her adımda, CR'nin this (veya tam hedefinize bağlı olarak target) içerip içermediğini kontrol edersiniz. Aksi takdirde, CR'yi R'ye eklersiniz ve CR'yi CR'nin çocuklarına ayarlarsınız ve R öğelerini CR'den çıkarırsınız.

CR boşalırsa, R this'dan erişilebilen tüm öğeler kümesidir.