Ordinamento di 'Attività' per l'esecuzione in base alle loro dipendenze

Question

Ordinamento di 'Attività' per l'esecuzione in base alle loro dipendenze

#1 da (2 voti)
#2 da (0 voti)

0

Diciamo che ho un insieme di Task che hanno dipendenze. Queste attività non sono in ordine, ma l'esecuzione delle attività dovrebbe essere nell'ordine corretto. Ogni attività ha due proprietà: Prima e Dopo.

Prima contiene un elenco di attività dipendenti dal risultato di questa attività, quindi dovrebbe essere eseguito prima di esse; Dopo contiene un elenco di attività che dipendono da queste attività specifiche. Quindi ci sono due modi per dire che B dipende dal risultato di A:

a) Aggiungi A alla B dopo l'elenco

b) Aggiungi B alla lista Befor di A

In entrambi i casi dovrebbe funzionare. Inoltre ci può essere gap tra le attività e dovrebbe essere compilato automaticamente al momento dell'esecuzione. Ad esempio, immaginiamo di avere i seguenti compiti:

Task1
  |____ Before: Task3, Task4
  |____ After: NA

Task4
  |____ Before: Task8
  |____ After: Task3

Task2
  |____ Before: NA
  |____ After: Task1

Task3
  |____ Before: Task5
  |____ After: Task2

Task5
  |____ Before: Task7
  |____ After: Task3

Quindi qui c'è un po 'di ambiguità su quale task dovrebbe essere eseguita prima: Task4 o Task5? Ma non è importante finché vengono eseguiti dopo Task3 e prima di Task7 e Task8. Questo dipende dall'algoritmo per metterli nel posto giusto.

L'unico modo che posso pensare di fare questo è di eseguire prima la scansione di tutte le attività e fondamentalmente registrare le dipendenze e quindi ricominciare ed eseguire ogni attività ora nel loro giusto ordine.

La complessità / efficienza dell'algoritmo non è molto importante in quanto ho meno di 500 task da ordinare prima di eseguirli, ma preferisco usare un algoritmo o un metodo ben noto per risolverlo, piuttosto mettere insieme le cose solo per ottenere fatto.

Aggiornamento: Il motivo principale per cui ho bisogno delle proprietà Before e After è la riduzione dell'errore umano durante la creazione delle attività. per esempio. È più semantico dire che CreateDirectory è Dopo LoadConfiguration e Prima CopyFiles . Ovviamente puoi dire che CopyFiles è dopo CreateDirectory e CreateDirectory dopo LoadConfiguration .

Ma alla fine tutti questi verranno convertiti solo nelle proprietà Dopo .

algorithms scheduling queue

posta Mahdi 21.04.2016 - 16:31

fonte

2 risposte

Leggi altre domande sui tag algorithms scheduling queue

Differenza fondamentale tra una classe statica e funzioni con nomi assegnati Quando devono essere elaborati diagrammi delle classi, diagrammi di flusso dei dati e diagrammi di flusso?

score 2 · Answer 1

Hai un grafico Aciclico indiretto e devi operare un Ordinamento topologico per ordinare il tuo grafico.

I dettagli dell'implementazione dipendono dal linguaggio di programmazione e dalla piattaforma su cui stai lavorando, quindi spetta a te trovare una libreria di grafi e così via da utilizzare nella tua applicazione.

In alternativa Tsort può essere utile anche.

score 0 · Answer 2

Al di là della risposta precisa di @ 53777A, la tua prima e amp; dopo che l'informazione è "interessante". Non hai bisogno di informazioni sia prima che dopo, quindi mi chiedo perché ti preoccupi di catturarle entrambe.

Quando disponiamo di informazioni sia prima che dopo, in forma canonica, le informazioni appaiono simmetriche, ovvero se Task1 deve essere prima di Task3, Task3 dovrebbe essere dopo Task1 e così via, che non è il caso nel tuo campione di dati.

Puoi facilmente ottenere tale prima e amp; dopo la forma canonica da quello che hai o da un elenco di dipendenze after-only o before-only, da un semplice attraversamento in cui ti assicuri che il link inverso simmetrico sia presente.

Tuttavia, usando solo dopo le informazioni (anche se rese canoniche se si parte dal tuo non canonico prima e dopo l'acquisizione), puoi semplicemente eseguire qualsiasi attività che sia pronta (tutte le sue dopo sono già state eseguite). Devi solo essere in grado di dire quali sono stati eseguiti finora.

A proposito, questo è esattamente un tipo topologico, è solo che lo stai facendo al volo invece che in anticipo. Se li numeri mentre li visiti invece di eseguirli, allora hai creato l'ordinamento e se li inserisci in un elenco mentre li visiti, hai creato un elenco ordinato topologicamente.

Sono sicuro che ci sono modi più efficaci per identificare ciò che può essere eseguibile in qualsiasi momento, il che sarebbe utile per i set di dati estremi più grandi, ma in un caso più semplice, puoi semplicemente scansionare l'elenco per qualsiasi oggetto non ancora eseguito / visitato i cui after hanno tutti eseguito / visitato. È possibile utilizzare due elenchi anziché o in aggiunta allo stato booleano per eseguito / visitato.

Se trovi che ci sono ancora elementi che non sono visitati e non puoi identificarne uno da eseguire successivamente, allora hai un ciclo, che rappresenta un errore nell'input. Questo non è improbabile se gli umani stanno mantenendo il precedente e & dopo le informazioni per queste 500 attività, è possibile utilizzare l'ordinamento per trovare questi errori prima di eseguire l'esecuzione.