Backtracking Algorithmus < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:39 Mi 03.06.2009 | | Autor: | Chibby |
| Aufgabe | Ein Programmierer soll n Kundenaufträge [mm] A_1 [/mm] bis [mm] A_n [/mm] bearbeiten. Um den Auftrag [mm] A_i [/mm] zu bearbeiten, benötigt er dazu die Zeit [mm] t_i. [/mm] Die Aufträge sollen so bearbeitet werden, dass die Kunden möglichst wenig Warten müssen.
Beispiel: Bei 3 Aufträgen mit der Bearbeitungszeit [mm] t_1 [/mm] =5, [mm] t_2 [/mm] = 10 und [mm] t_3 [/mm] = 3 ergibt sich für die Arbeitsreihenfolge [mm] A_1,A_2,A_3 [/mm] : [mm] w_1 [/mm] = 5, [mm] w_2 [/mm] =5+ 10; [mm] w_3 [/mm] = 5+10+3. Damit ist die gesamtwartezeit [mm] w_1+w_2+w_3 [/mm] = 38
|
Hallo.
Ich soll das Problem mit Backtracking für n Aufträge lösen, habe aber nun keine Ahnung, wie eine Abbruchsbedingung lauten könnte.
Meeine Idee wäre
Ich berechne die Gesamtwartezeit für die Auftragsreihenfolge [mm] A_1 [/mm] ... [mm] A_n; [/mm] Die Wartezeit sei [mm] w_1.
[/mm]
Danach gehe ich alle anderen Auftragsreihenfolgen durch, und sobald [mm] w_2 [/mm] > [mm] w_1, [/mm] breche ich ab.
Aber irgendwie ist das dann alle Möglichkeiten durchgehen, aber vorzeitig aufhören, wenn möglich. Muss man das so machen oder könt ihr mir da einen Pseudocode geben oder die Idee hier erläutern?
Grüße,
Chibby
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:54 Sa 06.06.2009 | | Autor: | Karl_Pech |
Hallo Chibby,
Irgendwie ist mir die Aufgabenstellung unklar. Was spräche denn dagegen alle Aufträge nach [mm]t_i[/mm] aufsteigend zu sortieren, damit die Aufträge mit der kürzesten Wartezeit zuerst abgearbeitet werden?
Haben die Aufträge zufälligerweise eine Art Wert oder so? Wenn ja, so könnte es eine Variante des ![[]](/images/popup.gif) Rucksackproblems sein. Aber so wie die Aufgabe bisher formuliert ist, scheint Sortieren nach [mm]t_i[/mm] die Lösung zu sein.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:06 Di 09.06.2009 | | Autor: | Gilga |
Man sollte sich schon an die Aufgabenstellung halten.
Backtracking würde so laufen.
Dein Ansatz stimmt schon
Man wählt ersten Auftrag aus den verbliebenen, 2. .....
Und sobald die bisherige Teilsumme meine beste Zeit (aus früherem Lauf) übersteigt mache ich backtracking zum vorgehenden Auftrag.
Dadurch muss nicht zwangsläufig alle Kombinationen durchsucht werden. Kann aber bei Backtracking vorkommen
|
|
|
|
