Problèmes avec un algorithme de dépendance simple
Dans ma webapp, nous avons beaucoup de champs qui résument d'autres champs, et ces champs résument plus de champs. Je sais que c'est un graphe dirigé acyclique.
Lorsque la page se charge, je calcule les valeurs pour tous les champs. Ce que j'essaie vraiment de faire est de convertir mon DAG en une liste unidimensionnelle qui contiendrait un ordre efficace pour calculer les champs.
Par exemple: A = B + D, D = B + C, B = C + E Ordre de calcul efficace: E - > C - > B - > D - > A
Maintenant mon algorithme ne fait que des insertions simples dans une liste itérativement, mais j'ai rencontré des situations où cela commence à se casser. Je pense que ce qui serait nécessaire à la place serait de travailler toutes les dépendances dans une structure arborescente, et à partir de là convertir cela dans la forme unidimensionnelle? Existe-t-il un algorithme simple pour convertir un tel arbre en un ordre efficace?
2 réponses
Cherchez-vous Type topologique? Cela impose un ordre (une séquence ou une liste) sur un DAG. Il est utilisé par, par exemple, des feuilles de calcul, pour déterminer les dépendances entre les cellules pour les calculs.
Ce que vous voulez, c'est une recherche approfondie.
function ExamineField(Field F)
{
if (F.already_in_list)
return
foreach C child of F
{
call ExamineField(C)
}
AddToList(F)
}
Ensuite, appelez ExamineField () sur chaque champ à tour de rôle, et la liste sera remplie dans un ordre optimal en fonction de vos spécifications.
Notez que si les champs sont cycliques (c'est-à-dire que vous avez quelque chose comme A = B + C, B = A + D), l'algorithme doit être modifié pour ne pas entrer dans une boucle sans fin.
Pour votre exemple, les appels iraient:
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)
Et la liste finirait par C, E, B, D, A.