Ordinamento topologico con funzione obiettivo

Question

Ho un DAG con N nodi, ovvero 1, 2, ..., N e ogni nodo ha un peso (possiamo chiamarlo ora) x_1, x_2, ..., x_N. Voglio fare uno smistamento topologico, ma la difficoltà è che ho una funzione obiettiva durante l'ordinamento. La mia funzione obiettivo è di ridurre al minimo il tempo totale tra diverse coppie di nodi.

Ad esempio, ho un DAG con 6 nodi, e voglio uno specifico ordinamento topologico tale che (1,3) + (2,4) è minimizzata, dove (A,B) indica il tempo tra due nodi A e B. Per esempio, se abbiamo una sorta [1, 6, 3, 2, 5, 4, 7], (1,3) = x_6 e (2,4) = x_5. Sulla base del DAG, voglio trovare un ordinamento che riduca al minimo lo (1,3) + (2,4).

Ho pensato questo problema per un po '. Generare tutti i tipi topologici possibili (riferimento link) e calcolare la funzione obiettivo uno per uno è sempre una soluzione possibile ma richiede troppo tempo se N è grande. Mi è stato anche suggerito di usare l'eliminazione ramificata quando si generano tutti i tipi possibili (non sono molto familiare, ma credo che non ridurrai drasticamente la complessità).

Qualsiasi algoritmo (ottimale o euristico) per questo tipo di problema? Sarebbe perfetto se l'algoritmo potesse essere applicato anche ad altre funzioni oggettive come minimizzare il tempo di avvio totale per alcuni nodi. Qualsiasi suggerimento è apprezzato.

PS: O in alternativa, è possibile formulare questo problema come un problema di ottimizzazione dei numeri interi?

Answer 1

Un modo per risolvere questo problema è la seguente:

In primo luogo abbiamo eseguito All-Pairs algoritmo percorso più breve Floyd-Warshall. Questo algoritmo può essere codificato in essentially 5 lines of code e viene eseguito nel tempo O(V^3). Genera i percorsi più brevi tra ciascuna coppia di vertici nel grafico, cioè genera come matrice la matrice V X V dei percorsi più brevi.

È semplice modificare questo algoritmo in modo da ottenere il conteggio dei vertici inclusi in ciascuno dei percorsi O(N^2). Quindi ora possiamo eliminare tutti i percorsi che hanno meno di N vertici. Per i percorsi rimanenti, li ordiniamo in base al loro costo e quindi testiamo ciascuno di essi per vedere se la proprietà di ordinamento topologico non viene violata. Se questa proprietà non viene violata, abbiamo trovato il nostro risultato desiderato.

L'ultimo passaggio sopra, cioè il test di ordinamento topologico può essere eseguito in O (V + E) per ciascuno dei percorsi O (V^2). Ciò produce il runtime peggiore di O(V^4). Tuttavia, in pratica, questo dovrebbe essere veloce perché Floyd-Warshall può essere reso molto amichevole con la cache e testeremo solo una piccola frazione di percorsi O (N^2) nella realtà. Inoltre, se il tuo DAG non è denso, potresti essere in grado di ottimizzare anche i test topologici con strutture dati adeguate.

Answer 2

Ecco un'idea:

Per semplicità, in primo luogo supporre che si dispone di una singola coppia di ottimizzare (io commentare il caso generale in seguito,) e supponiamo hai già il grafico topologically allineati in un array.

Prendere segmento matrice che inizia al minore (in termini di vostra topologico ordine) nodo della coppia, dire l, e termina al nodo superiore, dire h. Per ogni singolo nodo ordinato tra l e h, calcolare se è delimitato dal basso da l e/o delimitato dall'alto da h.È possibile calcolare la proprietà precedente contrassegnando i nodi in un BFS "ascendente" da l, tagliando ai nodi ordinati superiori a h; e allo stesso modo, quest'ultimo contrassegnando in un BFS "al ribasso" da h, tagliando ai nodi ordinati sotto l. La complessità di entrambi i passaggi sarà O (B * L), dove B è il fattore di diramazione e L è il numero di nodi originariamente ordinati tra l e h.

Ora, tutti i nodi non limitato superiormente da h possono essere spostati sopra h, e tutti i nodi che non sono delimitate dal basso da l possono essere spostati sotto l (i due insiemi possono sovrapporsi,) tutto senza violare la ordinamento topologico dell'array, a condizione che sia conservato l'ordine ordinato originale all'interno di ciascun gruppo di nodi trasferito verso l'alto o verso il basso.

Questa stessa procedura può essere applicata a tutte le coppie necessarie, a condizione che i segmenti che hanno tagliato dall'ordinamento originale non si sovrappongano.

Se due coppie si sovrappongono, diciamo (l1, h1) e (l2, h2), in modo che, ad es. l1 < l2 < h1 < h2 in originale ordinati ordine, sono disponibili le seguenti due casi:

1) Nel caso banale in cui h1 e l2 capita di essere correlato nell'ordine topologico, allora si dovrebbe essere in grado di ottimizzare le due coppie soprattutto indipendentemente l'uno dall'altro, applicando solo una certa cura per trasferire uno l2 sopra h1 o h1 sotto l2 (ma non esempio h1 sotto l1, se ciò risultano essere possibile.)

2) Se l2 < H1 nel topologica ordine , si possono trattare entrambe le coppie come la singola coppia (l1, h2), e poi eventualmente applicare la procedura più volta per (l2, h1).

Poiché non è chiaro quale sarà il processo completo nel caso di sovrapposizione non banale, specialmente se si hanno schemi di sovrapposizione più complessi, potrebbe risultare preferibile trattare tutte le coppie in modo uniforme, indipendentemente dalla sovrapposizione. In questo caso, l'ordine può essere processato ripetutamente mentre ogni corsa produce un miglioramento rispetto al precedente (non sono sicuro che la procedura sarà monotona in termini di funzione obiettivo, probabilmente no.)