Optimierung
-
Noch eine Frage:
Gibt es in C++ eine Funktion die mir eine Reihenfolge von Variablen so sortiert, dass deren Summe minimal ist ??
D.h. die Variabeln nehmen andere Werte an, je nachdem wo sie in der Reihe stehn!
z.B. A B C D
wenn A vor dem B steht nimmt es den Wert 20 anz.B. B A C D
steht A hinter dem B nimmt es den Wert 40 anGibt es so etwas in c++ ???
Danke
Gruß
Neo
-
du koenntest fuer jedes flugzeug alle moeglichen nachfolgenden flugzeuge berechnen, fuer die wieder das gleiche... bis in die tiefe ausschoepfen. dieser brute force algorithmus hat ne grauenhafte laufzeit, aber man muss nicht viel ueberlegen.
schau dir mal en.wikipedia.org/wiki/Dijkstra's_algorithm an.
-
Hi
man könnte auf sowas algs aus der KI los lassen. z.B. einen gewichteten Suchbaum. was aber ab einer bestimmten komplexität (die leider sehr schnell eintritt) verdammt lange dauert. Falls da nicht noch gewisse randbedingungen mit berücksichtigt werden müsste. ( z.B. der Flieger muss inerhalb der nächsten 30 min landen sonst gibts 175 Tote )
Auch stellt sich die frage wie optimal die sortierung sein soll. muss die beste lösung gesucht werden, oder reicht es wenn ein bistimtens zeitkriterium erfüllt wird ( z.B. 20 Flugzeuge inerhalb von 30 Min )
Anderemöglichkeit währe ein art Agentensystem, das durch mehr oder weniger wilkürliche mütationen versucht die reihenfolge zu optimieren. Da hat unser Dozent mal eine Optimierung für Spedition umgesetzt.
Das problem müsste sich sicherlich auch als Netzwerk darstellen lassen. Und somit könnte man algs aus der Grapenteorie drauf los lassen ( fals das nicht wieder auf einen suchbaum rauslaufen würde )
gruss
-
Ich denke, daß das Problem NP-vollständig ist. Brauchst Du die optimale Lösung? Oder reicht eine gute?
In dem Fall könntest Du zum Beispiel ne zufällige Reihenfolge wählen und solange Positionen tauschen wie es besser wird. Das Ergebnis ist dann schonmal nicht ganz schlecht. Das wiederholst Du dann einige Male (100 oder 1000 mal) und nimmst davon die beste Variante.
MfG Jester
-
um die optimale lösung zu finden musst du alle möglichkeiten permutieren => n! . oben stehen schon ein paar ansätze, um nicht die optimale, aber zumindenst keine ganz miese zu finden.
-
Also laut Vorgabe soll ich die optimale Lösung finden !! Aber ein "gute" würde mir auch schon reichen !
Gruß
-
mata^ schrieb:
um die optimale lösung zu finden musst du alle möglichkeiten permutieren => n!
Bist Du sicher? Oder ist das nur ne Vermutung?
Wenn ich n Zahlen so anordenen will, daß n*zahl_1 + (n-1)*zahl_2 +...+1*zahl_n minimal wird, dann gibt's dafür zwar auch n! Möglichkeiten. Trotzdem kann man in O(n*log n) sortieren.
Ich denke aber auch, daß es nicht viel besser als O(n!) geht. Vielleicht exponentiell, aber viel schneller würde mich wundern. Es sei denn, es gibt noch Informationen, die wir nicht wissen.
Nehmen wir zum Beispiel an: es gibt A und B, jeweils 3 Stück. Wechsel zwischen Buchstaben sind teuer, Gleiche hintereinander ist günstig.
Dann ist entweder AAABBB oder BBBAAA optimal. Je nachdem wierum der Wechsel günstiger ist.
@OP: Kannst Du vielleicht noch mehr Infos rausrücken?
-
Also wichtig bei dieser Geschichte ist die Abhängigkeit der einzelnen Variablen von einander!
Man muß sich das so vorstellen:
Es gibt 3 Typen von Flugzeugen: Typ A, Typ B und Typ C !!
Und die müssen bestimmte Abstände beim Landeanflug einhalten und damit entstehen feste Zeitintervalle!
Beispiel:
Fliegt A hinter B, benötigt diese Kombination 50sec
Fliegt aber B hinter A brauchen sie nur 40sec, da der Sicherheitsabstand zwischen von B auf A geringer sein muß als A auf B !!Ich soll nun eine zufällige Reihenfolge von Fliegern so sortieren, das möglichst geringe Mindestabstände einzuhalten sind!
D.h. das zum Beispiel in 60min möglichst viele Flieger landen können und sie dementsprechend angeordnet sein müssen!Ich hoffe, ich konnt euch mein Problem etwas näher bringen und bin weiterhin dankbar für eure Tipps !
Gruß
Neo
-
Ein paar zusätzliche infos währen würklich nicht schlecht.
Wieviele Flugzeugtypen gibt es, und wieveile flugzeuge müssen verarbeitet werden? zur ungefähren abschätzung ob sich das ggf mit einem suchbaum in einer angemessenen zeit realiesieren läst.
Wobei sich das bei einer entsprechenden optimierung ggf sogar soweit verkürzen lässt, das nicht alle pfade bis zum schluss durchgerechnet werden müssen. Pfade bie schon mehr zeitbrauchen, aber wo noch nicht alle flugzeuge unten sind gegenüber der bisher besten lösung, brauchen nicht weiter betrachtet zu werden (zeitersparrniss). Da ich ja den Baum nicht vollständig expandieren muss, um die suche durchführen zu können, sondern im prinzip mir nur 2 äste davon merken muss (einer wird dann entsprechend so manipoliert, das er durch die endpunkte des Baumswandert), ist das speicherpoblem nicht gegeben.
Nur kurtz zum aufwand. bei sagen wir mal 5 Flugzeugtypen und 30 zu landenden Flugzeugen ergeben sich WENIGER als 5^30 mögliche kombinationen die im schlimsten falle erst mal berechnet und geprüft werden müssen. (die anzahl wird sich dadurch reduziehren, da nur eine bestimmte anzhal von flugzeugen je type existiert.)
gruss
-
Ich muss mich jetzt wohl korigieren.
Wieveile Flugzeuge von den einzelnen typen gibt es die man runterbringen muss?
Oder ist die frage wieveile flugzeuge kann man inerhalb einer Stunde runterbekommen?
Zumindestens beim Suchbaum verändert sich da ein bischen was. zumindestens bei der Suchtiefe und den abbruchkriterien. Auch ergeben sich da ganz andere Optimierungsmöglichkeiten wenn die Flugzeuganzahl je type egal ist. ggf läst sich dann sowas sogar noch von Hand expandieren und oder eine optimale wiederholungsfolge finden.gruss
-
Da ich mit Flugzeugklassen arbeite gibt es im Prinzip nur 3 verschiedene Flugzeugtypen: Heavy, Medium und Small !
Das Programm soll dann im Prinzip ein Feld generieren können mit einer bestimmten Zahl von Flugzeugen, so zwischen 10 und 200 vielleicht! Wieviele von jedem Typ is dabei willkürlich !
Für diese Menge soll dann die optimale Reihefolge bstimmt werden, also die minimale Zeit die sie benötigen um alle zu landen!
Ziel ist es also die Reihenfolge so zu verändern das die Summe der Zeit minimal wird!
-
Und wie sind die Zeitunterschiede? Das ist doch die wichtige Frage.
Wenn alle Paare gleich teuer sind, dann ist jede Reihenfolge optimal.Ohne die genauen Kostenangaben können wir Dir nicht genauer sagen, wie schwierig das Problem ist.
-
Termite schrieb:
ergeben sich WENIGER als 5^30 mögliche kombinationen die im schlimsten falle erst mal berechnet und geprüft werden müssen. (die anzahl wird sich dadurch reduziehren, da nur eine bestimmte anzhal von flugzeugen je type existiert.)
Schon, nennt sich Backtracking, kann man beim TSP (Traveling Salesman Problem) auch einsetzen. Trotzdem ist TSP NP-vollständig.
-
Die Zeitintervalle werde ich nachher mal hier posten!
Die sollen aber auch veränderbar sein!sagen wir folgende Reihenfolge: A >> B >> C >> A >> C >> B
B landet zuerst!
dann folgt im Abstand von 20sec C, d.h C auf B ist 20 sec,
dann folgt im Abstand von 15sec A, d.h A auf C ist 15 sec,
dann folgt im Abstand von 30sec C, d.h C auf A ist 30 sec,
dann folgt im Abstand von 35sec B, d.h B auf C ist 35sec,
dann folgt im Abstand von 10sec A, d.h A auf B ist 10 sec !!!Summe wäre 110sec !!
Und jetzt möchte ich die Reihenfolge so ändern das die Summe geringer wird!
Man sieht ja das, z.B. A auf C nur 15sec braucht, wogegen C auf A 30sec braucht!
Das sind jetzt nur fiktive Werte, die reellen hab ich gerade nicht zur Hand, kann ich aber gerne mal posten !
-
Ja, und vergiß bitte auch nicht alle Kombinationen zu posten:
Was ist mit AC, AA etc.?
Es gibt 9 verschiedene Kombinationen. Wenn wir nicht für alle die Werte kennen ist es witzlos.
-
Unten seht ihr einen Ausschnitt aus dem Programm:
Gibt die Typen 1,2,3 !
Und bei Summe steht dann immer das Zeitintervall....
12 >> 82
21 >> 146
31 >> 167
13 >> 78
...for (i=0; i <=9; i++)
{
if (flieger [i] == 1 && flieger [i+1] == 2)
{
Summe = Summe + 82;
}
else if (flieger [i] == 2 && flieger [i+1] == 1)
{
Summe = Summe + 146;
}
else if (flieger [i] == 3 && flieger [i+1] == 1)
{
Summe = Summe + 167;
}
else if (flieger [i] == 1 && flieger [i+1] == 3)
{
Summe = Summe + 78;
}
else if (flieger [i] == 3 && flieger [i+1] == 2)
{
Summe = Summe + 138;
}
else if (flieger [i] == 2 && flieger [i+1] == 3)
{
Summe = Summe + 78;
}
else if (flieger [i] == 1 && flieger [i+1] == 1)
{
Summe = Summe + 82;
}
else if (flieger [i] == 2 && flieger [i+1] == 2)
{
Summe = Summe + 82;
}
else if (flieger [i] == 3 && flieger [i+1] == 3)
{
Summe = Summe + 167;
}
}