Summe eingschränkter Summanden < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo Ihr!
Ich suche die Anzahl a aller Möglichkeiten eine Zahl x in die minimale Anzahl an Summanden (s), der maximalen Größe g auszudrücken. Dabei herrscht kein Kommutativ-Gesetz. (s kann berechnet werden)
Die Anzahl der Summanden s ist schnell berechnet. Ist die Zahl x bspw. 7, und die höchste Zahl eines Summanden g = 3, so müssen genau ceil(7/3) = 3 Summanden existieren. (ceil = aufrunden)
Die Summanden-Terme um auf diese 7 zu kommen, können sein:
3+3+1
3+2+2
3+1+3
2+3+2
2+2+3
1+3+3
Die Anzahl a ist also 6, da 6 verschiedene Formeln existieren.
Ist (x=8,g=3) so gilt: s=ceil(8/3)=3
3+3+2
3+2+3
2+3+3
a = 3, da 3 verschiedene Formeln existieren.
Ist (x=9,g=3) so gilt: s=ceil(9/3)=3
3+3+3
a = 1, da nur diese eine Formel existiert.
Ist (x=5,g=3) so gilt: s=ceil(5/3)=2
3+2
2+3
a = 2
Gesucht ist also die Formel für a (aus x, g). Vielleicht seh ich den Wald vor Bäumen nicht, aber glaubt mir ich suche schon 'ne Ewigkeit.
Diese Formel benötige ich für meine Abschlussarbeit. Leider komme ich alleine nicht weiter. Vielleicht sucht irgendwann mal noch einer danach. Die Formel ist für das CVRP / VRP (Vehicle Routing Problem) und spiegelt die Anzahl aller Möglichkeiten der Positionen der Depots in einer Rundreise wieder. :-/
Weitere TAGs: Handlungsreisender, TSP, Capacitated
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Liberius,
Ich habe jetzt mal versucht etwas Allgemeine(re)s für [mm]a(x,g)\![/mm] rauszubekommen und habe dazu ein kleines Programm geschrieben (siehe Anhang). Wenn man die Ausgaben des Programms z.B. für alle x von 1 bis 10 betrachtet, entdeckt man folgende drei Regelmäßigkeiten(, wobei man auf die ersten zwei auch so kommen kann):
1.) [mm]a(kg, g) = 1; k \in \mathbb{N}[/mm]
2.) [mm]a(x, x-1) = x-1\![/mm]
3.) [mm]a(3+2k,2+k) = 2; k \in \{0\}\cup\mathbb{N}[/mm]
1. gilt wegen [mm]\tfrac{kg}{g}=k[/mm] wofür es genau eine Möglichkeit, nämlich [mm]kg\![/mm], gibt.
Bei 2. müssen es nach deiner Formel immer 2 Summanden sein. D.h. man zählt nach folgendem Muster: x-1+1 = x, x-2 + 2= x, ... x-(x-1) + x-1 = x. Das wären dann x-1 Möglichkeiten.
Wie man 3. beweisen kann, weiß ich nicht. Die Formel drängt sich einem jedoch auf, wenn man sich die Ergebnisse des Programms anschaut. 
Wie die allgemeine Formel aussieht, kann ich dir auch nicht sagen. Siehe dir mal die restliche Ausgabe meines Programms an, vielleicht entdeckst du ja noch 'was. Oder lass' das Programm für größere x-Werte laufen und versuche dann irgendwas zu entdecken. ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: txt) [nicht öffentlich]
Anhang Nr. 2 (Typ: txt) [nicht öffentlich]
Anhang Nr. 3 (Typ: py) [nicht öffentlich]
Anhang Nr. 4 (Typ: py) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:31 Fr 17.10.2008 | | Autor: | Liberius |
Spitze Karl! Deine Programme liefern ja wirklich genau das gesuchte a. Ich habe mal bis zur x=10 die n003.py->sums.txt ausgedruckt. Leider konnte ich keine allgemein gültige Formel finden.
Ein richtiger Ansatz ist sicherlich a = x - (((x % g) * 2) - 1) [+-?]
Wie du schon sagtest ist
a=1, wenn g=x
a=x-1, wenn g=x-1
Das hat mich auf die Idee gebracht, den Restwert zu benutzen, also (x%g). Man muss aber definitiv nochmals x und g in der Formel unterbringen, da bei a(8, 6) und a(8, 3) der gleiche Restwert aber ein anderes Resultat herauskommt.
Hmm. Na immerhin kann ich schreiben, dass keine einfache Formel für das Resultat offensichtlich ist.
Also: Vielen Dank nochmals
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:20 Do 23.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
