Autor |
Beitrag |
Kay Schönberger (kay_s)
Erfahrenes Mitglied Benutzername: kay_s
Nummer des Beitrags: 115 Registriert: 01-2001
| Veröffentlicht am Freitag, den 13. Juni, 2003 - 16:39: |
|
In einem Lagerhaus befinden sich nebeneinander vier großflächige Palettenstapel. Auf dem Stapel ganz links befinden sich 100 Paletten, die anderen sind leer. Um die (ziemlich schweren) Paletten umzuverteilen steht ein vollautomatischer Gabelstapler bereit. Das Problem: Die gesamte Technik sowie die Software stammt noch aus den Siebzigern. Damals war die Steuerelektronik noch ziemlich primitiv und so versteht der Gabelstapler nur die zwei Befehle "L" und "R". Nach einer solchen Anweisung holt der Stapler eine Zahl Paletten vom aktuellen Stapel, bewegt sich (je nach Anweisung "L" oder "R") eine Position nach links oder rechts und schichtet die Paletten auf den aktuellen neuen Stapel auf. Dummerweise kann das Maschinchen nicht einzelne Paletten auseinanderhalten, sondern holt nach jeder Anweisung exakt die Hälfte der Paletten vom aktuellen Stapel herunter (ist die Zahl N der Paletten ungerade, werden (N+1)/2 Stück geholt). Der Lagerchef würde es nun gerne sehen, daß der Gabelstapler folgende Aufgaben erledigt: Programm A: 60 Paletten vom Ausgangsstapel gleichmäßig auf die restlichen verteilen (Zielkonfiguration: 40/20/20/20) Programm B: 90 Paletten vom Ausgangsstapel gleichmäßig auf die restlichen verteilen (Zielkonfiguration: 10/30/30/30) In einem Beispiel würde die Anweisungsfolge "R L R R R L ..." also zu der Konfigurationsfolge (100/0/0/0 [1]) -> (50/50/0/0 [2]) -> (75/25/0/0 [1]) -> (37/63/0/0 [2]) -> (37/31/32/0 [3]) -> (37/31/16/16 [4]) -> (37/31/24/8 [3]) -> ... führen (letzte Ziffer = aktuelle Position der Maschine). Der Chef sieht sich trotz seiner Qualifikation leider nicht in der Lage, die richtige Anweisungsfolge einzugeben. Deshalb hat er sich ein ganzes Dutzend Programmierer ins Boot geholt, die das Problem lösen sollten. Und tatsächlich - nach einer Woche fand einer der gestreßten Computerexperten eine Anweisungsfolge für Programm A! Wie sah sie wohl aus? (P.S.: Trotzdem der Chef weitere zwei Monate Zeit investiert hat, fand keiner der Programmierer eine Lösung für Programm B...) |
Martin (martin243)
Senior Mitglied Benutzername: martin243
Nummer des Beitrags: 771 Registriert: 02-2001
| Veröffentlicht am Montag, den 16. Juni, 2003 - 17:33: |
|
Tach! Nach ersten zaghaften Versuchen per Hand kam ich zu dem Schluss, dass es wohl doch mehr als 5 oder 10 Schritte sein müssten. Also habe ich mal den Computer darauf angesetzt und er fand für A insgesamt 675 verschiedene jeweils 40-schrittige Lösungen. Hier mal drei davon: rrrlrlllrrrlllrrrlllrrrllrrlllrrllrrrlll rlrlrrlrrlllrrrllrllrrrlllrrlrrlllrrrlll rlrrrllrrlllrrlrrlllrrrlllrrlrrlllrrrlll Hier auch mal die letzte zum Nachvollziehen, wobei die Positionen mit 0 bis 3 bezeichnet sind: 50 50 0 0 [1] 75 25 0 0 [0] 37 63 0 0 [1] 37 31 32 0 [2] 37 31 16 16 [3] 37 31 24 8 [2] 37 43 12 8 [1] 37 21 34 8 [2] 37 21 17 25 [3] 37 21 30 12 [2] 37 36 15 12 [1] 55 18 15 12 [0] 27 46 15 12 [1] 27 23 38 12 [2] 27 42 19 12 [1] 27 21 40 12 [2] 27 21 20 32 [3] 27 21 36 16 [2] 27 39 18 16 [1] 47 19 18 16 [0] 23 43 18 16 [1] 23 21 40 16 [2] 23 21 20 36 [3] 23 21 38 18 [2] 23 40 19 18 [1] 43 20 19 18 [0] 21 42 19 18 [1] 21 21 40 18 [2] 21 41 20 18 [1] 21 20 41 18 [2] 21 20 20 39 [3] 21 20 40 19 [2] 21 40 20 19 [1] 41 20 20 19 [0] 20 41 20 19 [1] 20 20 41 19 [2] 20 20 20 40 [3] 20 20 40 20 [2] 20 40 20 20 [1] 40 20 20 20 [0] Über die B zerbreche ich mir momentan noch den Kopf. MfG Martin |
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 207 Registriert: 10-2001
| Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 07:12: |
|
Hallo Kay, für Programm A ist die kürzeste Lösung 38 Züge: 1: r [100,0,0,0] ==> [50,50,0,0] 2: l [50,50,0,0] ==> [50,25,25,0] 3: r [50,25,25,0] ==> [50,38,12,0] 4: l [50,38,12,0] ==> [69,19,12,0] 5: r [69,19,12,0] ==> [34,54,12,0] 6: r [34,54,12,0] ==> [34,27,39,0] 7: r [34,27,39,0] ==> [34,27,19,20] 8: l [34,27,19,20] ==> [34,27,29,10] 9: l [34,27,29,10] ==> [34,42,14,10] 10: l [34,42,14,10] ==> [55,21,14,10] 11: r [55,21,14,10] ==> [27,49,14,10] 12: r [27,49,14,10] ==> [27,24,39,10] 13: r [27,24,39,10] ==> [27,24,19,30] 14: l [27,24,19,30] ==> [27,24,34,15] 15: l [27,24,34,15] ==> [27,41,17,15] 16: r [27,41,17,15] ==> [27,20,38,15] 17: l [27,20,38,15] ==> [27,39,19,15] 18: l [27,39,19,15] ==> [47,19,19,15] 19: r [47,19,19,15] ==> [23,43,19,15] 20: r [23,43,19,15] ==> [23,21,41,15] 21: r [23,21,41,15] ==> [23,21,20,36] 22: l [23,21,20,36] ==> [23,21,38,18] 23: l [23,21,38,18] ==> [23,40,19,18] 24: l [23,40,19,18] ==> [43,20,19,18] 25: r [43,20,19,18] ==> [21,42,19,18] 26: r [21,42,19,18] ==> [21,21,40,18] 27: l [21,21,40,18] ==> [21,41,20,18] 28: r [21,41,20,18] ==> [21,20,41,18] 29: r [21,20,41,18] ==> [21,20,20,39] 30: l [21,20,20,39] ==> [21,20,40,19] 31: l [21,20,40,19] ==> [21,40,20,19] 32: l [21,40,20,19] ==> [41,20,20,19] 33: r [41,20,20,19] ==> [20,41,20,19] 34: r [20,41,20,19] ==> [20,20,41,19] 35: r [20,20,41,19] ==> [20,20,20,40] 36: l [20,20,20,40] ==> [20,20,40,20] 37: l [20,20,40,20] ==> [20,40,20,20] 38: l [20,40,20,20] ==> [40,20,20,20] Programm B ist nicht lösbar. Um es mal ein bißchen mit Graphentheorie zu sagen: Die Zielmenge B befindet sich in einem unabhängigen Teilgraphen. Es gibt keine Beziehung zur Startmenge. Scheinbar läßt die Art und Weise des umstapelns nicht alle möglichen Kombinationen zu, was eine kleine Statistik über den kompletten Graph zeigt: Ecken: 2265 (mögliche Palettenverteilung) Kanten: 3630 (Wege zwischen Palettenverteilungen) IMHO müßte der Graph 101^3 Palettenverteilungen enthalten (ca. 1 Mio.). Onkel Murray |
Giertzsch (bernoulli01)
Junior Mitglied Benutzername: bernoulli01
Nummer des Beitrags: 8 Registriert: 07-2003
| Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 09:30: |
|
Hallo Onkel Murray! Meinst du mit Ecken jetzt die Knoten, oder Blätter des Graphen? MFG |
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 208 Registriert: 10-2001
| Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 09:53: |
|
@Giertzsch: Wäre es ein Baum, dann hätte er Blätter, da es aber ein gerichteter Graph mit Schleifen ist (ein Baum hat keine Schleifen) meine ich die Knoten - und zwar in diesem Falle alle, welche mit dem Startknoten (100,0,0,0) erzeugbar sind. Wenn man Blatt als Knoten definiert, welcher keine Kinder hat, dann gibt es in diesem Graph auch keine Blätter (sorry, kann nix dafür ). Onkel Murray |
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 209 Registriert: 10-2001
| Veröffentlicht am Donnerstag, den 10. Juli, 2003 - 10:02: |
|
Aber um den Spaß mal zu steigern: Angenommen, der Typ der das Programm schreibt hat Pause während der Stapler stapelt. Dann möchte er doch möglichst ein langes Programm haben. Das Problem ist nur, würde der Stapler sich in einer Schleife verfangen, käme das Program nie zum Ende. Auch würde es dem Chef auffallen wenn eine Kombination mehrfach vorhanden ist. Dann grübelt mal schön Onkel Murray PS: Ich hab die Lösung schon, falls jemand verzweifelt kann ich auch Tips geben :-)
|
|