Kombinatorische Optimierung, Informatik |
| 02.12.2010, 00:13 | AndyFP | Auf diesen Beitrag antworten » | ||||
| Kombinatorische Optimierung, Informatik Kombinatorische Optimierung, Informatik Hallo Mathefreaks, ich beschaeftige mich derzeit mit einem Optimierungsproblem. Eine Methode das globale Optimum zu finden ist Enumeration. Das funktioniert mit kleineren n ganz gut, der Problemraum wird aber sehr schnell zu gross, wenn n steigt. Ich schraenke daher den Problemraum mit Hilfe von Constraints ein. Die Werte sind in einer Matrix organisiert: Ebene: 0 value -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21 Ebene: 1 value -1 -1 -1 -1 4 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 Ebene: 2 value 0 -1 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 Ebene: 3 value -1 -1 -1 -1 -1 5 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 18 -1 20 -1 Ebene: 4 value 0 -1 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 Ebene: 5 value -1 -1 -1 -1 -1 5 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 18 -1 20 -1 Ebene: 6 value 0 -1 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 Ebene: 7 value -1 -1 -1 -1 -1 5 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 18 -1 20 -1 Ebene: 8 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 9 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 10 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 11 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 12 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 13 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 14 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 15 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 16 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 17 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 18 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 19 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Ebene: 20 value 0 -1 2 3 4 -1 -1 7 -1 9 10 11 12 13 -1 15 16 17 -1 19 -1 21 Ebene: 21 value -1 1 -1 -1 -1 5 6 -1 8 -1 -1 11 -1 13 14 -1 -1 17 18 -1 20 21 Die Ebene steht fuer die Tiefe des Baums, die enthaltenen Werte ergeben die Breite. -1 steht fuer einen ungueltigen Wert, die anderen Werte bezeichnen eine gueltige Option. Obige Matrix ergibt einen Suchbaum, der wie folgt beginnt: 21 4 6 0 2 (4) 15 0 2 4 15 usw.. Im linken Zweig kommt die 4 ein 2tes Mal vor, dieser Knoten ist daher nicht mehr Bestandteil des Suchraums, da jeder Wert in einem Zweig nur einmal vorkommen soll. Dieses Verfahren schraenkt den Suchraum von den urspruenglichen 22! Moeglichkeiten auf eine unbekannte Groesse ein. Wenn man die Matrix genauer studiert, kann man erkennen, dass nur ein Teil der Kombinationen Zweige bis zur letzten Ebene zulaesst, diese vollstaendingen Zweige beinhalten moegliche Loesungen des Optimierungsproblems. Meine Frage lautet nun: gibt es eine Moeglichkeit die Anzahl moeglicher Loesungen zu berechnen? Cheers, Andy Meine Ideen: Ich habe noch keinen Ansatz fuer die Loesung dieser Frage, ausser der Enumeration. Enumeration ist aber keine Loesung, denn das Ermitteln der Anzahl moeglicher Loesungen wuerde dann genauso lange dauern wie die Loesung des Optimierungsproblems selbst. Ziel ist jedoch vor Ausfuehrung des Algorithmus angeben zu koennen wie lange die Berechnung dauern wird und ob eine Loesung ueberhaupt in angemessener Zeit berechenbar ist. |
||||||
| 10.12.2010, 07:07 | AndyFP | Auf diesen Beitrag antworten » | ||||
Hallo zusammen, habe ich die Frage falsch gestellt, oder hat tatsaechlich niemand einen Ansatz fuer dieses Problem? Wenn's keine Loesung gibt ist das uebrigens auch eine brauchbare Antwort. Thanks, Andy |
||||||
| 10.12.2010, 09:48 | René Gruber | Auf diesen Beitrag antworten » | ||||
Meiner Ansicht nach trifft es das so ziemlich (obwohl ich heute diesen Thread zum ersten Mal sehe, also vor einer Woche "verpasst" habe): Vielleicht hättest du erstmal mit der exakten mathematischen Darstellung des eigentlichen Optimierungsproblem starten sollen, das hier
finde ich jedenfalls unzureichend: Geht es um eine Zielfunktion mit und irgendeine endliche Menge, womöglich Teilmenge von oder , usw. ... Stattdessen hast du dich gleich in technische Details der Lösungsfindung gestürzt - das ist total demotivierend, weil das ohne Kenntnis der Problemstellung kein Mensch schlüssig findet. |
||||||
| 11.12.2010, 02:14 | AndyFP | Auf diesen Beitrag antworten » | ||||
OK, danke! Leider kriege ich keine exakte mathematische Beschreibung hin, aber ich versuchs mal so: Wieviele Kombinationsmoeglichkeiten gibt es, wenn ich die Werte n unterschiedlich langer Vektoren miteinander kombinieren will, so daß jeder Wert nur einmal in einer solchen Kombination vorkommt. Wenn alle Vektoren voll besetzt waeren (mit m moeglichen Werten), dann gaebe es ja m! Möglichkeiten, wenn m >= n ist oder n! Möglichkeiten, wenn m < n ist. Der gesuchte Wert sollte also deutlich kleiner sein, wenn die Vektoren nur wenige Werte enthalten. Die Frage ist nur, wie man das ausrechnen koennte (wenn ueberhaupt). Andy PS: eigentlich sind die Vektoren alle gleich lang, aber nur ein Teil der Werte ist gueltig. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
