4x4 Matrix Fahrstrecken berechnen



  • Hallo zusammen,
    ich habe ein Programm zu schreiben, dass folgendes tun soll:

    • die Gesamtlänge sowie die Gesamtfahrzeit für alle möglichen Streckenkombinationen eines Bahnnetzes berechnen, das aus 4 Knotenpunkten besteht.

    Die Entfernungen und die Durchschnittsgeschwindigkeiten zwischen den Knotenpunkten sind in einer
    4x4-Matrix als Datei gespeichert:

      1)  2)  3)  4)
    4) 600 400 300 0
    3) 350 250 0 180
    2) 150 0 95 105
    1) 0 75 90 120
    

    Daraus kann man z.b folgendes entnehmen:
    Entfernung zwischen den Knotenpunkten 1 und 2: 150 km
    Durchschnittsgeschwindigkeit zwischen bei diesem Streckenabschnitt beträgt 75 km/h.

    Strecke: 	 Länge[km]: 	 Fahrzeit[min]:
    1-2 		 150 		 120
    ..               ..              ..
    1-2-3 		 400 		 288
    ..               ..              ..     
    3-1-2            ..              ..
    ... usw
    

    Ich habe die Aufgabe im Prinzip gelöst. Die Ausgabe stimmt und die Berechnungen sind soweit auch korrekt. Hier ist mein Code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define KNOTEN 4
    
    int calcFactorial(int zahl);
    void readMatrix(FILE *knoten, int matrix[][KNOTEN]);
    void calcPermutations(int permutation[KNOTEN - 1]);
    int calcMaxPermutation(int permutation[KNOTEN - 1]);
    void calculate(int matrix[][KNOTEN], char strecke[][100], int laenge[], float zeit[], int maxPermutation);
    void printResults(char strecke[][100], int laenge[], float zeit[], int maxPermutation);
    
    int main()
    {
    	FILE *knoten;
    	int matrix[KNOTEN][KNOTEN], permutation[KNOTEN - 1];
    	int maxPermutation = 0;
    
    	knoten = fopen("knoten.txt", "r");
    	if(knoten == NULL)
    	{
    		printf("Datei konnte nicht geöffnet werden.\n");
    		return 1;
    	}
    
    	readMatrix(knoten, matrix);
    	calcPermutations(permutation);
    	maxPermutation = calcMaxPermutation(permutation);
    
    	char strecke[maxPermutation][maxPermutation];
    	int laenge[maxPermutation];
    	float zeit[maxPermutation];
    
    	calculate(matrix, strecke, laenge, zeit, maxPermutation);
    
    	printResults(strecke, laenge, zeit, maxPermutation);
    
    	fclose(knoten);
    	return 0;
    }
    
    int calcFactorial(int zahl)
    {
    	int fakultaet = 1;
    
    	for(int i = 1; i <= zahl; i++)
    		fakultaet += fakultaet * (zahl - i);
    
    	return fakultaet;
    }
    
    void readMatrix(FILE *knoten, int matrix[][KNOTEN])
    {
    	for(int i = KNOTEN - 1; i >= 0; i--)
    	{
    		for(int j = 0; j < KNOTEN; j++)
    			fscanf(knoten, "%d", &matrix[j][i]);
    	}
    }
    
    void calcPermutations(int permutation[])
    {
    	int i, j;
    
    	for(i = 0, j = 2 ; j <= KNOTEN; i++, j++)
    		permutation[i] = calcFactorial(KNOTEN) / calcFactorial(KNOTEN - j);
    }
    
    int calcMaxPermutation(int permutation[KNOTEN - 1])
    {
    	int max = 0;
    
    	for(int i = 0; i < KNOTEN - 1; i++)
    		max += permutation[i];
    
    	return max;
    }
    
    void calculate(int matrix[][KNOTEN], char strecke[][100], int laenge[], float zeit[], int maxPermutation)
    {
    	int i, j, k, l, m;
    	char temp[maxPermutation];
    	int count = 0;
    
    	for(i = 0; i < KNOTEN; i++)
    	{
    		for(j = 0; j < KNOTEN; j++)
    		{
    			if(i == j)
    				continue;
    
    			sprintf(temp, "%d-%d", i+1, j+1);
    			strcpy(strecke[count], temp);
    			laenge[count] = matrix[i][j];
    			zeit[count] += (float)matrix[i][j] / matrix[j][i] * 60;
    			count++;
    		 }
    	}
    
    	for(i = 0; i < KNOTEN; i++)
    	{
    		for(j = 0; j < KNOTEN; j++)
    		{
    			for(k = 0; k < KNOTEN; k++)
    			{
    				if(i == j || i == k || j == k)
    					continue;
    
    				sprintf(temp, "%d-%d-%d", i+1, j+1, k+1);
    				strcpy(strecke[count], temp);
    				laenge[count] = matrix[i][j] + matrix[j][k];
    				zeit[count] = ((float)matrix[i][j] / matrix[j][i] * 60) + ((float)matrix[j][k] / matrix[k][j] * 60) + 10;
    				count++;
    			}
    		}
    	}
    
    	for(i = 0; i < KNOTEN; i++)
    	{
    		for(j = 0; j < KNOTEN; j++)
    		{
    			for(k = 0; k < KNOTEN; k++)
    			{
    				for(l = 0; l < KNOTEN; l++)
    				{
    					if(i == j || i == k || i == l || j == k || j == l || l == k)
    						continue;
    
    					sprintf(temp, "%d-%d-%d-%d", i+1, j+1, k+1, l+1);
    					strcpy(strecke[count], temp);
    					laenge[count] = matrix[i][j] + matrix[j][k] + matrix[k][l];
    					zeit[count] = ((float)matrix[i][j] / matrix[j][i] * 60) + ((float)matrix[j][k] / matrix[k][j] * 60) + ((float)matrix[k][l] / matrix[l][k] * 60) + 20;
    					count++;
    				}
    			}
    		}
    	}
    
    
    }
    
    void printResults(char strecke[][100], int laenge[], float zeit[], int maxPermutation)
    {
    	printf("Strecke: \t Länge[km]: \t Fahrzeit[min]:\n");
    
    	for(int i = 0; i < maxPermutation; i++)
    		printf("%s \t\t %d \t\t %0.f\n", strecke[i], laenge[i], zeit[i]);
    }
    

    Auch wenn in der Aufgabe nicht verlangt, will ich der Vollständigkeit halber das Programm so umschreiben, dass man damit auch z.B eine 8x8 Matrix bearbeiten kann. Mein Problem ist aber, dass mir nicht einfällt wie ich die Berechnung vereinfachen kann.
    Bei einer 8x8 Matrix wären das 8 verschachtelte for-Schleifen!?

    Darum meine Frage hier. Kann mir jemand eine Vereinfachung für die Berechnungen anbieten?
    Vielen Dank im Voraus.


  • Global Moderator |  Mod

    Ich verstehe nicht, wozu du überhaupt 4 verschachtelte Schleifen brauchst. Sei die Anzahl der Knotenpunkt N. Von Punkt 1 kannst du zu den Punkten 2 bis N fahren. Von Punkt 2 kannst du zu den Punkten 1 und 3 bis N fahren, aber die Strecke 1 bis 2 hattest du schon, also bleiben von 2 aus nur noch die Strecken 3 bis N übrig. Von Punkt 3 aus kannst du nach 1 und 2 und nach 4 bis N fahren. 1 bis 3 und 2 bis 3 hattest du schon, bleiben also nur noch 4 bis N. Und so weiter.

    Das sind zwei Schleifen, eine für den Start und eine für die möglichen Ziele. Es ist völlig egal, ob N gleich 4, 8, oder 43934346643 ist.



  • Ich verstehe nicht ganz. Wie kann ich dann die Streckenvarianten mit 2 Schleifen darstellen? Dann kann ich sprintf auch nicht mehr verwenden oder ?



  • Du könntest ein int-array mit den Werten 0..KNOTEN-1 erstellen. Und dann die C++-Funktion std::next_permutation in C nachbauen und dann einfach, solange du eine weitere Permutation erzeugst, diese verwenden.

    Du kannst sonst auch Rekursion benutzen.



  • Du könntest auch Rekursion verwenden.



  • So ich hab es nun geschafft mit Rekursion die Streckenvarianten auszugeben. Dennoch weiß ich nicht weiter wie ich die Längen der jeweiligen Strecken berechne.

    void permute(int matrix[][KNOTEN], int *knoten, int size, int position, int n)
    {
    	int k[20];
    
    	if(position == n)
    	{
    		for(int i = 0; i < n; i++)
    		{
    			k[i] = knoten[i];
    			printf("%d-", knoten[i]);
    		}
    
    		printf("\t\t");
    
    		for(int i = 0; i < n-1; i++)
    		{
    			for(int j = n-1; j > 0; j--)
    			{
    				printf("%d", matrix[k[i]][k[j]]);
    			}
    		}
    
    		printf("\n");
    	}
    
    	for(int i = position; i <= size-1; i++)
    	{
    		swap(&knoten[i], &knoten[position]);
    		permute(matrix, knoten, size, position+1, n);
    		swap(&knoten[i], &knoten[position]);
    	}
    }
    


  • Indem du die Summe der Einzelstrecken bildest.



  • Das kennt wohl jeder, wenn man den Wald vor lauter Bäumen nicht mehr sieht...
    Das Beste ist wohl, die Arbeit immer an anderen Stellen zu erledigen. In dem Fall sind es die Fahrdauern, die direkt berechnet werden können (die Durchschnittsgeschwindigkeit wird anschließend sowieso nicht mehr benötigt) und eben die Permutationsberechnung, die bei der Bestimmung der Gesamtdistanz und Fahrdauer nichts verloren hat.
    Der Aufbau würde dann viel klarer sein:

    const int KNOTEN=4;
    ...
    int indices[KNOTEN];
    // erste Strecke 0 1 2 3
    for(int k=0; k<KNOTEN; ++k)
        indices[k]=k;
    do
    {
        int distance=0, duration=0;
        for(int k=0; k<KNOTEN; ++k)
        {
            printf("%d ", indices[k]);
            if(k)
            {
                // distance+=Matrix[indices[k-1]][indices[k]]
                // duration+=Matrix[indices[k]][indices[k-1]]
            }
        }
        /* Ausgabe Distanz und Dauer*/
        putchar('\n');
    
    } while(next_permutation(&indices[0], &indices[KNOTEN]));
    

    Auslagern von Funktionalität ist natürlich auch hinsichtlich der Wiederverwendung super. Leider kennt C keine templates.

    void swap(int* i1, int* i2)
    {
    	int t=*i1;
    	*i1=*i2;
    	*i2=t;
    }
    
    void reverse(int* first, int* last)
    {
    	for( ; first!=last && first!=--last; ++first)
    		swap(first, last);
    }
    
    typedef enum bool_ {false, true} bool;
    
    // Code von HP
    bool next_permutation(int* first, int* last)
    {
    	if(first==last)
    		return false;
    	int* i=first;
    	++i;
    	if(i==last)
    		return false;
    	i=last;
    	--i;
    	for(;;)
    	{
    		int* ii=i--;
    		if(*i<*ii)
    		{
    			int* j=last;
    			while(!(*i<*--j));
    			swap(i, j);
    			reverse(ii, last);
    			return true;
    		}
    		if(i==first)
    		{
    			reverse(first, last);
    			return false;
    		}
    	}
    }
    

    Edit: Mir fällt gerade noch auf, dass zu dem Startpunkt wohl noch zurückgekehrt werden sollte, aber das lässt sich auch noch leicht einbauen. Am besten, du lagerst alle Berechnungen einfach in einer weiteren Funktion aus.