Kruskal, Prim o Dijkstra?
Ciao.
Dovrei risolvere quest'esercizio, ma non sono sicuro come. Qualcosa mi dice che dovrei utilizzare i grafi per ottenere l'albero ricoprente a costo minimo, ma non lo so. Cosa mi consigliate?
L’Ente Nazionale Parchi sta pianificando lo sviluppo di una zona di sua competenza. Ci sono cinque zone
nell’area destinate all’accesso veicolare. Queste zone e le distanze in km tra di esse sono illustrate nella tabella. Per
avere il minor impatto possibile sull’ambiente, l’Ente vuole minimizzare il numero totale di km da pavimentare per
garantire i collegamenti veicolari tra le 5 aree. Determinare quali collegamenti dovrebbero essere pavimentati per
raggiungere l’obiettivo prefissato.
Dovrei risolvere quest'esercizio, ma non sono sicuro come. Qualcosa mi dice che dovrei utilizzare i grafi per ottenere l'albero ricoprente a costo minimo, ma non lo so. Cosa mi consigliate?
L’Ente Nazionale Parchi sta pianificando lo sviluppo di una zona di sua competenza. Ci sono cinque zone
nell’area destinate all’accesso veicolare. Queste zone e le distanze in km tra di esse sono illustrate nella tabella. Per
avere il minor impatto possibile sull’ambiente, l’Ente vuole minimizzare il numero totale di km da pavimentare per
garantire i collegamenti veicolari tra le 5 aree. Determinare quali collegamenti dovrebbero essere pavimentati per
raggiungere l’obiettivo prefissato.
Risposte
Non riesco a capire se devo usare un algoritmo tra Kruskal e Prim oppure devo calcolare i cammini minimi con Dijkstra?
Leggendo quest'esempio su wikipedia http://it.wikipedia.org/wiki/Algoritmo_di_Kruskal#Esempio_pratico_risolto
E quest'altro http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra#Risoluzione_pratica_di_un_esercizio
Deduco che si risolve con Kruskal, visto che non ho un punto di partenza e uno di arrivo e devo trovare un percorso minimo che copra tutte le aree della rete indipendentemente dall'ordine.
Aspetto qualche anima pia,
, che mi dia conferma quanto suddetto.
Grazie.
Leggendo quest'esempio su wikipedia http://it.wikipedia.org/wiki/Algoritmo_di_Kruskal#Esempio_pratico_risolto
E quest'altro http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra#Risoluzione_pratica_di_un_esercizio
Deduco che si risolve con Kruskal, visto che non ho un punto di partenza e uno di arrivo e devo trovare un percorso minimo che copra tutte le aree della rete indipendentemente dall'ordine.
Aspetto qualche anima pia,
, che mi dia conferma quanto suddetto.Grazie.
Qualcosa mi dice che dovrei utilizzare i grafi per ottenere l'albero ricoprente a costo minimo,
questo è lo spirito, i grafi escono da ogni dove, anche quando meno te lo aspetti
questo è un caso risolvibile con i grafi, però devi vedere bene cosa chiede il problema:
Per avere il minor impatto possibile sull’ambiente
perciò:
- L'algoritmo di Dijkstra/... risolve il problema dei camminini minini da sorgente unica in s (dipendente da un accesso veicolare in particolare)
- l'algortimo di Prim/Kruskal risolvere il problema minimum spanning tree, cioè il minimo albero radicato in r
(dipendente da un accesso veicolare in particolare)
se vuoi minimizzare l'impatto su tutto il grafo indipendentemente da dove parti ad analizzarlo (rispettivamente da dove entri con l'auto) che problema dovresti risolvere?
PS: si può formalizzare anche come problema di programmazione matematica.
"hamming_burst":
se vuoi minimizzare l'impatto su tutto il grafo indipendentemente da dove parti ad analizzarlo (rispettivamente da dove entri con l'auto) che problema dovresti risolvere?
Io ho utilizzato kruskal, ma se non ho capito male, nessuno tra prim/kruskal e dijkstra devo usare...beh nel programma di ricerca operativa al quale devo attenermi prevede questi tre algoritimi sui grafi e quello del massimo flusso(che non mi sembra attuabile a questo problema). A questo punto, non lo so. Devo farlo con la programmazione lineare?
"Skeggia":
Io ho utilizzato kruskal, ma se non ho capito male, nessuno tra prim/kruskal e dijkstra devo usare...
attento che è corretto utilizzarne uno di questi, ma non hai compreso bene come applicarli.
Forse un disegno ti può aiutare:
Il problema ci chiede di minimazzare, quello che devi domandarti: cosadobbiamo minimiazzare? la strada? il percorso?
tieni in considerazione che c'è un peso sugli archi, che è in questo caso la distanza euclidea.
Il problema dei cammini minimi da sorgente unica ci da un cammino (guarda un po'
) che percorre ogni vertice, ma questo percorso ci da davvero la minima pavimentazione? stesso discorso per l'albero.domandati: come minimizzo ogni percorso da ogni sorgente o radice?
"hamming_burst":
attento che è corretto utilizzarne uno di questi, ma non hai compreso bene come applicarli.
Diciamo che qualcosina l'avevo capita, però poi leggendo quello che mi hai scritto, sono andato fuori strada...
"hamming_burst":
domandati: come minimizzo ogni percorso da ogni sorgente o radice?
Con Dijkstra estraggo sempre il minimo dalla coda...mentre con kruskal elenco tutti gli archi in ordine crescente di distanza e evidenzio gli archi, procedendo nell'ordine dell'elenco, in modo da non creare cicli.
Ora sono ancora più confuso...
mi dispiacerebbe se non comprendi il ragionamento per arrivare alla soluzione, per come applicare uno dei due problemi, perciò proviamo un'ultima volta.
le cose che sappiamo:
- devi minimizzare la pavimentazione
- devi garantire che le cinque aree siano tutte collegate
applicato ai grafi:
- hai un grafo non-orientato, completamente connesso e completo.
- è un grafo pesato, dove le distanze euclidee sono i pesi
- essendo non-orientato i veicoli vanno in entrembe le direzioni
- il cammino deve essere minimo
- il problema non specifica il tipo di collegamento, perciò assumiamo che non ci servono circuiti.
In effetti forse la cosa che ti può confondere è che i due problemi si sovrappongono, perchè i cammini minimi (di solito) si utilizzano in grafi orientati e in questo caso è non-orientato e completo.
Perciò devi considerare TUTTI i vertici e TUTTI i cammini, quindi TUTTE le coppie di vertici. Capire se i due problemi sono equivalente o meno, in questo caso, lo lascio a te.
le cose che sappiamo:
- devi minimizzare la pavimentazione
- devi garantire che le cinque aree siano tutte collegate
applicato ai grafi:
- hai un grafo non-orientato, completamente connesso e completo.
- è un grafo pesato, dove le distanze euclidee sono i pesi
- essendo non-orientato i veicoli vanno in entrembe le direzioni
- il cammino deve essere minimo
- il problema non specifica il tipo di collegamento, perciò assumiamo che non ci servono circuiti.
In effetti forse la cosa che ti può confondere è che i due problemi si sovrappongono, perchè i cammini minimi (di solito) si utilizzano in grafi orientati e in questo caso è non-orientato e completo.
Perciò devi considerare TUTTI i vertici e TUTTI i cammini, quindi TUTTE le coppie di vertici. Capire se i due problemi sono equivalente o meno, in questo caso, lo lascio a te.
"hamming_burst":
mi dispiacerebbe se non comprendi il ragionamento per arrivare alla soluzione, per come applicare uno dei due problemi, perciò proviamo un'ultima volta.
Ti ringrazio per la pazienza che stai avendo...anche a me dispiacerebbe non comprendere il ragionamento, perché con esercizi simili sarei punto e a capo. Il fatto è che ero convinto che dovessi usare l'abero ricoprente, perché ho applicato Dijkstra in situazioni dove da una sorgente dovevo giungere ad una destinazione precisa.
Perciò devi considerare TUTTI i vertici e TUTTI i cammini, quindi TUTTE le coppie di vertici. Capire se i due problemi sono equivalente o meno, in questo caso, lo lascio a te.
Questo mi fa capire che devo usare Dijkstra perché devo considerare tutto. Invece, kruskal evita gli archi che creano i cicli. Ma sinceramente, non riesco ad essere convinto.
Per esempio ho un altro esercizio dove una persona devo spostarsi da casa all'ufficio ed ho una tabella simile a quella su che illustra i minuti di viaggio tra i luoghi intermedi per giungere a destinazione. E mi esce un grafo dove non tutti i nodi sono collegati tra loro. Lo scopo è quello di conoscere il percorso minimo in termini di minuti. Qui per me si applica Dijkstra, perché ho una sorgente e destinazione e si capisce che è un problema di cammini minimi.
"Skeggia":
Il fatto è che ero convinto che dovessi usare l'abero ricoprente, perché ho applicato Dijkstra in situazioni dove da una sorgente dovevo giungere ad una destinazione precisa.
dai che ci siamo
ho compreso il punto che non ti è chiaro.
Guardati bene l'algortimo di Dijkstra e quello di Kruskal (dove è ancora più evidente cosa accade) guarda quale è la scelta che viene fatta per il successivo nodo migliore.
Se guardi bene in Dijkstra (SP) si tiene conto di TUTTO il percorso dalla sorgente al nodo attuale, cioè la soluzione attuale può venir modificata se si trova un arco di costo minore.
In Kruskal (MST) si guardano solo i nodi adiacenti, perciò solo il nodo successivo e si sceglie l'arco di costo minore e non il cammino minore per esser raggiunto.
per il problema ci pensiamo dopo, per il momento vedi se ti è chiara la differenza dei problemi che è evitende nei loro algoritmi solutori.
"hamming_burst":
Guardati bene l'algortimo di Dijkstra e quello di Kruskal (dove è ancora più evidente cosa accade) guarda quale è la scelta che viene fatta per il successivo nodo migliore.
Se guardi bene in Dijkstra (SP) si tiene conto di TUTTO il percorso dalla sorgente al nodo attuale, cioè la soluzione attuale può venir modificata se si trova un arco di costo minore.
In Kruskal (MST) si guardano solo i nodi adiacenti, perciò solo il nodo successivo e si sceglie l'arco di costo minore e non il cammino minore per esser raggiunto.
Li ho rivisti e ho rifatto gli esempi associati, che per altro avevo capito. Il mio problema è questo: vedo le cose troppo meccanicamente. Cioè se mi dici fai kruskal o altri li so svolgere. Quando poi c'è da usare il cervello, vengono i problemi...uffà!!
Comunque devo applicare dijkstra perché considera tutto il percorso dalla partenza al nodo attuale. Lo stesso discorso vale anche per l'altro esercizio che brevemente ti ho esposto.
Che dire hamming_burst GRAZIE!!Spero di riuscire a superare questo esame nei prox mesi!!
"Skeggia":
Li ho rivisti e ho rifatto gli esempi associati, che per altro avevo capito. Il mio problema è questo: vedo le cose troppo meccanicamente. Cioè se mi dici fai kruskal o altri li so svolgere. Quando poi c'è da usare il cervello, vengono i problemi...uffà!!
bhe capita anche a me
Ma è una pratica utile, utilizzare soluzioni esistenti, di problemi ben noti, per risolverne altri
Comunque devo applicare dijkstra perché considera tutto il percorso dalla partenza al nodo attuale. Lo stesso discorso vale anche per l'altro esercizio che brevemente ti ho esposto.
La questione del post era il come applicare il problema dei camminimi minimi. Qua è un po' inutile parlane perchè è un grafo completo, ma dicendo di utilizzare Dijkstra bisognerebbe modificare il problema a cui è originiariamente appllicato (SP da singola sorgente) ed anche il tipo di grafo (SP con grafo orientato)
- il grafo devi trasformarlo in orientato, inserendo due archi uno uscente e l'altro entrante.
- il problema di cui parlo è quello dei "cammini minimi tra tutte le coppie". Ma in questo caso il grafo è completo ed è più semplice, basta applicare una singola volta l'algoritmo su un qualunque vertice.
Sembra la stessa cosa il ragionamento, ma attenzione a cosa si sta facendo.
Che dire hamming_burst GRAZIE!!Spero di riuscire a superare questo esame nei prox mesi!!
di nulla, quando avrai problemi basta postare
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo