Alberi di Steiner
Buongiorno, questo è il primo messaggio che lascio su questo forum.
Sto cercando di risolvere il problema degli Steiner Trees.
L’istanza del problema è un grafo G = (V,E), un insieme R appartenente a V (dei nodi richiesti).
Il problema dello Steiner Tree consiste nel trovare un albero di costo minimo che ricopra (almeno) i vertici di R.
Per risolvere questo problema ho utilizzato l'algoritmo di Floyd - Warshall, il quale permette di calcolare, per ogni vertice V, il cammino minimo per raggiungere un qualsiasi altro vertice del grafo.
Detto questo, vorrei porvi una domanda.
Non mi pare semplicissimo, per un novello come me, trovare un algoritmo che riesca a trovare sempre l'albero di Steiner ottimo.
L'algoritmo che ho usato può realmente servirmi o dovrei intraprendere un'altra strada?
Sto cercando di risolvere il problema degli Steiner Trees.
L’istanza del problema è un grafo G = (V,E), un insieme R appartenente a V (dei nodi richiesti).
Il problema dello Steiner Tree consiste nel trovare un albero di costo minimo che ricopra (almeno) i vertici di R.
Per risolvere questo problema ho utilizzato l'algoritmo di Floyd - Warshall, il quale permette di calcolare, per ogni vertice V, il cammino minimo per raggiungere un qualsiasi altro vertice del grafo.
Detto questo, vorrei porvi una domanda.
Non mi pare semplicissimo, per un novello come me, trovare un algoritmo che riesca a trovare sempre l'albero di Steiner ottimo.
L'algoritmo che ho usato può realmente servirmi o dovrei intraprendere un'altra strada?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo