petter2
-
Gesamte Inhalte
18 -
Benutzer seit
-
Letzter Besuch
Inhaltstyp
Profile
Forum
Downloads
Kalender
Blogs
Shop
Beiträge von petter2
-
-
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
-
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!
-
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
-
_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...
-
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.
-
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!
-
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.
-
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...
-
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.
-
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!
-
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!
-
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!
-
Ok, also eine Liste führen. Vielen Dank!
-
Das ist aber meine Problemstellung
Die Richtung, wie das Skript auf die Verbindung kommt, ist, wie von dir geschrieben, egal.
-
OK, danke!
Jede Verbindung braucht eine Pfeilrichtung. Jedes Kästchen hat aber ein bestimmtes Limit, wie viel Pfeile dort hinzeigen dürfen. Fällt einem dazu vielleicht noch etwas ein?
Die Verbindungen und Kästchen sind in zwei Arrays.
-
Vielen Dank für Deine Antwort!
Ich habe mal versucht mit Paint das darzustellen. Wenn das Programm auf ein Problem trifft, soll er so lange zurück gehen, bis eine andere Möglichkeit vorhanden ist (das ist in der Grafik nicht ersichtlich). Meine Frage ist jetzt, wie ich die Blau markierten Felder wieder "leeren" kann, da da ja durch die andere Entscheidung auch wiederrum alles ändern kann.
Vielen Dank!
EDIT:
Wird aber deutlich komplizierter, z.B. hier, zurück bis auf 2:
-
Hallo!
Folgendes Problem:
Func Funktion($a) If Fehler() Then Return -1 ; Funktion ; ... For $a in $b ; Bedingung für weitere Durchführungen $erfolgreich = Funktion($a) If $erfolgreich == -1 Then ; Funktion rückgängig machen ; ... Return -1 EndIf Next Return 1 EndFunc
Angenommen, er geht das erste mal in die Funktion hinein. Die zweite Ebene durchläuft er auch, der erste Zweig ist erfolgreich und er kommt wieder zurück, beim zweiten Zweig gibt es einen Fehler. Dann löscht er auch die erste Ebene. Aber was muss man wie programmieren, damit er auch die Entscheidungen von der zweiten Ebene vom ersten Zweig löscht (das ist ja auch verzweigt und verschachtelt)?
Ich hoffe ich habe mich verständlich ausgedrückt, ansonsten bitte Fragen.
Vielen Dank!
gültige Kombination finden
in Algorithmik
Geschrieben
Vielen Dank nochmal flashpixx für deine Hilfe! Du hast mir sehr geholfen.