Algoritmo per determinare l'ordine di risoluzione della proprietà

1

Ho una lista di proprietà, che sono legate a qualche espressione di stringa:

property z, expression '[x] + [y]'
property x, expression '[y] + 1'
property y, expression '1'

Quindi per risolvere z, devo prima risolvere xey. La mia attuale approssimazione è questa:

var solved = new List<string>();
while (properties.Count() > 0) 
{
   var property = properties.Dequeue();
   var dependencies = FindDependencies(property)
         .Where(x => !solved.Contains(x))
         .ToList();

   // no unsolved dependencies, solve it
   if (dependencies.Count == 0) 
   {
       property.Solve();
       solved.Add(property.Name);
   } 
   // it can't be solved now, add to the end of queue
   else 
   {  
        properties.Enqueue();
   }
}

Questa approssimazione ha due problemi:

a) Penso che non sia ottimale, perché la proprietà non risolta viene aggiunta alla fine, potrebbe essere che potrebbe essere risolta prima e in tal caso le proprietà dipendenti non potrebbero essere posticipate anche.
b) Impossibile ottenere una buona condizione di uscita, quando è irrisolvibile (ovvero, c'è un riferimento circolare).

Qualcuno riconosce l'algoritmo già noto o ha idee su come ottimizzarlo?

    
posta Giedrius 25.09.2013 - 16:44
fonte

1 risposta

4

Le tue proprietà sono nodi in un grafico aciclico diretto (DAG), con le dipendenze come bordi. La ricerca di un ordinamento topologico ti fornirà l'ordine necessario per valutare le proprietà. Esistono altri algoritmi per rilevare i cicli per applicare la proprietà aciclica quando si aggiunge un nodo.

    
risposta data 25.09.2013 - 16:57
fonte

Leggi altre domande sui tag