[ALGORITMI] Uso dei d-heap nell'algoritmo di Dijkstra, help
Ciao,
domani ho l'orale di algoritmi e sono abbastanza disperato.
Mi aiutate a fare un po' di chiarezza su questo argomento?
Se uso l'algoritmo di Dijkstra che usa un heap binario avrò una complessità di O(m*log(n)) con m=numero archi ed n = numero di nodi
Tale complessità è data dal fatto che quando vado ad inserire un nodo nell'insieme della soluzione parziale X potrei al più andare a modificare i pesi di m nodi nell'heap
Se il grafo è sparso allora questo algoritmo è efficiente
Il problema si pone però quando il grafo è DENSO (ovvero se ho un numero di archi \(m = \omega(n^2)\), in questo caso la complessità diventa \(\omega(n^2) \cdot _log(n)) peggiorando drasticamente la situazione
Stavo leggendo che in questi casi per migliorare la situazione potrei usare un d-heap ovvero un heap in cui ogni nodo ha di figli (tranne eventualmente l'ultima foglia a destra che potrebbe averne meno)
Mi pare di capire che a conti fatti se usassi un d-heap con grado d = m/n si possa dimostrare che il costo dell'algoritmo NON È SUPERIORE rispetto al costo di Dijkstra che fà uso di un heap binario, anzi potenzialmente potrei anche migliorare
Nel caso in cui ho un numero di archi \(m = \omega(n^2)\) la complessità dovrebbe essere circa \(O(n^2) \)
Quindi in finale ho che la complessità dovrebbe essere data dalla funzione \(min[n^2 ; m \cdot log(n)] \)
Quindi in pratica posso dire che usare un d-heap con grado d=m\n mi conviene perchè potrei migliorare ma sicuramente non peggioro mai la situazione?
E' veramente importante...per favore aiutatemi...temo che questa domanda me la farà domani all'orale...
Grazie mille
Andrea
domani ho l'orale di algoritmi e sono abbastanza disperato.
Mi aiutate a fare un po' di chiarezza su questo argomento?
Se uso l'algoritmo di Dijkstra che usa un heap binario avrò una complessità di O(m*log(n)) con m=numero archi ed n = numero di nodi
Tale complessità è data dal fatto che quando vado ad inserire un nodo nell'insieme della soluzione parziale X potrei al più andare a modificare i pesi di m nodi nell'heap
Se il grafo è sparso allora questo algoritmo è efficiente
Il problema si pone però quando il grafo è DENSO (ovvero se ho un numero di archi \(m = \omega(n^2)\), in questo caso la complessità diventa \(\omega(n^2) \cdot _log(n)) peggiorando drasticamente la situazione
Stavo leggendo che in questi casi per migliorare la situazione potrei usare un d-heap ovvero un heap in cui ogni nodo ha di figli (tranne eventualmente l'ultima foglia a destra che potrebbe averne meno)
Mi pare di capire che a conti fatti se usassi un d-heap con grado d = m/n si possa dimostrare che il costo dell'algoritmo NON È SUPERIORE rispetto al costo di Dijkstra che fà uso di un heap binario, anzi potenzialmente potrei anche migliorare
Nel caso in cui ho un numero di archi \(m = \omega(n^2)\) la complessità dovrebbe essere circa \(O(n^2) \)
Quindi in finale ho che la complessità dovrebbe essere data dalla funzione \(min[n^2 ; m \cdot log(n)] \)
Quindi in pratica posso dire che usare un d-heap con grado d=m\n mi conviene perchè potrei migliorare ma sicuramente non peggioro mai la situazione?
E' veramente importante...per favore aiutatemi...temo che questa domanda me la farà domani all'orale...
Grazie mille
Andrea
Risposte
Prima di tutto.. calmati.. dubito che ti farà una domanda del genere all'esame. A dire il vero sono ben altre le soluzioni normalmente adottate in grafi densi (e non) di grandi dimensioni. In questi casi, anche visitare tutti i nodi una volta è spesso troppo. In questi casi ci si accontenta spesso di cammini non ottimali o si utilizzano euristiche per ridurre il numero di nodi/archi visitati.
In ogni caso, dove hai trovato questa cosa? L'ha detta il tuo professore? L'hai letta su un libro? Su internet?
In ogni caso, dove hai trovato questa cosa? L'ha detta il tuo professore? L'hai letta su un libro? Su internet?
Premessa: il post lo ho scritto prima dell'intervento di apatriarca che in effetti ha pienamente ragione, è una questione tecnica e particolare questa della discussione, ed a un orale mi sembra troppo che venga richiesto.
Mi son lasciato un po' trasportare dalla descrizione, prendila come dissertazione interessante per chiarirti i dubbi ma nulla di più!
l'algoritmo che utilizza heap-binari si chiama Algoritmo di Johnson.
non mi piace proprio come l'hai espresso. Non lo caratterizzi in modo adeguato con l'utilizzo degli heap e non sottolinei da dove salta fuori $m$.
Meglio:
Ogni nodo è estratto dall'heap una sola volta e il ciclo di esplorazione del grafo è eseguito $n$ volte.
Le operazioni proprie delle strutture heap (dipende dal testo i nomi) deleteMin(), decrease() richiedono $O(log(n))$. nel caso pessim però decrease() è richiamato su tutti i nodi dell'insieme di adiacenza (G.adj(u)):
\[O\left (n*\log(n) + \left (\sum_{1\geq u \geq n} |\text{G.adj(u)}|\right )*\log(n)\right )\]
notando che $(\sum_{1\geq u \geq n} |\text{G.adj(u)}|) \in O(m)$ cioè il numero di archi.
Perciò la complessità che vien fuori è dominata da $O(mlog(n))$
è efficiente se $m in O(n)$ cioè è migliore di Dijkstra $O(n^2)$
vero
che deriva dal fatto che decrease() ha costo $O(log(n))$.
all'inizio pensavo ti riferissi all'algoritmo di Fredman-Tarjan che utilizza heap di Fibonacci ($O(m + nlog(n))$) per migliorare il caso di grafi densi nell'algoritmo di Johnson. Ma qua tratta un'altra versione. Poco cambia, il principio è quello migliorare una algoritmo esistente.
Mi son lasciato un po' trasportare dalla descrizione, prendila come dissertazione interessante per chiarirti i dubbi ma nulla di più!
"AndreaNobili":
Ciao,
domani ho l'orale di algoritmi e sono abbastanza disperato.
Mi aiutate a fare un po' di chiarezza su questo argomento?
Se uso l'algoritmo di Dijkstra che usa un heap binario avrò una complessità di O(m*log(n)) con m=numero archi ed n = numero di nodi
l'algoritmo che utilizza heap-binari si chiama Algoritmo di Johnson.
Tale complessità è data dal fatto che quando vado ad inserire un nodo nell'insieme della soluzione parziale X potrei al più andare a modificare i pesi di m nodi nell'heap
non mi piace proprio come l'hai espresso. Non lo caratterizzi in modo adeguato con l'utilizzo degli heap e non sottolinei da dove salta fuori $m$.
Meglio:
Ogni nodo è estratto dall'heap una sola volta e il ciclo di esplorazione del grafo è eseguito $n$ volte.
Le operazioni proprie delle strutture heap (dipende dal testo i nomi) deleteMin(), decrease() richiedono $O(log(n))$. nel caso pessim però decrease() è richiamato su tutti i nodi dell'insieme di adiacenza (G.adj(u)):
\[O\left (n*\log(n) + \left (\sum_{1\geq u \geq n} |\text{G.adj(u)}|\right )*\log(n)\right )\]
notando che $(\sum_{1\geq u \geq n} |\text{G.adj(u)}|) \in O(m)$ cioè il numero di archi.
Perciò la complessità che vien fuori è dominata da $O(mlog(n))$
Se il grafo è sparso allora questo algoritmo è efficiente
è efficiente se $m in O(n)$ cioè è migliore di Dijkstra $O(n^2)$
Il problema si pone però quando il grafo è DENSO (ovvero se ho un numero di archi \(m = \omega(n^2)\), in questo caso la complessità diventa \(\omega(n^2) \cdot \log(n) \) peggiorando drasticamente la situazione
vero
che deriva dal fatto che decrease() ha costo $O(log(n))$.
Stavo leggendo che in questi casi per migliorare la situazione potrei usare un d-heap ovvero un heap in cui ogni nodo ha di figli (tranne eventualmente l'ultima foglia a destra che potrebbe averne meno)
Mi pare di capire che a conti fatti se usassi un d-heap con grado d = m/n si possa dimostrare che il costo dell'algoritmo NON È SUPERIORE rispetto al costo di Dijkstra che fà uso di un heap binario, anzi potenzialmente potrei anche migliorare
Nel caso in cui ho un numero di archi \(m = \omega(n^2)\) la complessità dovrebbe essere circa \(O(n^2) \)
Quindi in finale ho che la complessità dovrebbe essere data dalla funzione \(min[n^2 ; m \cdot log(n)] \)
Quindi in pratica posso dire che usare un d-heap con grado d=m\n mi conviene perchè potrei migliorare ma sicuramente non peggioro mai la situazione?
E' veramente importante...per favore aiutatemi...temo che questa domanda me la farà domani all'orale...
Grazie mille
Andrea
all'inizio pensavo ti riferissi all'algoritmo di Fredman-Tarjan che utilizza heap di Fibonacci ($O(m + nlog(n))$) per migliorare il caso di grafi densi nell'algoritmo di Johnson. Ma qua tratta un'altra versione. Poco cambia, il principio è quello migliorare una algoritmo esistente.
Grazie,
sei stato molto chiaro...anche se ho difficoltà a capire fino in fondo e a fare mio questo argomento...
Purtroppo per me è un esame molto difficile e a questo appello su tipo 35-40 persone siamo stati ammessi all'orale solo in 3 persone...tutte e 3 non raggiungiamo la sufficienza e ci è stato detto che per portare a casa il 18 dobbiamo fare un OTTIMO orale...mi voglio suicidare...
sei stato molto chiaro...anche se ho difficoltà a capire fino in fondo e a fare mio questo argomento...
Purtroppo per me è un esame molto difficile e a questo appello su tipo 35-40 persone siamo stati ammessi all'orale solo in 3 persone...tutte e 3 non raggiungiamo la sufficienza e ci è stato detto che per portare a casa il 18 dobbiamo fare un OTTIMO orale...mi voglio suicidare...
Mi rendo conto che si tratta di un esame difficile, ma sei certo di volerlo passare con 18?
Comunque il discorso più preciso (cercando di capire dagli appunti) dovorebbe essere questo:
Per migliorare l'algoritmo invece di usare per forza di cose un heap binario potrei pensare di usare un d-heap
Come si è visto il problema dipende dalle operazioni di update (quella che tu chiami adj): \displaystyle {\left(\sum_{{{1}\geq{u}\geq{n}}}{\left|\text{G.adj(u)}\right|}\right)}\in{O}{\left({m}\right)} che è O(m), quindi se m=w(n^2) allora la complessità dell'algoritmo diventa quadratica...
Il suo ragionamento completo per ottimizzare l'algoritmo dovrebbe essere il seguente (sempre se riesco a seguire il filo logico...)
OSSERVAZIONE: Se aumento il GRADO DELL'HEAP, aumento il numero di figli che ogni nodo dell'heap deve avere succedono 2 cose:
1)DIMINUISCO L'ALTEZZA DELL'ALBERO (quindi una volta che inserisco un nuovo nodo nella soluzione parziale X di Dijkstra, quando vado ad aggiornare le distanze dei nodi ad esso vicini ho la possibilità di "risparmiare sul numero di livelli da scendere nell'heap" detto in maniera molto molto informale...
2) Aumentando il numero di figli di ogni nodo dell'heap aumento il numero di confronti da fare quando faccio l'operazione di POP che rimuove un elemento dall'heap (se prima avevo 2 confronti, ora ne ho d), quindi ora una operazione di pop non mi costa più O(log(n)) ma mi costa \(O(d \cdot log_d(n)) \)
Voglio dimostrare che maggiore è il grado d, migliore è la complessità
Intanto inizio a ragionare su quanto può valere il grado d di un Heap: può valere minimo 2 (heap binario) e massimo m/n (questa cosa non mi è del tutto chiara perchè ma vabbè...)
Quindi voglio dimostrare che scegliendo \(d = max [2; m/n]) \) (con n = numero nodi ed m = numero archi) miglioro sicuramente la situazione
CASO d=2
Allora il grafo G è molto sparso ed ho che m = O(n) e quindi la complessità di Dijkstra è O(n*log(n)) ed è buona
CASO d =m/n
Allora significa che ho n>2m
Adesso la complessità dell'algoritmo dipenderà da entrambi i parametri n ed m (credo per i 2 punti dell'osservazione precedente) e la complessità dell'algoritmo risulta essere:
\(T(n,m) = O(m \cdot log_{m/n}(n) ) \)
Quindi ora ho un logaritmo in base d=m/n
Ora lui per studiarsi la situazione esegue un cambio di base e se lo riporta nuovamente in un logaritmo avente BASE 2, cioè ho che la complessità equivale a:
\(T(n,m) = O(m \cdot \frac{log(m)}{log(\frac{m}{n}}) \)
OSSERVAZIONE: Poichè siamo nel caso m>2n allora vale che log(m/n) >= 1
Quindi visto che log(m/n) è il denominatore della mia complessità ricalcolata con i logaritmi in base 2 posso dire di trovare la seguente limitazione superiore:
\(m \cdot \frac{log(m)}{log(\frac{m}{n}} \le m \cdot log(m) \)
Poi dice che si osserva che
\(\frac{m}{log(\frac{m}{n})}\) è una FUNZIONE CRESCENTE avente il massimo in m=n^2 (anche se no capisco da dove se la ricavi questa funzione...mi viene da pensare dalla coomplessità ignorando il termine logaritmico log(m) che forse è trascurabile?)
Quindi ora si chiede cosa succede nel caso in cui ho che \(m = \Omega(n^2) \)
E per vederlo rvà a sostituire tale valore di m nella complessità espressa con i logaritmi in base d=m/n
\( T(n,m) = m \cdot log_{m/n}(n) = n^2 \cdot \frac{log(n^2)}{log(\frac{n^2}{n})} \approx n^2 \)
Quindi chiudo l'analisi che nel caso peggiore ho comunque una complessità quadratica, non vado a peggiorare ma potenzialmente potrei migliorare...
Spero di aver capito bene il ragionamento...solo che questa roba è una cambogia di conti ed onestamente a memoria non mi entrerà mai ed anche se la capisco posso spiegartela ma avendo un prospettino sotto mano...
Per migliorare l'algoritmo invece di usare per forza di cose un heap binario potrei pensare di usare un d-heap
Come si è visto il problema dipende dalle operazioni di update (quella che tu chiami adj): \displaystyle {\left(\sum_{{{1}\geq{u}\geq{n}}}{\left|\text{G.adj(u)}\right|}\right)}\in{O}{\left({m}\right)} che è O(m), quindi se m=w(n^2) allora la complessità dell'algoritmo diventa quadratica...
Il suo ragionamento completo per ottimizzare l'algoritmo dovrebbe essere il seguente (sempre se riesco a seguire il filo logico...)
OSSERVAZIONE: Se aumento il GRADO DELL'HEAP, aumento il numero di figli che ogni nodo dell'heap deve avere succedono 2 cose:
1)DIMINUISCO L'ALTEZZA DELL'ALBERO (quindi una volta che inserisco un nuovo nodo nella soluzione parziale X di Dijkstra, quando vado ad aggiornare le distanze dei nodi ad esso vicini ho la possibilità di "risparmiare sul numero di livelli da scendere nell'heap" detto in maniera molto molto informale...
2) Aumentando il numero di figli di ogni nodo dell'heap aumento il numero di confronti da fare quando faccio l'operazione di POP che rimuove un elemento dall'heap (se prima avevo 2 confronti, ora ne ho d), quindi ora una operazione di pop non mi costa più O(log(n)) ma mi costa \(O(d \cdot log_d(n)) \)
Voglio dimostrare che maggiore è il grado d, migliore è la complessità
Intanto inizio a ragionare su quanto può valere il grado d di un Heap: può valere minimo 2 (heap binario) e massimo m/n (questa cosa non mi è del tutto chiara perchè ma vabbè...)
Quindi voglio dimostrare che scegliendo \(d = max [2; m/n]) \) (con n = numero nodi ed m = numero archi) miglioro sicuramente la situazione
CASO d=2
Allora il grafo G è molto sparso ed ho che m = O(n) e quindi la complessità di Dijkstra è O(n*log(n)) ed è buona
CASO d =m/n
Allora significa che ho n>2m
Adesso la complessità dell'algoritmo dipenderà da entrambi i parametri n ed m (credo per i 2 punti dell'osservazione precedente) e la complessità dell'algoritmo risulta essere:
\(T(n,m) = O(m \cdot log_{m/n}(n) ) \)
Quindi ora ho un logaritmo in base d=m/n
Ora lui per studiarsi la situazione esegue un cambio di base e se lo riporta nuovamente in un logaritmo avente BASE 2, cioè ho che la complessità equivale a:
\(T(n,m) = O(m \cdot \frac{log(m)}{log(\frac{m}{n}}) \)
OSSERVAZIONE: Poichè siamo nel caso m>2n allora vale che log(m/n) >= 1
Quindi visto che log(m/n) è il denominatore della mia complessità ricalcolata con i logaritmi in base 2 posso dire di trovare la seguente limitazione superiore:
\(m \cdot \frac{log(m)}{log(\frac{m}{n}} \le m \cdot log(m) \)
Poi dice che si osserva che
\(\frac{m}{log(\frac{m}{n})}\) è una FUNZIONE CRESCENTE avente il massimo in m=n^2 (anche se no capisco da dove se la ricavi questa funzione...mi viene da pensare dalla coomplessità ignorando il termine logaritmico log(m) che forse è trascurabile?)
Quindi ora si chiede cosa succede nel caso in cui ho che \(m = \Omega(n^2) \)
E per vederlo rvà a sostituire tale valore di m nella complessità espressa con i logaritmi in base d=m/n
\( T(n,m) = m \cdot log_{m/n}(n) = n^2 \cdot \frac{log(n^2)}{log(\frac{n^2}{n})} \approx n^2 \)
Quindi chiudo l'analisi che nel caso peggiore ho comunque una complessità quadratica, non vado a peggiorare ma potenzialmente potrei migliorare...
Spero di aver capito bene il ragionamento...solo che questa roba è una cambogia di conti ed onestamente a memoria non mi entrerà mai ed anche se la capisco posso spiegartela ma avendo un prospettino sotto mano...
"apatriarca":
Mi rendo conto che si tratta di un esame difficile, ma sei certo di volerlo passare con 18?
C'è gente che lo ha fatto 10 volte per avere un 18...se mi mette 18 accendo un cero alla madonna...ho 28 anni e mi voglio laureare, la specialistica non ho alcuna intenzione di farla e non farò mai il matematico "da grande" (faccio il programmatore)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo