petter2 Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 Hallo! Ich habe zwei Listen: A 1 B 2 C 1 D 3 E 0 F 0 (natürlich deutlich länger) (Anzahl gleich Summe aller Zahlen in der 1. Liste) AB AC AD AF BC BD EC Jetzt muss hinter jede Zeile der zweiten Liste ein Buchstabe stehen. Dabei dürfen aber die in der ersten Liste genannten Limits nicht unterschritten werden. Wenn das Limit 0 ist, muss der andere Buchstabe ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Buchstabe vorkommt, entspricht. Die Datenstruktur habe ich wie folgt interpretiert: $limits[X][0] Limit $limits[X][1] Buchstabe $limits[X][2] Anzahl der Vorkommnisse $limits[X][3] Quotient Limit durch Anzahl $verbindung[X][0] erster Buchstabe $verbindung[X][1] zweiter Buchstabe $verbindung[X][2] Lösung Ich bin jetzt schon seit Tagen am Rumprobieren, aber irgendwie bekomme ich es nicht hin. Ich lande immer in einer Dauerschleife. Es wäre sehr nett, wenn mir da jemand helfen könnte! Vielen Dank! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 Wenn ich das richtig verstehe, dann weißt Du, dass Du in der Liste, die mit A beginnt, max einen Buchstaben hinzufügen kannst und nimmst dann eben aus der Liste alle Elemente, die eben nicht A sind. Diese Listen lassen sich rekursiv aufbauen, nimm ein Element der Liste, nimm die Liste ohne diese Elemente und kombiniere dann. Aber Achtung, die Laufzeit dieses Verfahren wächst exponentiell mit der Größe der Liste. Generell bzw. bei sehr großen Datenmengen würde man einen Simplexalgorithmus oder genetischen Algorithmus verwenden und sich mit einer hinreichend guten Lösung zufrieden geben und eben nicht die optimale Lösung anstreben, da dies in keinem Verhältnis zum Rechenaufwand steht. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 13. November 2011 Autor Teilen Geschrieben 13. November 2011 Vielen Dank für die Antwort! 1700 Einträge hat die erste Liste, 2700 die zweite. Aber die vorgehensweise verstehe ich nicht. D muss z.B. 3 mal vorkommen (die Zahl ist exakt - es gibt eine optimale Lösung bei der alles aufgeht) Bei dem Beispiel möchte ich dann z.B. diese Ausgabe: AB: B AD: D AC: C AF: A BD: D BC: B ED: D Ich habe übrigens beim ersten Post B und C vertauscht, hier sind die richtigen Verbindungen... Vielen Dank! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 (bearbeitet) Gib bitte einmal den Algorithmus (in Worten) an, wie die Listen kombiniert werden müssen. Denn auf Grund Deines Beispiels ist nicht klar, was und wie kombiniert werden muss. Bei Deinem Ergebnis jetzt schreibst Du hinter ein Element auf der zweiten Liste ein Element aus der ersten: AB => B B hat in Deiner ersten Liste eine 2 als Suffix, es scheint aber bei dem Ergebnis unerheblich zu sein, was dort angegeben ist, denn Deine Lösung erhält immer genau einen Buchstaben. Aber die vorgehensweise verstehe ich nicht. D muss z.B. 3 mal vorkommen (die Zahl ist exakt - es gibt eine optimale Lösung bei der alles aufgeht) Nur weil eine exakte Lösung existiert, kann durchaus das Problem auftreten, dass es sehr schwierig ist diese zu bestimmen. In vielen Fällen sind approximative / heuristische Verfahren nicht schlechter als kombinatorische. Weiterhin möchte ich Dir den Tip geben, dass Du nicht hier an einem Buchstabenbeispiel, das nicht unbedingt gut verständlich ist, das Problem bzw. Dein Ziel beschreibst, sondern das zugrunde liegende Problem, denn in den meisten Fällen kann man durch eine Änderung des Algorithmus (und Datenstruktur) das Problem oft effizienter lösen. Beschreibe also die Problemstellung, d.h. in Deinem Fall was ist das inhaltliche Problem mit den Listen Bearbeitet 13. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 13. November 2011 Autor Teilen Geschrieben 13. November 2011 In der ersten Liste wird angegeben, wie oft der jeweilige Buchstabe als Lösung in der zweiten Reihe existieren darf. Das alles ist eine Aufgabe mit eigentlich Namen stadt Buchstaben, z. B. Tom 1 Peter 2 Lisa 0 Tom Peter : Peter Lisa Peter : Peter Tom Lisa : Tom Zuerst kann man die eindeutigen Fälle bestimmen: Wenn das Limit 0 ist (bei jeder Festlegung wird aktuallisiert), muss der andere Name ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Name vorkommt, entspricht (z.B. Peter, 2 Einträge, Limit 2). Vielen Dank! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 13. November 2011 Autor Teilen Geschrieben 13. November 2011 Die Aufgabenstellung ist: Jeder Schüler hat ein individuelles Limit an Aufgaben, die er erledigen muss (limits.txt). Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. Geben Sie dazu für jede Zeile an, welcher Schüler die Aufgabe zugeteilt bekommen soll. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 13. November 2011 Autor Teilen Geschrieben 13. November 2011 meine Datenstruktur: $limits[X][0] Limit $limits[X][1] Name des Schülers $limits[X][2] Anzahl der Aufgaben $limits[X][3] Quotient Limit durch Aufgabenanzahl $verbindung[X][0] erster Name $verbindung[X][1] zweiter Name $verbindung[X][2] wird bearbeitet von... Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 (bearbeitet) Das ist doch schon etwas verständlicher. Ich formuliere das mal etwas abstrakter: Jeder Schüler hat ein individuelles Limit an Aufgaben, die er erledigen muss (limits.txt). D.h. Du hast für jeden Schüler eine maximale Anzahl an Aufgaben, die erreicht werden kann. Also ein Schüler S, hat k Aufgaben, d.h. sofern der Schüler <= k Aufgaben erledigt, ist das eine gültige Lösung Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. D.h. Du hast hier n Aufgaben. Hier ist jetzt in der Formulierung nicht klar, ob hier eine Zuordnung von Aufgabe zu Schüler existiert, d.h. Du hast die Information, welche Aufgabe welcher Schüler erledigen soll. So wie ich das verstehe existiert hier nur eine Liste von Aufgaben Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. Geben Sie dazu für jede Zeile an, welcher Schüler die Aufgabe zugeteilt bekommen soll. Das Ziel ist also, die n Aufgaben so auf die Schüler zu verteilen, dass a) jeder <= k Aufgaben erledigt und jeder möglichst gleich viel zu tun hat und c) keine Aufgabe doppelt vergeben wird. Du hast somit im Grunde drei Constraints, die die Lösung einschränken und die zu beachten sind. Ich kann hier direkt sagen, dass eine Lösung, die durch das Bestimmen jeder möglichen Kombination berechnet wird, extrem schlecht funktionieren wird, weil mehrere gültige Lösungen existieren können. Außerdem bei einer Listengröße > 1000 Elemente wird das bestimmen der Lösungen extrem ineffizient funktionieren. Ich rate deshalb das ganze über ein heuristisches Verfahren zu lösen Genetischer Algorithmus Man kann das Problem als binäres Problem (Schüler S löst Aufgabe j und kein weiterer Schüler darf dann j lösen) aufbauen und dann über einen genetischen Algorithmus lösen, was durchaus zu einer recht guten Lösung führt. Eine Lösung wie "Probiere alle möglichen Kombinationen durch" wird hier zu extremer Laufzeit führen. Rein formal kann jeder Schüler jede Aufgabe lösen, so lange er eben sein Limit (maximale Anzahl an Aufgaben) noch nicht erreicht hat und nicht jemand anderes diese Aufgabe schon bearbeitet. Um nun möglichst die Aufgabe so zu verteilen, dass alle gleich viel erledigen muss man so etwas wie die "mittlere Aufgabenanzahl" bestimmen und eben bei jedem Schüler schauen, wie weit seine aktuelle Anzahl von dieser mittleren Anzahl abweicht. D.h. im Sinne des genetischen Algorithmus bestimmt man "wie gut die Verteilung der Aufgaben bei jedem Schüler ist" und dieses optimiert man nun. Bearbeitet 13. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 13. November 2011 Autor Teilen Geschrieben 13. November 2011 Das ist doch schon etwas verständlicher. Ich formuliere das mal etwas abstrakter: D.h. Du hast für jeden Schüler eine maximale Anzahl an Aufgaben, die erreicht werden kann. Also ein Schüler S, hat k Aufgaben, d.h. sofern der Schüler <= k Aufgaben erledigt, ist das eine gültige Lösung D.h. Du hast hier n Aufgaben. Hier ist jetzt in der Formulierung nicht klar, ob hier eine Zuordnung von Aufgabe zu Schüler existiert, d.h. Du hast die Information, welche Aufgabe welcher Schüler erledigen soll. So wie ich das verstehe existiert hier nur eine Liste von Aufgaben Jede Zeile stellt eine Aufgabe dar, es geht nur darum, den jenigen zu ermitteln, der die Aufgabe zu löschen hat. Das Ziel ist also, die n Aufgaben so auf die Schüler zu verteilen, dass a) jeder <= k Aufgaben erledigt und jeder möglichst gleich viel zu tun hat und c) keine Aufgabe doppelt vergeben wird. a) genau nein, Ziel ist es, das jeder sich an sein Limit hällt und nicht mehr oder weniger bearbeitet c) Jede Namenskombination kommt nur ein mal vor, das kann also ignoriert werden. Du hast somit im Grunde drei Constraints, die die Lösung einschränken und die zu beachten sind. Ich kann hier direkt sagen, dass eine Lösung, die durch das Bestimmen jeder möglichen Kombination berechnet wird, extrem schlecht funktionieren wird, weil mehrere gültige Lösungen existieren können. Ich brauch nur eine Außerdem bei einer Listengröße > 1000 Elemente wird das bestimmen der Lösungen extrem ineffizient funktionieren. Ich rate deshalb das ganze über ein heuristisches Verfahren zu lösen Genetischer Algorithmus Man kann das Problem als binäres Problem (Schüler S löst Aufgabe j und kein weiterer Schüler darf dann j lösen) aufbauen und dann über einen genetischen Algorithmus lösen, was durchaus zu einer recht guten Lösung führt. Eine Lösung wie "Probiere alle möglichen Kombinationen durch" wird hier zu extremer Laufzeit führen. Kannst Du mir dazu bitte einen Pseudo-Code geben? Es gibt ja auch die eindeutigen Fälle, wo die Entscheidung eigentlich schon fest steht. Heuristisch könnte man dazu noch anwenden, das der Schüler mit dem geringeren Quotienten die Aufgabe lösen soll, falls das nicht klappt der andere. Danke. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 (bearbeitet) a) genau nein, Ziel ist es, das jeder sich an sein Limit hällt und nicht mehr oder weniger bearbeitet c) Jede Namenskombination kommt nur ein mal vor, das kann also ignoriert werden. Okay, dann fällt raus, d.h. es wäre eben auch möglich, dass einer ganz viele Aufgaben bearbeitet und ein andere keine. Die Bedingung, dass das Limit jedes Schüler exakt erfüllt wird, ist nicht möglich, sofern Du nicht garantieren kannst, dass exakt so viele Aufgaben zur Verfügung stehen, wie alle Schüler zusammen bearbeiten sollen. Selbst wenn Du das garantieren kannst, muss die Lösung nicht eindeutig sein, denn sobald zwei Schüler gleich viele Aufgaben bearbeiten, wäre eine Permutation der Aufgaben immer noch eine gültige Lösung, d.h. Du hast hier eine Vielzahl von möglichen Lösungen. D.h. Du kannst es naiv machen und jede mögliche Lösung bestimmen und nimmst dann eine davon oder Du versuchst direkt eine gute Lösung zu bestimmen. Um alle Lösungen zu bestimmen und dann eine auszuwählen (vor allem ist dann die Frage, wie Du diese auswählst) wird eben nicht effizient möglich sein. Kannst Du mir dazu bitte einen Pseudo-Code geben? Nein nicht direkt. Man kann das Problem als eine Abwandlung von Rucksackproblem auffassen. Eine Lösung mit Hilfe eines genetischen Algorithmus habe ich als Beispielcode hier implementiert http://flashpixx.de/svn/MachineLearning/developer/examples/geneticalgorithm/knapsack.cpp Die Grundannahme ist, dass jeder Schüler jede Aufgabe bearbeiten kann. Man nimmt dann eben n Schüler und verteilt erst einmal zufällig die Aufgaben auf diese. Danach bewertet man wie gut jeder Schüler ist (Fitnessfunktion), d.h. hier musst Du sicherstellen, dass eben wenn mehrere Schüler die gleiche Aufgabe bearbeiten, nur einer als "gut" bewertet wird. Ebenso muss hier bewertet werden, ob er eben seine maximale Anzahl an Aufgaben noch nicht erreicht hat etc., d.h. in diese Bewertungsfunktion müssen alle Bedingungen einfließen, die relevant sind. Anhand dieser Bewertung werden dann eine Anzahl an Schülern ausgewählt und eben rekombiniert, d.h. aus n Schülern werden k neue gemacht. Danach werden ggf noch einzelne Schüler mutiert, d.h. man weist ihnen zufällig Aufgaben zu. Dieses Verfahren iteriert man so lange, bis Konvergenz eintritt, d.h. bis eine Lösung gefunden wurde. Was in den meisten Fällen selbst bei großen Datenmengen in weniger als 100 Iterationen eintritt Heuristisch könnte man dazu noch anwenden, das der Schüler mit dem geringeren Quotienten die Aufgabe lösen soll, falls das nicht klappt der andere. Nein die Zuweisung bezüglich des Quotienten (d.h. der aktuellen Lösungsanzahl) hat mit Heuristik nichts zu tun. Das Verfahren der genetischen Algorithmen ist eine Heuristik. Im Grunde wäre hier die Aussage, dass Schüler, die aktuell "wenig" oder "schlecht" gearbeitet haben, bevorzugt werden, eine weitere Aufgabe zu erhalten. Bearbeitet 13. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 13. November 2011 Teilen Geschrieben 13. November 2011 (bearbeitet) Man kann halt naiv auch durch Reduktion arbeiten, das funktioniert aber nur, wenn keine weiteren Randbedingungen an der Aufgabenstellung existieren, also d.h. man hat nur die Bedingung jeder Schüler muss <= k Aufgaben bearbeiten. In diesem Fall verteilt man eben die Aufgaben so lange auf die Schüler, bis bei jedem / einigen das k erreicht ist, nachdem eine Aufgabe zugeteilt wurde, entfernt man sie aus der Liste, wenn ein Schüler das k erreicht entfernt man diese aus der Liste. Somit reduziert man die Aufgaben und die Schüler (siehe Association rule learning - Wikipedia, the free encyclopedia / frequent itemsets). Nachteil bei dieser Lösung ist aber, dass man eben keine weiteren komplexeren Randbedingungen leicht hinzufügen kann. Man würde eben bei diesem Vorgehen allen Schülern eine Aufgabe zuweisen, dann entfernt man alle Schüler, bei denen das k == 1 ist. Dann weist man eben wieder allen verbleibenden Schülern Aufgaben zu usw. Das ganze macht man so lange, bis entweder keine Aufgaben mehr da sind oder kein Schüler. Bearbeitet 13. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 (bearbeitet) Ich habe es nach dem Verfahren hier versucht Global $fertig = False Func loesungfinden($nr) While $fertig == False $erfolg = Suchen($nr, 0) If $erfolg == -1 Then $erfolg = Suchen($nr, 1) EndIf If $erfolg == 1 Then If $fertig == True Then Return True If loesungfinden($nr + 1) == True Then Return True Else loeschen($nr) If Suchen($nr, 1) == -1 Then loeschen($nr) Else If loesungfinden($nr + 1) == True Then Return True EndIf EndIf EndIf loeschen($nr) Return False WEnd EndFunc ;==>loesungfinden loesungfinden(0) Für die Methode 2. Aber leider funktioniert das nicht, das endet in einer Dauerschleife: ..... ### 374:0 # 401 ### 375:0 # 402 ### 376:0 # 403 ### 377:0 # 404 ### 378:1 # 405 ### 379:0 # 406 ### 380:0 # 407 ### 381:0 # 408 ### 382:1 # 409 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 ### 382:1 # 410 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 zurück: 381 ### 381:1 # 411 ### 382:0 # 412 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 ### 382:1 # 413 ### 383:0 # 414 ### 384:1 # 415 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 416 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 ### 383:0 # 417 ### 384:1 # 418 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 419 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 zurück: 382 zurück: 381 zurück: 380 ### 380:1 # 420 ### 381:0 # 421 ### 382:0 # 422 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 ### 382:1 # 423 ### 383:0 # 424 ### 384:1 # 425 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 426 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 ### 383:0 # 427 ### 384:1 # 428 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 429 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 zurück: 382 zurück: 381 ### 381:1 # 430 ### 382:0 # 431 ### 383:0 # 432 ### 384:1 # 433 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 434 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 ### 383:0 # 435 ### 384:1 # 436 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:1 # 437 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 zurück: 382 ### 382:1 # 438 ### 383:0 # 439 ### 384:0 # 440 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:0 # 441 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 ### 383:0 # 442 ### 384:0 # 443 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 ### 384:0 # 444 0 sind bei beiden übrig 385 0 sind bei beiden übrig 385 ###bereits leer### zurück: 384 zurück: 383 zurück: 382 zurück: 381 zurück: 380 zurück: 379 ### 379:1 # 445 ### 380:0 # 446 ### 381:0 # 447 ### 382:1 # 448 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 ### 382:1 # 449 0 sind bei beiden übrig 383 0 sind bei beiden übrig 383 ###bereits leer### zurück: 382 zurück: 381 ### 381:1 # 450 zurück: XXX = Eintrag wieder gelöscht ### XXX:Y # 449 = Eintrag XXX für Y. Schüler festgelegt 0 sind bei beiden übrig: Limit bei beiden Schülern mitlerweile auf 0 Vorher werden alle eindeutigen Fälle bereits zugeordnet und gelöscht, diese kommen also im gesammten Teil nicht mehr vor. Die Funktion suchen(ID, Nr) überprüft erst, ob mitlerweile ein eindeutiger Fall (bei mehreren Fehler) vorliegt und teilt dann entsprechend zu (auch zum anderen, wenn nötig, also zum 1. anstatt 0. wie aufgerufen). Beinem uneindeutigem Fall wird nach dem übergebenen Parameter entschieden. Die Funktion löschen(ID) löscht den Eintrag wieder. Mir ist die Laufzeit relativ egal, hauptsache die Aufgabe ist gelöst, kann auch ruhig 2 Stunden dauern. Fällt Dir da irgendwo ein Fehler auf? Vielen Dank! Bearbeitet 14. November 2011 von petter2 Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 14. November 2011 Teilen Geschrieben 14. November 2011 (bearbeitet) Dein Code sieht etwas aus wie PHP, da ist die Laufzeit schon relevant, weil der Interpreter, wenn sie eine vorgegebene Grenze überschreitet, einfach das Script abbricht. Wieso muss eine Aufgabe zurück !? Du verteilst nach Deiner Aussage nur die Aufgaben, wann sie zurück kommen, war nicht gefordert. Du kannst keine "uneindeutigen" Fälle produzieren, denn wenn Du so vorgehst, wie in meinem letzten Post beschrieben, wird jede Aufgabe genau einmal an einen Schüler zu gewiesen (Duplikate sind ausgeschlossen) Im Pseudocode: while Aufgabenliste nicht leer und Schülerliste nicht leer { for each s in Schülerliste { hole Aufgabe a aus Aufgabenliste und entferne diese Aufgabe aus der Liste Schüler s erhält Aufgabe a if Aufgabenliste leer break } for each s in Schülerliste if Schüler s hat Maximum an Aufgaben erreicht || Aufgabenliste leer { Schüler s mit seinen Aufgaben anzeigen entferne Schüler s aus Schülerliste } } Ich sehe hier nicht, warum Du ein Backtracking brauchst, denn diese Du hast keine Abhängigkeit, die ggf rückgängig gemacht werden muss. Du Zuordnungen sind immer eindeutig möglich. Ein Backtracking wäre nur nötig, wenn eine Aufgabe an mehrere Schüler ausgegeben wird und einer sie beendet, wobei man dann eben auch alle anderen, die die Aufgabe erhalten haben, benachrichtigen muss. Wobei ein echtes Backtracking braucht man da nicht wirklich. Backtracking brauchst Du nur, wenn Du zu Beginn nicht weißt, ob die Lösung zum Erfolg führt. In diesem Fall geht man alle Möglichkeiten durch und die Lösungen die eben keinen Erfolg liefern kann man während der Berechnung abbrechen. Bearbeitet 14. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 Das haut aber nicht ganz hin... z.B. A0 B1 C3 D1 E1 F1 G2 Nach deinem Verfahren: AB: B AC: C CB: C BD: C CE CD: D DF: F EG: E FG: G Ein G ist übrig, CE ist leer. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 14. November 2011 Teilen Geschrieben 14. November 2011 Ich kann mit Deinen Listen nicht anfangen, bitte benutze eine Darstellung, die leicht (!), schnell (!) zu lesen und verständlich (!) ist. Nur weil es nicht läuft bedeutet das nicht, dass das Verfahren nicht funktioniert, ich würde hier auf Deine Implementierung tippen, dass diese fehlerhaft ist. Das Verfahren konvergiert, denn die Aufgabenmenge wird sofern die Schülerliste nicht leer ist kleiner, bis sie entsprechend leer ist, ebenso die Schülerliste, denn sobald ein Schüler seine maximale Anzahl an Aufgaben erreicht wird er aus der Liste entfernt. Abbruchkritieren sind eben eine leere Schülerliste oder eine leere Aufgabenliste. Bei dem Verfahren werden zuerst die Schüler aus der Liste entfernt, die max. eine Aufgabe erhalten, dann die, die zwei erhalten etc. Der Fall, dass ein Schüler max keine Aufgaben (==0) erhalten darf, muss entsprechend vorher beachtet werden. Der Fall, dass Schüler keine Aufgaben erhalten tritt nur dann auf, wenn die Aufgabenanzahl < als Anzahl der Schüler ist. Andernfalls erhält jeder Schüler mind. eine Aufgabe. Es kann nicht garantiert werden, dass jeder Schüler seine maximale Anzahl an Aufgaben erhält, denn es war nur gefordert <= Anzahl Aufgaben. Wenn eben nicht genügend Aufgaben vorhanden sind, dann kann das eben niemals eintreten. Weiterhin garantiert ist, dass jeder Schüler genau eine Aufgabe bekommt, es treten keine Duplikate auf. D.h. der Algorithmus liefert ein von Dir gefordertes Ergebnis Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 _ArraySort($limits, 1) Dim $loesung[UBound($partner)][3] $partnerLeer = False $limitsLeer = False While $partnerLeer = False And $limitsLeer = False For $i = UBound($limits) - 1 To 0 Step -1 For $t = 0 To UBound($partner) - 1 If ($partner[$t][0] == $limits[$i][1]) Then $loesung[$partner[$t][3]][0] = $partner[$t][0] $loesung[$partner[$t][3]][1] = $partner[$t][1] $loesung[$partner[$t][3]][2] = $partner[$t][0] If _ArrayDelete($partner, $t) == "" Then $partnerLeer = True EndIf $limits[$i][0] -= 1 If $limits[$i][0] = 0 Then If _ArrayDelete($limits, $i) == "" Then $limitsLeer = True EndIf EndIf ExitLoop EndIf If ($partner[$t][1] == $limits[$i][1]) Then $loesung[$partner[$t][3]][0] = $partner[$t][0] $loesung[$partner[$t][3]][1] = $partner[$t][1] $loesung[$partner[$t][3]][2] = $partner[$t][1] If _ArrayDelete($partner, $t) == "" Then $partnerLeer = True EndIf $limits[$i][0] -= 1 If $limits[$i][0] = 0 Then If _ArrayDelete($limits, $i) == "" Then $limitsLeer = True EndIf EndIf ExitLoop EndIf Next Next WEnd _ArrayDisplay($loesung) Das funktioniert nicht, er kommt nich aus der Schleife hinaus... Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 Schüler A, 2 Aufgaben Schüler B, 0 Aufgaben Schüler C, 4 Aufgaben Schüler D, 1 Aufgaben Schüler E, 1 Aufgaben Schüler F, 4 Aufgaben Schüler G, 0 Aufgaben Schüler H, 1 Aufgaben Schüler I, 0 Aufgaben --------------------- Summe = 13 Aufgaben Partner: AB AD AC CE DF CF HI HF GE FG CD GI EF mögliche Lösung: AB A AD A AC C CE C DF D CF C HI H HF F GE E FG F CD C FI F EF F Dein Verfahren: 1. Durchlauf: AB A AD AC C CE E DF D CF F HI H HF GE FG CD FI EF 2. Durchlauf: AB A AD A AC C CE E DF D CF F HI H HF F GE FG CD C FI EF 3. Durchlauf: nichts mehr für C AB A AD A AC C CE E DF D CF F HI H HF F GE FG F CD C FI EF 4. Durchlauf: nichts mehr für 2x C AB A AD A AC C CE E DF D CF F HI H HF F GE LEER FG F CD C FI F EF LEER Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 14. November 2011 Teilen Geschrieben 14. November 2011 Noch einmal der Hinweis: Dein Code ist undokumentiert, noch sind Deine Ausgaben in irgendeiner Form verständlich. Ändere es so ab, dass es verständlich, wenn Du möchtest, dass man Dir hilft. Als weiterer Punkt nehme ich Deine Aufgabenstellung: Jeder Schüler hat ein individuelles Limit an Aufgaben, die er erledigen muss (limits.txt). Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. Geben Sie dazu für jede Zeile an, welcher Schüler die Aufgabe zugeteilt bekommen soll. Daraus folgt, dass für jeden Schüler ein individuelles Limit an Aufgaben existiert und eine Liste von Aufgaben existiert, die Auf die Schüler verteilt werden muss. Es existiert somit keine Einschränkung, dass bestimmte Aufgaben auf bestimmte Schüler verteilt werden müssen o.ä. Wie Du den Hinweis Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. umsetzen willst, hast Du bisher nicht beantwortet. Du hast sogar gesagt, dass der Vorschlag von mir, dass im Mittel jeder gleich viele Aufgaben bearbeiten soll, nicht umgesetzt werden muss. Somit kann ich die genannte Aussage auf <= reduzieren. Dieser Code: $schueler = array( "Peter" => array("max" => 2, "aufgaben" => array()), "Klaus" => array("max" => 5, "aufgaben" => array()), "Nina" => array("max" => 4, "aufgaben" => array()), "Sara" => array("max" => 3, "aufgaben" => array()) ); $aufgaben = array( "Tafel putzen", "Kreide holen", "Bücher holen", "aufräumen", "aufpassen", "Bücher wegräumen", "Klassenzimmer putzen", "Klassenbuch führen", "Kinder betreuen", "Labor aufräumen", "Hausaufgaben machen", "Referat halten", "Test schreiben", "Pausenaufsicht", "Fenster putzen", "Musik spielen", "Essen austeilen" ); while ( (!empty($schueler)) && (!empty($aufgaben)) ) { foreach(array_keys($schueler) as $name) { array_push($schueler[$name]["aufgaben"], array_pop($aufgaben)); if (empty($aufgaben)) break; } foreach ($schueler as $name => $val) if ($val["max"] == count($val["aufgaben"])) { echo "=> ".$name." <=\n"; print_r($schueler[$name]); echo "\n\n"; unset($schueler[$name]); } } echo "Schüler, die das Maximum der Aufgaben nicht erreicht haben:\n"; print_r($schueler); echo "\n\nnicht vergebene Aufgaben:\n"; print_r($aufgaben); [/PHP] liefert genau eine Lösung für Dein Problem. Woher in Deinem Code auf einmal irgendwelche "Partnerbeziehungen" kommen, ist aus der Aufgabenstellung heraus nicht ersichtlich. Die Aussage Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. lässt genau die Aussage zu, dass man eben eine Anzahl an Aufgaben hat, wobei die Einschränkung existiert, dass jede Aufgabe genau einmal bearbeitet werden soll. Liefere entweder weitere Einschränkungen, die zur Lösung relevant sind, ansonsten ist der Code von mir eine Lösung im Rahmen der Aufgabenstellung Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 Die Aufgaben sind völlig egal. Die 1. vorliegende Liste mit den Zahlen gibt das Limit an. z. B. 0, Tom 1, Lisa 1, Mona Die Zahl dabei ist nicht höher als das Vorkommen in Liste 2. Die 2. vorliegende Liste gibt alle Aufgaben an, dabei ist es egal, welche Aufgabe es ist. In der Liste steht z.B. "Tom", "Lisa" "Mona", "Lisa" Als drittes soll hinter jeder Zeile ein Name kommen, entweder Tom oder Lisa, entweder Mona oder Lisa. Jeder Schüler darf so oft drankommen, wie das in der ersten Liste definiert ist. Als Lösung: "Tom", "Lisa": "Lisa", da Tom keine Aufgaben bearbeiten darf "Mona", "Lisa": "Mona", da Lisa keine Aufgaben mehr bearbeiten darf Vielen Dank für die Mühe! Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 14. November 2011 Teilen Geschrieben 14. November 2011 Da fehlt aber noch ein Abbruchkriterium, denn Du weißt aus der ersten Datei, wie viele Aufgaben jeder maximal bearbeiten darf, aus der zweiten Datei weißt Du, wer schon die Aufgabe bearbeitet, aber wann ist die Aufgabe beendet. Als Bsp: 3, Tom 2, Lisa 3, Mona 4, Tim wenn nun in der ersten Zeile der Aufgaben steht: Tom, Lisa => Mona, Tim wenn die zweite Zeile so aussieht, ergibt sich => dann Lisa, Mona => Tom, Tim d.h. jede Zeile Deiner Aufgaben würde mit allen Namen aufgefüllt werden, sofern jeder noch Aufgaben machen darf. Du hättest somit für jede Aufgabenzeile immer alle möglichen Namen stehen. Du bräuchtest somit in der Aufgabenlist eine Information, wann die Aufgabe als "erfüllt" gilt z.B. wenn immer 4 Leute daran mitarbeiten o.ä. So wie ich den das verstehe besagt die Zeile in der Aufgabendatei, wer schon an der Aufgabe arbeitet. Ich sehe das jetzt so, dass Du eben eine Belegung von allen Aufgaben finden sollst, so dass alle Aufgaben bearbeitet werden und keiner seine maximale Anzahl überschreitet. Ist das so richtig !? Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 14. November 2011 Autor Teilen Geschrieben 14. November 2011 Aber es darf ja nur entweder der eine oder der andere Machen. Mona, Tom -> die Aufgabe darf nur Mona oder Tom bearbeiten, wenn deren Limit noch nicht erschöft ist Mona, Tom -> die Aufgabe darf nur Mona oder Lisa bearbeiten, wenn deren Limit noch nicht erschöft ist Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
flashpixx Geschrieben 14. November 2011 Teilen Geschrieben 14. November 2011 (bearbeitet) Ah, dann hatte ich das anders verstanden, ich hatte es so gelesen, dass bei "Mona", "Tom" es heißt, dass die Aufgabe von "Mona" und "Tom" bearbeitet wird und nun noch weitere Mitarbeiter gefunden werden sollen Das sollte das gewünschte liefern: function aufgabenbacktrack( $personen, $aufgaben, $index = 0, $loesung = array()) { if ($index >= count($aufgaben)) { print_r($loesung); return true; } $lpersonen = $personen; foreach($lpersonen as $name => $val) { if ($val <= 0) continue; if (in_array($name, $aufgaben[$index])) { $lloesung = $loesung; array_push($lloesung, $name); $lpersonen[$name]--; if (aufgabenbacktrack($lpersonen, $aufgaben, $index+1, $lloesung)) return true; } } return false; } $schueler = array( "Peter" => 2, "Klaus" => 1, "Nina" => 2, "Sara" => 3, "Christian" => 1, "Joachim" => 3, "Robert" => 2 ); $aufgaben = array( array("Peter", "Klaus"), array("Nina", "Peter"), array("Sara", "Nina", "Klaus"), array("Sara", "Nina"), array("Robert", "Joachim", "Nina"), array("Klaus", "Peter", "Nina", "Joachim") ); aufgabenbacktrack($schueler, $aufgaben); [/php] Bearbeitet 14. November 2011 von flashpixx Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
petter2 Geschrieben 16. November 2011 Autor Teilen Geschrieben 16. November 2011 Vielen Dank nochmal flashpixx für deine Hilfe! Du hast mir sehr geholfen. Zitieren Link zu diesem Kommentar Auf anderen Seiten teilen Mehr Optionen zum Teilen...
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.