Pages: [1]   Go Down
Print
Author Topic: Chiarimento esercizio su cammini minimi  (Read 562 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« on: 03-02-2017, 00:40:08 »

Di seguito il testo dell'esercizio:

(a) Si illustri un algoritmo, valutandone anche la complessità computazionale, per determinare in maniera efficiente se un dato grafo pesato (G;w), ove G=(V;E) e w:E->R, contiene un ciclo di peso negativo.

(b) Si risolva lo stesso esercizio, ma per veri care l'eventuale presenza di cicli di peso positivo.

Per quanto riguarda il punto a) penso possa essere corretto utilizzare l'algoritmo di Bellman-Ford sul grafo G1 modificato opportunamente come nella prima parte dell'algoritmo di Johnson caso generale. In questo caso la complessità totale sarebbe O(V)+O(VE)=O(VE) rispetto a Floyd-Warshall O(V3)

Sul punto b) invece ho qualche dubbio. Ho cercato anche sulla rete per confrontare possibili soluzioni.
Ho trovato un primo metodo in cui si utilizza Bellman-Ford con il peso degli archi invertito, cioè w(u,v)=-w(u,v) che restituisca TRUE chiamando !Bellman-Ford. In questo caso dovremmo però iterarlo per ogni vertice, ma possiamo utilizzare sempre la procedura come nel punto a) La complessità totale dovrebbe essere O(E)+O(V)+O(VE)=O(VE).
L'altra soluzione è quella di modificare l'algoritmo di Floyd-Warshall come riportato qui:
Quote
Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, then the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph). Fonte
In questo caso la complessità sarebbe O(V3)
Sono corretti come procedimenti? C'è qualche altra soluzione? Ho sbagliato tutto e ho fatto na' figuraccia?  testate
Logged
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 342



« Reply #1 on: 03-02-2017, 09:20:17 »

Di seguito il testo dell'esercizio:

(a) Si illustri un algoritmo, valutandone anche la complessità computazionale, per determinare in maniera efficiente se un dato grafo pesato (G;w), ove G=(V;E) e w:E->R, contiene un ciclo di peso negativo.

(b) Si risolva lo stesso esercizio, ma per veri care l'eventuale presenza di cicli di peso positivo.

Per quanto riguarda il punto a) penso possa essere corretto utilizzare l'algoritmo di Bellman-Ford sul grafo G1 modificato opportunamente come nella prima parte dell'algoritmo di Johnson caso generale. In questo caso la complessità totale sarebbe O(V)+O(VE)=O(VE) rispetto a Floyd-Warshall O(V3)

Sul punto b) invece ho qualche dubbio. Ho cercato anche sulla rete per confrontare possibili soluzioni.
Ho trovato un primo metodo in cui si utilizza Bellman-Ford con il peso degli archi invertito, cioè w(u,v)=-w(u,v) che restituisca TRUE chiamando !Bellman-Ford. In questo caso dovremmo però iterarlo per ogni vertice, ma possiamo utilizzare sempre la procedura come nel punto a) La complessità totale dovrebbe essere O(E)+O(V)+O(VE)=O(VE).
L'altra soluzione è quella di modificare l'algoritmo di Floyd-Warshall come riportato qui:
Quote
Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, then the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph). Fonte
In questo caso la complessità sarebbe O(V3)
Sono corretti come procedimenti? C'è qualche altra soluzione? Ho sbagliato tutto e ho fatto na' figuraccia?  testate

Perché non ne parliamo al ricevimento di oggi pomeriggio?
Logged
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #2 on: 03-02-2017, 10:32:16 »

Purtroppo non mi trovo a Catania professore, altrimenti sarei venuto con piacere.

EDIT:

Eventualmente se non è un problema, la posso chiamare pomeriggio al suo ufficio.
« Last Edit: 03-02-2017, 10:42:30 by turì » Logged
Domenico Cantone
Moderator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 342



« Reply #3 on: 03-02-2017, 12:32:06 »

Di seguito il testo dell'esercizio:

(a) Si illustri un algoritmo, valutandone anche la complessità computazionale, per determinare in maniera efficiente se un dato grafo pesato (G;w), ove G=(V;E) e w:E->R, contiene un ciclo di peso negativo.

(b) Si risolva lo stesso esercizio, ma per veri care l'eventuale presenza di cicli di peso positivo.

Per quanto riguarda il punto a) penso possa essere corretto utilizzare l'algoritmo di Bellman-Ford sul grafo G1 modificato opportunamente come nella prima parte dell'algoritmo di Johnson caso generale. In questo caso la complessità totale sarebbe O(V)+O(VE)=O(VE) rispetto a Floyd-Warshall O(V3)

Sul punto b) invece ho qualche dubbio. Ho cercato anche sulla rete per confrontare possibili soluzioni.
Ho trovato un primo metodo in cui si utilizza Bellman-Ford con il peso degli archi invertito, cioè w(u,v)=-w(u,v) che restituisca TRUE chiamando !Bellman-Ford. In questo caso dovremmo però iterarlo per ogni vertice, ma possiamo utilizzare sempre la procedura come nel punto a) La complessità totale dovrebbe essere O(E)+O(V)+O(VE)=O(VE).
L'altra soluzione è quella di modificare l'algoritmo di Floyd-Warshall come riportato qui:
Quote
Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, then the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph). Fonte
In questo caso la complessità sarebbe O(V3)
Sono corretti come procedimenti? C'è qualche altra soluzione? Ho sbagliato tutto e ho fatto na' figuraccia?  testate

OK per quanto riguarda il punto (a) (si inserisce una nuova sorgente collegandola con archi, ad es. di costo nullo, a tutti i vertici di G).

Per quanto riguarda il punto (b), invertendo il peso di ciascun arco, il problema viene ricondotto al precedente (cioè di ricercare nel nuovo grafo possibili cicli di peso negativo). Pertanto, in entrambi i casi, la complessità computazionale asintotica è quella dell'algoritmo di Bellman-Ford, cioè O(VE).
Logged
turì
Apprendista Forumista
**
Offline Offline

Posts: 275



« Reply #4 on: 03-02-2017, 12:36:36 »

Grazie tante professore.

Per quanto riguarda il punto b) sarebbe corretto utilizzare la modifica di Floyd Warshall oppure no, indipendentemente dalla complessità? Oppure vale solo per trovare cicli in generale?
Logged
Pages: [1]   Go Up
Print
Jump to: