Optimale Lösung mit Vorbedingungen finden |
| 14.02.2008, 17:42 | ChristophM | Auf diesen Beitrag antworten » | ||
| Optimale Lösung mit Vorbedingungen finden hallo erstmal, dies ist ja mein erster Eintrag hier im Forum 
Um gleich zur Sache zu kommen, ich habe ein mathematisches Problem, dass ich gerne lösen möchte, aber trotz einer Woche grübeln und Anfragen an Mathestudenten bzw. -dozenten hab ich immernoch keine Lösung. Eine Möglichkeit wäre ein Greedy Algorithmus, allerdings wäre das nur die Notlösung, denn der findet nur ein gutes Ergebnis, aber nicht unbedingt das Beste. Zum Problem: (sehr genaue Beschreibung im pdf im Anhang) Es gibt x verschiedene Buchstaben (A,B,C,D,E.....) und y verschiedene Formen (roter Kreis, blauer Kreis, grüner Kreis,....). Von jedem Buchstaben und von jedem Kreis gibt es eine bestimmte Anzahl, z.B. 5*A, 3*B, 7*C und 4 * roter Kreis, 5 * blauer Kreis und 1 * grüner Kreis. Dazu gibt es dann eine Zuordnungstabelle, die jeder Buchstaben/Form Kombination einen Punktewert zuordnet (für ein Beispiel, siehe pdf). Ziel ist es jetzt, den maximalen Punktestand zu errechnen den man erreichen kann und die Kombination, die diesen Punktestand erzeugt anzeigen zu lassen. Jetzt bin ich auf eure Ideen/Denkanstösse/Ansätze gespannt, frohes nachdenken
Grüße Christoph Anhang: www.abi2007-bzm.de/Problembeschreibung.pdf |
||||
| 14.02.2008, 19:29 | Mazze | Auf diesen Beitrag antworten » | ||
Greedy wird hier nicht funktionieren weil es keine optimale Substruktur gibt. edit2 : Mist Problem verlesen ich schreib was neues edit3 : So erstmal sollte man den Problemraum ordentlich beschreiben. Es gibt eine Bewertungsmatrix M die den Paaren (Buchstabe,Form) einen Wert zu weisst. (Ich geh davon aus das du eine endliche Buchstaben und Formenmenge hast). Dann hast Du noch gewisse Anzahlen von Buchstaben und Formen die aufsummiert das gleiche Ergeben. Also hast Du zwei Tupel mit den Anzahlen. Das ganze Skalliert natürlich überhaupt nicht. Wenn man alle Möglichkeiten (was Prinzipiell geht) durchgeht wird das sehr schnell sehr Aufwändig. Willst Du eine möglichst optimale Lösung haben? edit4: Nimmt man an wir haben ein geordnetes Feld (nach Buchstaben) will man eine optimale Permutation finden. Man muss nur noch ein zweites Feld anlegen wo dann die Punkte bezüglich der zuordnung der Permutation drin stehen. Dann nimmt man sich das Feld mit der höchsten Punktzahl. Man muss aber alle permutationen Berechnen was Permutationen sind. |
||||
| 14.02.2008, 22:28 | Silencer | Auf diesen Beitrag antworten » | ||
hm, ich denke, das ist ein Problem, welches man mit der Suche nach einem maximalen Fluss in polynomieller Zeit suchen kann. Hilft dir das schon weiter? MfG |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
