간단한 의존성 알고리즘의 문제

Question

webapp에는 다른 필드의 합계가 많은 필드가 있으며 그 필드는 더 많은 필드를 합산합니다. 이것이 비순환 식 그래프라는 것을 압니다.

페이지가로드되면 모든 필드의 값이 계산됩니다. 내가 실제로하려고하는 것은 필드를 계산할 효율적인 순서가 포함 된 1 차원 목록으로 DAG를 변환하는 것입니다.

예 : A = B + D, D = B + C , B = C + E 효율적 계산 순서 : E -> C -> B -> D -> A

현재 알고리즘은 목록에 반복적으로 간단한 삽입을 수행하지만, 그것은 부서지기 시작합니다. 대신 트리 구조로 모든 종속성을 해결하는 것이 무엇이 필요한지 생각하고 거기에서 그것을 일차원 형식으로 변환합니까? 이러한 트리를 효율적인 순서로 변환하는 간단한 알고리즘이 있습니까?

Answer 1

topological sort을 찾고 계십니까? 이것은 DAG에 순서 (목록 또는 목록)를 부과합니다. 예를 들어 스프레드 시트에서 계산을 위해 셀 간의 종속성을 파악하는 데 사용됩니다.

Answer 2

원하는 것은 깊이 우선 검색입니다.

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

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

    AddToList(F) 
} 

은 그럼 그냥 차례로 각 필드에 ExamineField()를 호출하고, 목록은 사양에 따라 최적의 순서에 채워집니다.

필드가주기 인 경우 (즉, A = B + C, B = A + D와 같은 항목이있는 경우) 무한 루프가되지 않도록 알고리즘을 수정해야합니다 .

귀하의 예를 들어

, 통화가 갈 것 :

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) 

을 그리고 목록