C Schleifenproblem

[datalukas]

Das wäre ja dann das Gleiche wie die C#-Lösung.
Dann kann ich es ja auch etwas anders machen (ist ja auch nicht zu umständlich), außerdem wusste ich ja nicht, ob das mit C genau so geht wie in C#.

Die A*-Algorithmus-Lösung ist jedenfalls schon mal falsch, das hab ich auch gemerkt, denn die F-Werte von Knoten werden nachträglich auch noch mit kleineren F-Werten überschrieben.

Also werde ich es mal von unten nach oben probieren.

EDIT: Ist die Hauptschleife so besser?

while(/*Kein f-Wert größer als ein abgeschlossener Weg ist*/)
	{
		/*Fortfahren mit dem Knoten, der den größten F-Wert besitzt
		Dazu werden die Array-Positionen des Knotens als Variablen max_z und max_r gespeichert*/
		for(int i = 14; i>=0; i--)
		{
			for(int n = 14; n>=0; n--)
			{
				if(f[i][n]>max)
				{
					f[i][n] = max;
					max_z = i;
					max_r = n;
				}
			}
		}
		//Untersuchung des größeren Nachfolgeknotens
		if(f[max_z-1][max_r-1]>f[max_z-1][max_r] && max_r > 0) 
		{
			//Wenn der Knoten schon in der Open List ist, darf der F-Wert mit einem anderen kleineren F-Wert übeschrieben werde
			if(zahlen_list[max_z-1][max_r-1] != 1 || f[max_z][max_r] - 99 + zahlen[max_z-1][max_r-1] > f[max_z-1][max_r-1]) 
			{
					f[max_z-1][max_r-1] = f[max_z][max_r] - 99 + zahlen[max_z-1][max_r-1];
					zahlen_list[max_z-1][max_r-1] = 1;
			}
		}
		else
		{
			if(zahlen_list[max_z-1][max_r] != 1 || f[max_z][max_r] - 99 + zahlen[max_z-1][max_r] > f[max_z-1][max_r])
			{	
				f[max_z-1][max_r] = f[max_z][max_r] - 99 + zahlen[max_z-1][max_r];
				zahlen_list[max_z-1][max_r] = 1;
			}
		}
		//Falls beide Nachfolgeknoten untersucht sind, kommt der Knoten auf die Closed List
		if(zahlen_list[max_z-1][max_r-1]==1 && zahlen_list[max_z-1][max_r]==1)
			zahlen_list[max_z][max_r]=2;
	}
	scanf("%i", &test);
	return 0;
}

 

[maxwell-cs]

hi, ich habe grade recht wenig zeit, aber da ich dich ja explizit aufgefordert habe, das mal effizienter zu machen:

kannst du vielleicht in einfachem pseudocode die idee deines algorithmus erklären? eine idee anhand von
-sorry- nicht so schönem C nachzuvollziehen ist etwas zeitraubend.
funktioniert der algorithmus auch auf der großen instanz (ich glaube problem 68 (?))?

falls du die große instanz noch nicht lösen kannst, also noch exponentiell bist, und nicht weiter kommst, kann ich dir ja die idee der effizienten lösung sagen.

 

[datalukas]

Die effiziente Lösung war in der C#-Lösung auch. Den Text habe ich nicht gelesen, aber die Idee war auf dem Bild zu sehen. Scheinbar muss das Dreieck in mehrere kleinere Dreiecke unterteilt werden, da sich die Wege zum Teil überschneiden.

Der Pseudocode befindet sich im Anhang als txt, da der Code-Tag das Ganze unlesbar macht.
Von der Lesbarkeit sollte man allerdings trotzdem nicht allzu viel erwarten, bei dem Algorithmus hab ichs nicht besser hinbekommen.

Die f-werte-Funktion sähe so aus:

bool fnumbers(int f[15][15])
{
	for(int i = 0; i<=14; i++)
	{
		for(int n = 0; n<=14; n++)
		{
			if(f[i][n]>f[0][0])
				return true;
		}
	}
	return false;
}

Sie untersucht, ob es irgendeinen F-Wert gibt, der größer als der von zahlen[0][0] ist, da dieser sich erst verändert, wenn ein Weg vollständig durchlaufen ist.

Übrigens bin ich mir ziemlich sicher, dass dieser Ansatz so nicht mal für den Problem 18 richtig funktioniert. In dieser Fassung (als C-Code natürlich) geht er jedenfalls erst mal nicht, Fehler sind also so oder so noch drinnen.

 

[maxwell-cs]

die idee ist es, für jeden punkt im dreieck zu berechnen, was die maximale länge eines weges von der spitze dahin ist. du brauchst keinen A*. du beginnst mit der wurzel, hier gibt es nur eine möglichkeit.

dann gehst du die punkte zeilenweise durch. wenn du einen punkt bearbeitest, weißt du, dass für den vorgänger nur zwei möglichkeiten in frage kommen, und der weg dahin natürlich ein längstmöglicher ist (den du schon berechnet hast, da du ja zeilenweise vorgehst). du brauchst also immer nur die beiden möglichen vorgänger zu betrachten und den längeren weg zu nehmen.

ich kann es vllt die tage mal in C hacken, aber die idee sollte klar sein.

 

[datalukas]

Eigentlich bin ich ja so vorgehen, bzw. wollte es so tun. Nur habe ich das Gefühl, dass immer der größere Vorgänger genommen wird und das Ergebnis somit falsch ist.