[ALGORITMO] Calcolo percorso massimo grafo orientato aciclico a rami pesati

[Darksky]

Mi serve quanto in oggetto. Attingendo a dispense di ricerca operativa e project management ho trovato un algoritmo applicabile a strutture reticolari ma la mia situazione non soddisfa la condizione per cui il grafo deve avere un solo nodo sorgente ed uno solo finale.

Nella mia situazione ho un solo nodo finale ed N nodi sorgenti che non voglio definire a priori ma voglio far trovare all'algoritmo. Ogni nodo è una elaborazione che dura un tot di tempo. Il mio problema è trovare il cammino critico ovvero il tempo necessario per arrivare al nodo finale.

Avete qualche indizio da darmi per focalizzare meglio le mie ricerche ?

grazie

[Darksky]

mi correggo: i job sorgenti riesco ad identificarli già automaticamente, quindi non deve essere tale algoritmo a farlo.
Vorrei evitare però di creare un nodo sorgente fittizio.

[LeaderGL]

Lasciando stare la definizione di "nodo di partenza" e "nodo di arrivo", non sono ben riuscito a capire il tuo problema qual'è.

Dato un grado (orientato, aciclico e pesato) devi trovare il percorso a costo massimo da un nodo verso tutti gli altri?

[ramy89]

Essendo il grafo aciclico c'è un solo percorso che congiunge due nodi, quindi l' unico percorso che trovi tra due nodi è anche quello massimo.

[Darksky]

ramy89 forse stai facendo confusione.
E' vero che inm un grafo orientato due nodi collegati lo sono da un solo arco.

Ma qui parliamo di collegare un nodo sorgente ed uno finale, non adiacenti....e con archi pesati...oppure nodi pesati.

Cmq ho fatto un po' di ricerchine, si finisce in ricerca operativa e algoritmi comuni utilizzati nel project management.

La mia intuizione di inserire delle sorgenti ed eventualmente un pozzo fittizio per rientrare nelle ipotesi di partenza era corretta e cmq non se ne può fare a meno, sembra.

Quello che cercavo sembra essere il CPM Time analysis su una rete AON (activities on Nodes). Va bene il CPM perchè bene o male riesco a conoscere la durata delle singole attività sui nodi, altrimenti avrei dovuto optare per il PERT. Le risorse a disposizione si possono considerare illimitate. (si tratta di elaborazioni di una mega schedulazione che gira ogni giorno).
Fra l'altro riesco anche a trovare i tempi di slittamento per le attività non critiche e quindi se una elaborazione non critica si ferma, posso quantizzare quanto tempo si ha a disposizione per farla ripartire e terminare senza impattare sul tempo di fine megaelaborazione totale stimato.

[ramy89]

Originariamente inviato da Darksky
ramy89 forse stai facendo confusione.
E' vero che inm un grafo orientato due nodi collegati lo sono da un solo arco.
Ma qui parliamo di collegare un nodo sorgente ed uno finale, non adiacenti....e con archi pesati...oppure nodi pesati.

Appunto:

[...] c'è un solo percorso che congiunge due nodi [...]

Non ho detto che c'è un solo arco che congiunge due nodi, c'è un solo percorso, cioè un' unica sequenza finita di archi.
Se hai un nodo finale e N nodi sorgenti, ti basterà fare l' albero di copertura del grafo partendo dal nodo finale.

[Darksky]

Originariamente inviato da ramy89
Appunto:



Non ho detto che c'è un solo arco che congiunge due nodi, c'è un solo percorso, cioè un' unica sequenza finita di archi.
Se hai un nodo finale e N nodi sorgenti, ti basterà fare l' albero di copertura del grafo partendo dal nodo finale.

Forse stiamo parlando di 2 cose differenti.

tu hai scritto:

Essendo il grafo aciclico c'è un solo percorso che congiunge due nodi, quindi l' unico percorso che trovi tra due nodi è anche quello massimo.

Se ho una roba tipo questa:



posso arrivare dalla sorgente al pozzo con più percorsi, quindi non esiste l'unico percorso.
La discriminante, oltre che il numero di connessioni o step, è il peso che hai sugli archi o sui nodi ed è quella che ti fa scegliere un percorso fra i tanti disponibili.

[LeaderGL]

Ma il grafo rappresenta un diagramma di GANTT e gli archi sono le dipendenze tra i task?

[ramy89]

Ora ho capito, ti serve l' algoritmo di djikstra.Però l' algoritmo di djikstra serve per calcolare i cammini minimi, tu lo devi modificare in modo che invece dell' albero di copertura minimo ti dia quello massimo.

[staipa]

Ciao Darksky , è passato tantissimo da questa tua discussione, mi occupo anche io di schedulazione e di algoritmi per il cammino nelle schedulazioni. Ho il tuo stesso problema, alla fine come lo hai risolto?
Sei arrivato ad una buona soluzione?