Unauffindbarer Fehler bei einem Optimierungsproblem
-
Hallo,
das ist mein erster Post hier, also bitte verzeiht mir alles, was ich falsch mache
Ich habe eine Funktion, bei der ich den Fehler nicht finde.
Ziel ist es, ein Programm zu schreiben, dass folgendes leistet:
Gegeben sind n Elemente.
Jedes Element hat die Zuverlässigkeit ZV.
Jedes Element darf beliebig oft genutzt werden (um die gesammtzuverlässigkeit zu erhöhren).
Jedes Element kostet einen bestimmten Betrag.
Ein bekanntes Budget darf nicht überschritten werden. Jedes Element muss mindestens einmal vorkommen.So, das waren die Bedingungen.
Der Code der Funktion, die die eigentliche Optimierung leistet, ist folgender:
// ===== Rekursive Funktion zur Bestimmung des Optimums ===== double f(int Stufen,double Budget, double* ZV, double* Ko, int* Vielf){ FunkAuf++; if (Stufen>1) { double Restkosten=0; //Bestimmung der Kosten fuer das restliche System (ausgenommen die jetzige Stufe). for (int i=1; i<Stufen; i++) Restkosten=Restkosten+Ko; /* opt: Wahrscheinlichkeit der bisher besten Loesung. result: speichert die aktuelle Loesung. momkost: Kosten fuer die aktuelle Stufe. */ double opt=0; double result=0; double momkost=Ko[0]; for (int i=1; Budget-momkost>=Restkosten;i++){ result=(1-Power(1-ZV[0],i))*f(Stufen-1,Budget-momkost,&ZV[1],&Ko[1],&Vielf[1]); if (result>opt) { opt=result; Vielf[0]=i; } momkost=momkost+Ko[0]; } return opt; } else { /* opt: Wahrscheinlichkeit der bisher besten Loesung. result: speichert die aktuelle Loesung. momkost: Kosten fuer die aktuelle Stufe. */ double opt=0; double result=0; double momkost=Ko[0]; for (int i=1; Budget-momkost>=0;i++){ result=1-Power(1-ZV[0],i); if (result>opt) { opt=result; Vielf[0]=i; } momkost=momkost+Ko[0]; } return opt; } }Die Ausgabe dazu lautet:
Beispiel 1: Stufe Vielf. Kosten Zuv. Komp. Zuv. Stufe --------------------------------------------------- 1 7 2.20 0.50 0.992188 2 1 1.60 0.90 0.900000 Fehler! 3 1 3.20 0.80 0.800000 Fehler! 4 1 5.10 0.90 0.900000 Fehler! 5 1 1.10 0.40 0.400000 Fehler! --------------------------------------------------- Gesamt 26.40 0.976159 Von dem Budget 56 haben Sie 26.4 verbraucht. Ihre Zuverlaessigkeit von 0.976159 ist Ok. Sie haben 0 Sekunden und 5898 Funktionsaufrufe benoetigt. Eigentlich benoetigt man 9546 Aufrufe. Die Musterloesung brauchte 0 Sekunden.Man sieht:
Es wird nicht das gesammte Budget aufgebraucht.
Es werden unkluge Entscheidungen getroffen (Stufe 2 ist billiger und Zuverlässiger als Stufe 1, wurde aber nur einmal gewählt).Bei Bedarf reiche ich gerne den gesamte Quelltext nach.
Gruß,
SaM[i]edit*
Nachtrag:
Ich vermute, dass der Fehler hier liegt:if (result>opt) { opt=result; Vielf[0]=i; }Dort wird immer wieder das Array für die Vielfachkeiten (also wie oft Element n vorhanden ist) immer wieder überschrieben.
Dementsprechend werden dort komplett falsche Informationen aufgesammelt.... Wie kann man das beheben?edit2
Ich hab das Programm nun modifiziert://tmpVielf speichert die Vielfachen der momentan optimalsten Lösung ab. //Dadurch kommt es vermutlich zu den Verzögerungen im Programmablauf. //TODO: Bessere Lösung finden! int *tmpVielf = new int[Stufen]; for (int i=1; Budget-momkost>=Restkosten;i++){ result=(1-Power(1-ZV[0],i))*f(Stufen-1,Budget-momkost,&ZV[1],&Ko[1],&Vielf[1]); if (result>opt) { opt=result; tmpVielf[0]=i; for (int j=1; j<Stufen; j++) tmpVielf[j]=Vielf[j]; } momkost=momkost+Ko[0]; } for (int j=0; j<Stufen; j++) Vielf[j]=tmpVielf[j]; delete tmpVielf; return opt;Jetzt funktioniert dsa Programm, aber das umkopieren der Arrays scheint sehr viel zeit zu benötigen (ca. 10 mal länger als die Musterlösung). Hat jemand eine Idee, wie man das effizienter machen kann?
-
Du musst dir nur das merken, was rückgängig zu machen ist.
-
camper schrieb:
Du musst dir nur das merken, was rückgängig zu machen ist.
Aber wie soll ich das denn machen? Das Problem dabei ist ja, dass auch, wenn bereits ein Optimum gefunde wurde (also das korrekte Optimum), weitere Moeglichkeiten getestet werden. Und mir wuerde keine Moeglichkeit einfallen, fuer die anderen rekursionsstufen die Information bereit zu stellen, in wie fern die neuen Ergebnisse gespeichert werden sollen bzw. rueckgaengig gemacht werden sollen...
Ich habe auch schon ueberlegt, am Anfang eine Art Dreiecksmatrix zu uebergeben, sodass jede Rekursionsstufe ein eigenes Feld hat, um darin zu arbeiten. Aber das erspart mir ja noch kein dauerndes umkopieren.