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

[Darksky]

Ho scoperto che c'era un plugin dello schedulatore che faceva già tutto lui.
Onestamente è passato tanto tempo e non ricordo più a cosa ero arrivato per conto mio.

[staipa]

"Critical Path" immagino

[vince001]

Se devi trovare il percorso a costo minimo da un nodo A ad un Nodo B ti basta implementare l'algoritmo di Dijkstra, ti basta una matrice dei costi e due vettori; il primo indica il costo minimo per arrivare a quel nodo (Inizialmente sono tutti infinito) e l'altro il nodo precedente da cui si proviene a costo minimo. Per ogni nodo di esamini gli archi e se migliorano il costo aggiorni i due vettori sopra citati e richiami ricorsivamente la funzione considerando il nodo a vai a finire prendendo l'arco in considerazione. Un'altra versione la puoi realizzare tramite una priority queue

[staipa]

Sarebbe una bellissima risposta se il thread fosse "Calcolo percorso minimo in un grafo a rami pesati" ma purtroppo è "Calcolo percorso massimo grafo orientato aciclico a rami pesati"

[vince001]

Non puoi a provare la logica e considerare il prezzo massimo invece del minimo? Potrebbe essere uno spunto di partenza,
Altrimenti penso che potresti costruire un maximum spanning tree

[M.A.W. 1968]

Personalmente mi sono occupato approfonditamente per un certo periodo di tematiche di scheduling, all'inizio della mia carriera, grazie al mio background in vari campi dell'ottimizzazione. I progressi nel settore (sono trascorsi circa vent'anni) risultano scarsi o nulli dal punto di vista algoritmico, e sono legati sostanzialmente al massiccio aumento di capacità elaborativa ed allo sviluppo di euristiche e verticalizzazioni. Infatti il problema del percorso massimo è NP-hard nel caso generale, e risulta totalmente diverso dalla ricerca del percorso minimo, quindi non v'è molto da divagare in merito.

Il grafo orientato aciclico pesato (W-DAG) è un caso particolarissimo per il quale esiste una soluzione in tempo lineare al problema della ricerca di un percorso massimo, basata sostanzialmente sul riordino topologico del grafo stesso. Tale algoritmo, implementato da sempre in software di scheduling giustamente famosi (vedi NICIM e derivati) così come in motori di constraint solving dedicati (vedi Ilog/CPLEX, Chip, Eclipse...), viene generalmente denominato Critical Path Method o CPM, come peraltro qualcuno ha già telegraficamente suggerito nel thread. Questo è il massimo offerto dall'attuale conoscenza algoritmica in materia, a meno di qualche euristica e delle solite tecniche generali di ottimizzazione, che comunque sono altro argomento.

L'idea è che, allo stato attuale e salvo casi ancora più particolari, oltre il CPM c'è sostanzialmente il nulla, e certo non esistono alternative più o meno fantasiose che non siano prestazionalmente disastrose. Il tutto, peraltro, si trova ampissimamente squadernato anche nel più sintetico dei testi di logistica e organizzazione della produzione, operations research, et similia.