Programmazione lineare, cammino minimo
Salve
In questo periodo mi sto dedicando a imparare un po' la programmazione lineare, però sono due settimane che sono bloccato su questo problema.
Dato un grafo con gli archi pesati, trovare il cammino minimo tra due nodi s e t. Il testo mi consiglia di costuire la soluzione usando l algoritmo di Dijkstra per il cammino minimo, ma non riesco a capire come devo procedere.
Qualcuno mi sa aiutare?
Mi scuso in anticipo se non è la sezione giusta. In caso non lo sia fatemelo notare e elimino la domanda.
In questo periodo mi sto dedicando a imparare un po' la programmazione lineare, però sono due settimane che sono bloccato su questo problema.
Dato un grafo con gli archi pesati, trovare il cammino minimo tra due nodi s e t. Il testo mi consiglia di costuire la soluzione usando l algoritmo di Dijkstra per il cammino minimo, ma non riesco a capire come devo procedere.
Qualcuno mi sa aiutare?
Mi scuso in anticipo se non è la sezione giusta. In caso non lo sia fatemelo notare e elimino la domanda.
Risposte
Da quello che ho capito dovresti scrivere il duale e poi applicare l'algoritmo di Dijkstra che trova la soluzione per entrambi i problemi. Applicare l'algoritmo di Dijkstra è molto banale (se non lo hai mai applicato trova in rete degli esercizi che lo spiegano svolto), non dovresti avere particolari problemi. Sinceramente, dato che non ti chiede la dimostrazione che risolvere il primale risolve anche il duale, trovo l'esercizio un po' inutile. Secondo me potresti benissimo scriverti il semplice duale, inventarti un grafo (piccolo) e applicarci Dijkstra. In questo modo ti rendi conto se lo applichi correttamente.
PS: Per la spiegazione dell'algoritmo di Dijkstra vedi wikipedia. Se stai usando un testo in inglese e magari non hai ben chiaro il discorso primale-duale per il problema del cammino minimo dai una occhiata a questa dispensa, mi sembra molto ben fatta.
Buono studio...
PS: Per la spiegazione dell'algoritmo di Dijkstra vedi wikipedia. Se stai usando un testo in inglese e magari non hai ben chiaro il discorso primale-duale per il problema del cammino minimo dai una occhiata a questa dispensa, mi sembra molto ben fatta.
Buono studio...
Grazie mille per la dispensa!! Effetivamente sono un po' carente in alcuni argomenti della ricerca operativa.
Io mi sa che a questo punto provo a dimostrare anche che la soluzione del duale va bene per quella del primale.
Leggendo molti pdf su internet, ho trovato il discorso del problema primale ristretto che viene usato per trovare una soluzione ottima al primale originario. Non ho capito molto bene come applicare questa procedura, ma secondo te può essere una buona tecnica?
Io mi sa che a questo punto provo a dimostrare anche che la soluzione del duale va bene per quella del primale.
Leggendo molti pdf su internet, ho trovato il discorso del problema primale ristretto che viene usato per trovare una soluzione ottima al primale originario. Non ho capito molto bene come applicare questa procedura, ma secondo te può essere una buona tecnica?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo