#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define ZEILENLAENGE 100#define TRUE 1#define FALSE 0#define MAX 100//Globale Variablenfloat strecke = 0;//Funktionenvoid zeige_hilfe();void datei_hilfe();float kleinste_strecke(float array[MAX], int anzahl);int naechster_nachbar(float matrix[MAX][MAX], int n, int punkt);/**********************************************************************************************************/int main(int argc, char *argv[]){ FILE *fp; //Variablen clock_t start, ende; char puffer[ZEILENLAENGE]; int zeilen = 0; int n,i,j; int letzter_punkt; float x[MAX]; float y[MAX]; float matrix[MAX][MAX]; float matrix_tmp[MAX][MAX]; if(argv[1] == NULL) /*Wurde ein Kommandozeilenparameter angegeben*/ { printf("Es wurde keine Datei angegeben!\n"); exit(1); } if(argc != 2) { zeige_hilfe(); } if((fp = fopen(argv[1], "r")) == NULL) /*Kann die Datei zum Lesen geöffnet werden*/ perror("Fehler beim Oeffnen der Datei"); else { while(fgets(puffer,ZEILENLAENGE,fp)) /*Die Anzahl der Zeilen wird ermittelt*/ zeilen++; fseek(fp, 0L, SEEK_SET); /*Der Zeiger fp wird an den Anfang der Datei gesetzt*/ fscanf(fp,"%d",&n); if(n <= 0 || n != zeilen - 1)//stimmt n nicht mit den zeilen-1 ueberein, zeige datei_hilfe() datei_hilfe(); else { i = 0; while(fgets(puffer,ZEILENLAENGE,fp) && i < n)//die datei wird zeilenweise ausgelesen { fscanf(fp,"%f %f",&x[i],&y[i]);//Die Koordinaten x und y werden befuellt i++; } fclose(fp);//die datei wird geschlossen for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(i == j) //der weg zu sich selbst ist null matrix[i][j] = 0.0; else//die entfernung der knoten wird berechnet und in der matrix abgespeichert matrix[i][j] = (float)sqrt(pow((x[i] - x[j]),2) + pow((y[i] - y[j]),2)); } } for(i = 0; i < n; i++)//Befuellen der matrix_tmp { for(j = 0; j < n; j++) { matrix_tmp[i][j] = matrix[i][j]; } } /*for(i = 0; i < n; i++)//testausgabe der matrix { for(j = 0; j < n; j++) { printf("\t%g",matrix[i][j]); } printf("\n"); }*/ printf("-----------------------------------------------------------------------------\n"); printf("---------------------NEAREST NEIGHBOUR ALGORITHMUS---------------------------\n"); printf("-----------------------------------------------------------------------------\n\n"); start = clock(); //Die Zeit beginnt zu laufen printf("Startpunkt 1\n"); //Es wird immer vom Punkt 1 ausgegangen letzter_punkt = naechster_nachbar(matrix_tmp,n,0); strecke = strecke + matrix[0][letzter_punkt]; //die strecke vom letzten zum ersten Punkt wird noch addiert printf("Strecke: %g\n",matrix[0][letzter_punkt]); printf("Endpunkt 1\n"); printf("Gesamtstrecke: %g\n",strecke); ende = clock(); //Die Zeit stoppt printf("-----------------------------------------------------------------------------\n"); printf("CPU-Zeit fuer den Nearest Neighbour Algorithmus: %.2f Sekunden\n", /*Ausgabe der benötigten Zeit in Sekunden*/ (float)(ende-start)/CLOCKS_PER_SEC); printf("-----------------------------------------------------------------------------\n"); } } return EXIT_SUCCESS;}/**********************************************************************************************************/void zeige_hilfe(){ printf("usage: tsp <filename>\n"); exit(1);}/**********************************************************************************************************/void datei_hilfe(){ printf("Der Wert n muss mit der Anzahl der Koordinaten uebereinstimmen!\n"); exit(1);}/**********************************************************************************************************/int naechster_nachbar(float matrix[MAX][MAX], int n, int punkt){ int i, j; int next; int ende = TRUE; float kleinste = 0; float matrix_tmp[MAX]; for(i = 0; i < n; i++)//Befuellen des Arrays matrix_tmp[], wird dann an die { //Fkt. kleinste_strecke uebergeben matrix_tmp[i] = matrix[punkt][i]; } kleinste = kleinste_strecke(matrix_tmp,n);//Aufruf der Fkt. kleinste_strecke for(i = 0; i < n; i++) { if(kleinste == matrix[punkt][i])//der naechste Punkt wird ermittelt next = i; } printf("Strecke: %f\n",kleinste); printf("Naechster Punkt: %d\n",next+1); for(i = 0; i < n; i++)//Punkte die nicht mehr besucht werden koennen, werden mit False befuellt { matrix[punkt][i] = FALSE; matrix[i][punkt] = FALSE; } for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(matrix[i][j] > 0) //ist noch ein Punkt vorhanden ende = FALSE; } } if(ende == FALSE) // es ist noch ein Punkt vorhanden, also rekursiver Aufruf der Funktion naechster_nachbar(matrix,n,next); strecke = strecke + kleinste; return next;}/**********************************************************************************************************/float kleinste_strecke(float array[MAX], int anzahl){ int i, j; float kleinste; for (i = 0; i < anzahl; i++) { for (j = anzahl - 1; j >= i; j--) { if (array[j] < array[j - 1]) { kleinste = array[j]; array[j] = array[j - 1]; array[j - 1] = kleinste; } } } i = 0; while(array[i] == 0) i++; return array[i]; //die kleinste strecke != 0 wird zurueckgegeben!}