Sto facendo un esercizio sui cammini minimi in c++. Sembra funzionare tutto, non ci sono errori in debug ma alla fine quando stampo i cammini mi stampa il cammino giusto ma con un elemento in meno.
Copio tutto il progetto.
Mi scuso se ho sbagliato i modi e luoghi per pubblicare questo problema.
il risultato del cammino dovrebbe essere : 0 14 15 3 7 5 11 4 2 6 1 13 9 10 12 8 0
ma risulta essere senza il nodo 15.
condivido anche il kingdom.txt da cui prendere le coordinate
#include "kingdom.h"
double kingdom::calcDistanza(nodo from, nodo dest) {
double x = (dest.getFirst() - from.getFirst());
x = x*x;
double y = (dest.getSecond() - from.getSecond());
y = y*y;
double somma = x+y;
double distanza = sqrt(somma);
return distanza;
}
void kingdom::inizializzaMappa(){
for( int i=0; i< n_isole ; i++) {
for(int j=0; j<n_isole ; j++){
if(i==j){
distMap[i][j] = 0;
} else {
distMap[i][j] = calcDistanza(isole[i], isole[j]); //calcola distanza ed assegna alla tabella distmap
}
}
}
for( int i=0; i< n_isole; i++) {
for (int j = 0; j < n_isole; j++) {
cout << distMap[i][j] << " ";
}
cout << endl;
}
}
void kingdom::stampaIsole(){
for (int i= 0; i< n_isole +1 ; i++){
nodo temp = isole[i];
cout << "le coordinate dell'isola " << temp.getName() << " sono : " << temp.getFirst() << " " << temp.getSecond() << endl;
}
}
int kingdom::VicinoMinimo(double *distanza){
double min = INT_MAX;
int index = 1;
for(int i=1; i< n_isole; i++){
if(!visitato[i]){
if( distanza[i] < min){
min = distanza[i];
index = i;
}
}
}
return index;
}
double kingdom::nearestNeighbourPath(){
for (int i= 0; i < n_isole ; i++){
visitato[i]= false;
}
int isolaCorrente = 0, prossimaIsola;
actualPath.push_back(0); //inizio dalla capitale
visitato[0] = true; //visita capitale
double totale = 0; //inizializza totale
for (int i= 1; i < n_isole ; i++){ //ciclo per tutte le isole
prossimaIsola = VicinoMinimo(distMap[isolaCorrente]); //cerchiamo con la funzione viciniminimo la prossima isola
cout << "\nsto prendendo l'isola : " << prossimaIsola << endl;
visitato[prossimaIsola] = true; //settiamo come visitata l'isola
for (int i = 0; i< visitato.size(); i++) {
cout << visitato[i] << ' ' ;
}
nodo temp1 = isole[prossimaIsola]; //estraiamo il nodo in una variabile temporanea
actualPath.push_back(temp1.getName()); //salviamo in un array il cammino
totale = totale + distMap[isolaCorrente][prossimaIsola]; //aggiorniamo il totale
isolaCorrente = prossimaIsola; //aggiorniamo l'isola corrente
}
//aggiungiamo il ritorno alla capitale
actualPath.push_back(0);
totale = totale + distMap[isolaCorrente][0];
costo1 = totale;
cout << "\nDistanza totale con Nearest Neighbour Algorithm = " << costo1 << endl;
cout << "Cammino utilizzato dall'algoritmo : " << endl;
for (int i = 0; i <actualPath.size(); i++) {
cout << actualPath[i] << ' ';
}
return costo1;
}
Rispondi quotando
