Kombinationen (Ansatz gesucht)



  • Ausgangssituation:

    Es gibt k Beförderungsmittel und n Passagiere. Jedes Beförderungsmittel bietet max. N Sitzplätze für diese Passagiere (Variante: es gibt k1 Beförderungsmittel mit N und k2 Beförderungsmittel mit M Sitzplätzen). Die Sitzplätze im Beförderungsmittel gelten als gleichwertig, spielen also bei der Zuordnung keine Rolle, entscheidend ist nur die Zuordnung eines Passagiers zu einem Beförderungsmittel. Es gibt maximal so viele Passagiere, wie es Sitze gibt, d.h. jeder Passagier findet einen Platz.

    Aktion (in einer Runde):

    Jeder Passagier soll einem Sitzplatz zugeordnet werden.

    Mathematische Aufgabe:

    Wieviele Möglichkeiten der Zuordnung gibt es?

    IT-Aufgabe:

    Wie sieht ein Algorithmus (bevorzugt in C++) aus, der alle Möglichkeiten, z.B. zur Berechnung der möglichen Fahrtrouten, die sich aus den Zuordnungen ergeben, "abklappert".

    Beispiele:

    1 Beförderungsmittel mit N=3, 1,2 oder 3 Passagiere: es gibt nur eine Zuordnungsmöglichkeit.
    Bei 1-3 Passagieren und 1 Beförderungsmittel ist es also einfach: 1 Option

    1 Passagier, 2 Beförderungsmittel (N=3): 2 Optionen
    a | -
    symmetrisch für beide Beförderungsmittel

    2 Passagiere, 2 Beförderungsmittel (N=3): 4 Optionen
    a | b
    a b | -
    symmetrisch für beide Beförderungsmittel

    3 Passagiere, 2 Beförderungsmittel (N=3): 8 Optionen
    a b | c
    a c | b
    b c | a
    a b c | -
    symmetrisch für beide Beförderungsmittel

    2 Beförderungsmittel mit N=3 und 5 Passagiere: es gibt 2 * 10 = 20 Zuordnungsmöglichkeiten. 10 ist hier 5 über 2.

    Die üblichen Möglichkeiten wie z.B. in http://www.schulminator.com/mathematik/kombinatorik (oder im Pascal-Dreieck) beschrieben, treffen diesen Vorgang sowohl für Beförderungsmittel als auch für Sitze nicht vollständig. Wie spielt die Zahl der Sitzplätze N (oder N,M bei verschiedenen Beförderungsmitteltypen) hinein?

    Hierzu finde ich keine Formel und kein passendes konkretes Beispiel, bitte euch daher um Hilfe.

    Nur zur Info: Es ist keine theoretische Schul-/Klausuraufgabe, sondern eine praktische Aufgabenstellung.



  • Eine geschlossene Formel kann ich auf die Schnelle leider nicht bieten (sofern es eine gibt). Am Computer könnte ich die Berechnung der Anzahl der Möglichkeiten nur auf ein NP-schweres Problem reduzieren:
    \sum\limits_{\substack{\{(n\_1,\ldots,n\_k): \\ n=\sum\limits_{i=1}^kn\_k \\ n\_i Die Summe geht also über die Menge aller möglichen Partitionierungen von nn, wobei solche ausgeschlossen werden müssen, welche die Anzahl der Sitzplätze NiN_i im ii-ten Beförderungsmittel übersteigen.

    Dein n=3n=3, k=2k=2, Ni=N=3N_i=N=3 Beispiel liefert die gültigen Partitionierungen {(3,0),(2,1),(1,2),(0,3)}\{(3,0),(2,1),(1,2),(0,3)\}, also 4 Terme:
    (3!3!0!+3!2!1!+3!1!2!+3!0!3!)=1+3+3+1=8\left(\frac{3!}{3!0!}+\frac{3!}{2!1!}+\frac{3!}{1!2!}+\frac{3!}{0!3!}\right)=1+3+3+1=8.
    Für n=5n=5, k=2k=2, Ni=N=3N_i=N=3:
    5!(13!2!+13!2!)=205!\left(\frac{1}{3!2!}+\frac{1}{3!2!}\right)=20.



  • @Jodocus: Danke! Wie würdest du das abklappern, oder geht das gar nicht? Z.B. bis 3 Fahrzeuge á 3 Sitze mit 0 ... n Passagieren.



  • Zumindest die Anzahl der Kombinationen kann man relativ einfach mit einem danamischen Programm ausrechnen, geeignet umgebaut kann man damit natürlich auch alle zuordnungen ausrechnen.

    Edit: Allerdings wird das sicher sehr bald sehr viel... Und den letzten schritt habe ich icht verstanden. Inwiefern ergeben sich aus der zuordnung fahrtwege?

    Edit2: auf jeden fall würde ich so ein Problem lieber als Ganzzahliges lineares Programm formulieren und dann durch einen solver jagen, das ist wahrscheinlich irdentlich schneller als brute force und noch dazu einfach zu machen.



  • Zumindest die Anzahl der Kombinationen kann man relativ einfach mit einem dynamischen Programm ausrechnen, geeignet umgebaut kann man damit natürlich auch alle zuordnungen ausrechnen.

    Also doch nicht NP-schwer? Existiert ein konkretes Beispiel / ein konkreter Algorithmus, an dem man sich beim Code orientiern kann?

    @Jester: Berechnung der möglichen Fahrtrouten <== dieses Thema ist bereits in allgemeiner Form vollständig gelöst. Es geht nur noch um alle möglichen Assignments zwischen Fahrzeugen und Passagieren. Bei Heuristiken findet man nämlich nicht alle Möglichkleiten, sondern man wählt nach einem bestimmten Verfahren aus. Dabei kann man prinzipiell am konkretisierbaren Optimum vorbei laufen bzw. man weiß nicht, wie gut man wirklich ist. Zumindest für einfache Fälle, die man mit heutiger Technik noch berechnen kann, möchte ich das wissen, z.B. 2 Fahrzeuge und 5 Passagiere mal alle möglichen Fahrwege. Das sind 20 (Formel oben) * (90 (für N=3) + 6 (für N=2) = 1920 Optionen.

    Mir fehlt allerdings noch der konkrete Code, diese 20 Assignments durchzugehen. 🙄

    C++ bietet da ja einiges, z.B. Permutation:

    do
    		{
    			// hier erfolgt Aktion
    			// z.B. Wegstreckenberechnungen, Bewertung, Speicherung der Ergebnisse
    		} while (std::next_permutation(container.begin(), container.end()));
    

    Welcher STL code wäre für obigen Fall geeignet?
    Vielleicht sollte man das Thema nach C++ verschieben?



  • Die Idee für den Algorithmus ist in etwa die folgende:

    Angenommen, wir haben n Personen und k Autos mit jeweils N Plätzen. Bezeichne T[i,j] die Anzahl der Möglichkeiten i Leute auf j Autos zu verteilen. Was Dich interessiert, ist T[n,k].

    Was offensichtlich gilt, ist T[i,1] = 1, falls i<=N, und T[i,1] = 0 falls i>N.
    Außerdem gilt folgende Rekurrenz für (i,j) mit j>1: T[i,j] = \sum_{k=0}^{\min\{N,i\}} \binom{i}{k} \cdot T[i-k,j-1]

    Wie kann man nämlich Leute in das j-te Auto stecken? Man kann von 0 bis max{i,N}\max \{i,N\} Leute reinstecken. Und für jeden Wert k in diesem Bereich gibt es (ik)\binom{i}{k} Möglichkeiten diese k Leute unter den i verbleibenden Leuten auszuwählen. Und wieviele Gesamtlösungen ergeben sich daraus? Na genau die Anzahl der Möglichkeiten dies zu tun multipliziert damit, wie man die verbleibenden i-k Laute auf die verbleibenden j-1 Autos verteilen kann. Genau das berechnet die Formel.

    Anzumerken ist, dass immer noch Lösungen doppelt gezählt werden, weil man dieselben Zuweisungen allerdings mit permutierten Autos noch mehrfach bekommt, will man das vermeiden, muss man einfach die endgültige Zahl T[n,k] noch durch k! teilen (das ist die Anzahl der Möglichkeiten die Autos zu permutieren). Der Trick ist jetzt natürlich das nicht als Rekursion hinzuschreiben, sondern T[i,j] als Array zu implementieren. Die Rekurrenz greift immer nur auf Einträge mit kleineren Indizes zu, sodass man die Einträge einfach zeilenweise nacheinander ausfüllen kann. Das sollten nicht mehr als ne Handvoll Zeilen Code werden, aber darauf hab ich grad keine Lust. Wenn es Schwierigkeiten gibt, frag gerne nach.

    edit: aufgrund der Zahlengröße würde ich eine library wie GMP oder auch Java nebst BigInteger empfehlen.

    Wenn Du nun die Zuweisungen echt haben willst, musst Du halt zusätzlich in jeder Zelle alle möglichen Teilzuweisungen mitspeichern und statt * zu rechnen jede Teilzuweisung aus der Vorgängerzelle mit jeder Möglichkeit das j-te Auto zu beladen kombinieren. Dann wachsen die Mengen allerdings sehr schnell an, und Du wirst wahrscheinlich nicht glücklich werden.

    Zu guter Letzt: Es ist ein Irrglaube zu denken es sei eine gute Lösung man habe ein Problem (die Tourenplanung) gelöst und nun verwendet man das einfach als Blackbox und legt ein Problem außenrum und zählt alle Zuweisungen auf und wendet dann jeweils die Lösung für das Tourenplanungsproblem an. In vielen Fällen lässt sich das besser lösen, indem man die Zuweisung so konstruiert, dass sie die Zielfunktion direkt minimiert. Gerade aus praktischer Sicht und aufgrund der Einfachheit möchte ich Dir hier nochmal die (gemischt) ganzzahlige lineare Programmierung empfehlen. Das funktioniert gerade bei solchen Tourplanungs- und Zuweisungsproblem überraschend gut. Damit ich dazu was sagen kann, müsstest Du aber was dazu sagen wie der Tourplanungsteil genau aussieht.



  • Erhard Henkes schrieb:

    Zumindest die Anzahl der Kombinationen kann man relativ einfach mit einem dynamischen Programm ausrechnen, geeignet umgebaut kann man damit natürlich auch alle zuordnungen ausrechnen.

    Also doch nicht NP-schwer? Existiert ein konkretes Beispiel / ein konkreter Algorithmus, an dem man sich beim Code orientiern kann?

    Ich bezog mich mit meiner Aussage über NP einfach auf die Tatsache, dass, wenn man die Anzahl aller Möglichkeiten aus meiner Formel mit einem Computer ausrechnen möchte, man alle Partitionierungen bestimmen müsste, was (so zumindest laut Wikipedia) ein NP-vollständiges Problem wäre. Ich möchte mich aber nicht zu weit aus dem Fenster lehnen, da (theoretische) Informatik nicht mein Gebiet ist. Vielleicht gibt es auch eine einfachere Formel als meine.

    Ein Algorithmus muss einfach nur systematisch durch alle Möglichkeiten durchiterieren. Ich habe hier mal einen rekursiven Vorschlag:

    #include <iostream>
    #include <vector>
    
    int main() {
    	using std::size_t;
    	size_t n = 5, k = 3; // distribute n distinguishable persons on k buses
    
    	std::vector<std::vector<size_t>> buses(k);
    	std::vector<size_t> bus_sizes(buses.size());
    	for(auto& bus_size : bus_sizes) bus_size = 3; // how large is each bus?
    	for(size_t n = 0; n < buses.size(); ++n) buses[n].reserve(bus_sizes[n]);
    
    	size_t start_person = 0;
    
    	auto comb = [&buses, &bus_sizes, n](size_t start_person, const auto& comb) -> void {
    		if(start_person == n) {
    			// finished, output bus distributions!
    			std::cout << '|';
    			for(size_t i = 0; i < buses.size(); ++i) {
    				for(size_t j = 0; j < buses[i].size(); ++j) std::cout << buses[i][j] << ' ';
    				std::cout << '|';
    			}
    			std::cout << '\n';
    		}
    		else {
    			size_t bus = 0;
    			for(; bus < buses.size(); ++bus) {
    				if(buses[bus].size() < bus_sizes[bus]) {
    					buses[bus].push_back(start_person); // place person i in bus
    					comb(start_person + 1, comb);
    					buses[bus].pop_back();
    				}
    			}
    			if(bus == buses.size()) { /* more people than buses :( EXCEPTION!!!! */ }
    		}
    	};
    
    	comb(start_person, comb);
    }
    

    Der Code ist jetzt nur aus dem Ärmel geschüttelt und Rekursion sicher nicht die beste Wahl, aber evtl. kannst du daraus ja was machen.



  • Das Aufzählen ist nicht wirklich NP-vollständig (ich glaube auch nicht, dass Wikipedia das irgendwo sagt). Es ist nur einfach so, dass es unglaublich viele Lösungen gibt, und man alleine deshalb keinen effizienten Algorithmus erwarten kann. Das Problem ist nicht inherent schwierig, die Ausgabe ist nur einfach riesig, und natürlich kann kein Programm schneller sein als die Zeit, die es benötigt um sein Resultat auszugeben.



  • Jester schrieb:

    Das Aufzählen ist nicht wirklich NP-vollständig (ich glaube auch nicht, dass Wikipedia das irgendwo sagt). Es ist nur einfach so, dass es unglaublich viele Lösungen gibt, und man alleine deshalb keinen effizienten Algorithmus erwarten kann. Das Problem ist nicht inherent schwierig, die Ausgabe ist nur einfach riesig, und natürlich kann kein Programm schneller sein als die Zeit, die es benötigt um sein Resultat auszugeben.

    Ich meinte dabei wirklich nur meine Formel aus Post #2, welche alle gültigen Partitionierungen braucht. Wenn man die in einem Computer umsetzen wollte, müsste man diese ja bestimmen, was hier als NP-vollständiges Problem bezeichnet wird. Das bloße Aufzählen aller Möglichkeiten ist natürlich deutlich schneller. Trotzdem bleibt die Frage, ob man eine analytisch geschlossene Formel (ohne Rekursionen oder Summen) für die Anzahl der Möglichkeiten angeben kann.



  • Oh, da steht in der Tat quatsch in Wikipedia. Folge der Referenz [1] aus Wikipedia, die als Quelle dafür angegeben wird. Dort steht die Definition des Problems PARTITION, und das tut was anderes. Nämlich gegeben eine Menge von Zahlen, partitioniere sie in zwei Teile, sodass die Summe beider Teile gleich ist. Das ist was anderes.

    edit: man merkt das alleine schon daran, dass sich die Komplexitätstheorie mit Entscheidungs- und manchmal noch mit Optimierungsproblemen beschäftigt. Das hier ist aber ein Aufzählproblem, da macht die klassische Komplexitätstheorie keine Aussagen dazu.



  • Jester schrieb:

    Oh, da steht in der Tat quatsch in Wikipedia. Folge der Referenz [1] aus Wikipedia, die als Quelle dafür angegeben wird. Dort steht die Definition des Problems PARTITION, und das tut was anderes. Nämlich gegeben eine Menge von Zahlen, partitioniere sie in zwei Teile, sodass die Summe beider Teile gleich ist. Das ist was anderes.

    Danke für den Hinweis.



  • @Jodocus: Danke für den Code-Vorschlag. Das hilft sehr. 🙂


Log in to reply