Basit bir bağımlılık algoritması ile ilgili sorunlar

Question

Web sunucumda, diğer alanları özetleyen birçok alanımız var ve bu alanlar daha fazla alan toplar. Bunun bir yönlendirilmiş asiklik grafik olduğunu biliyorum.

Sayfa yüklendiğinde, tüm alanların değerlerini hesaplıyorum. Yapmaya çalıştığım şey, DAG'ımı alanların hesaplanması için verimli bir sıra içeren tek boyutlu bir listeye dönüştürmektir.

Örneğin: A = B + D, D = B + C , B = C + E Verimli hesaplama sırası: E -> C -> B -> D -> A

Şu anda benim algoritmam bir listeye basitçe ekleme yapıyor, ancak bazı durumlarda bu kırmaya başlar. Bunun yerine, ihtiyaç duyulan şeylerin tüm bağımlılıkları bir ağaç yapısına dönüştürmek olduğunu ve oradan tek boyutlu forma dönüştürdüğünü düşünüyorum. Böyle bir ağacı verimli bir sıraya dönüştürmek için basit bir algoritma var mı?

Answer 1

topological sort mi arıyorsunuz? Bu, bir DAG üzerinde bir sıralamayı (bir sıra veya liste) empoze eder. Hesaplamalar için hücreler arasındaki bağımlılıkları belirlemek için, örneğin, elektronik tablolar tarafından kullanılır.

Answer 2

İstediğiniz, derinlemesine ilk aramadır.

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
} 

Sonra sadece sırayla her alanda ExamineField() arama ve listesi spec göre optimal sıralamada doldurulur.

alanları döngüsel ise (yani, A = B + C, B = A + D gibi bir şeyiniz varsa), algoritmanın, sonsuz bir döngüye girmeyecek şekilde değiştirilmesi gerektiğini unutmayın. .

senin Örneğin

, aramalar devam ediyorum:

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens) 

Ve liste