Planungsalgorithmus, mathem. Rätsel
Verfasst: Do Jul 18, 2013 6:52 pm
Hallo proggen-interessierte,
gerade hatte ich eine Konversation mit nufan, die ich hier weiterführen möchte.
Sie lautete:
auf der Suche nach Algorithmen und bekannten mathematischen Problemen bin ich auf dein Rucksackproblem-Artikel gestoßen.
Vielen Dank! Dafür wollte ich dir danken, denn er war sehr aufschlussreich.
Ich bin Student in Ingenieurwissenschaften und dies ist keine Formalwissenschaft wie Mathematik oder Informatik, weshalb ich in diesen Dingen weniger gut geschult bin.
Ich habe ein Problem und dachte, vielleicht hast du einen Ansatz oder kennst eine Klasse von Problemen, zu denen dieses zählt (denn ich denke nicht, dass es ein Problem der kombinatorischen Optimierung ist).
Nun zum Rätsel:
Vier Personen stehen auf der einen Seite eines Tunnels. Sie wollen zur anderen Seite. Durch den Tunnel können, weil er so eng ist, maximal 2 Personen gleichzeitig gehen. Die Personen sind unterschiedlich schnell. Der Tunnel ist dunkel und es muss bei jedem Weg durch den Tunnel eine Taschenlampe mitgeführt werden. Es gibt nur eine Taschenlampe.
Hier die Zahlen:
benötigte Zeit:
A: 1 min.
B: 2 min.
C: 4 min.
D: 5 min.
Das Problem: Die Taschenlampe hat exakt für 12 min. Batterieladung. Wer muss mit wem wie gehen, damit alle drüben ankommen?
----------------------------------------------------------------------------
Eins vorweg: ich glaube, dass dieses mit diesen Personen und dieser Taschenlampenbatterieladung keine Lösung hat.
Scheint so eine Art "Planungsalgorithmus" zu sein.
Es stellen sich aber dann sofort mehrere weitere (unter-) Fragen.
a)Nennen Sie für eine beliebige Zusammenstellung von Personen und ihren Geschwindigkeiten eine Formel für das zu erreichende Optimum
b)Nennen Sie einen Algorithmus (Laufstrategie), mit der dieses Optimum immer erreicht wird
c)Beweisen Sie beides, also dass die Formel stimmt, und dass der Algorithmus das Optimum liefert
Schnell wird klar, dass es wohl immer "Hinreisen" mit zwei Personen und "Rückreisen" mit einer Person geben muss, (die Taschenlampe muss immer zurückgebracht werden zur "Startseite" des Tunnels), alles andere wäre kontraproduktiv (etwa das nur ein einzelner eine Hinreise antritt oder etwa, dass irgendeine Rückreise aus zwei Personen bestehen würde). Auch schnell klar ist, dass also dann die Gesamtzahl der Hinreisen gleich der Anzahl der Reisenden minus eins sein muss (jede Hinreise und anschließende Rückreise transportiert effektiv eine Person ans Ziel, ausser der letzten Hinreise, auf die keine Rückreise mehr folgt, welche effektiv zwei Personen ans Ziel bringt). Die Anzahl der Rückreisen beträgt Anzahl der Hinreisen minus eins, da also ein Schema vorliegt, dass Hin- und Rückreisen immer abwechselnd passieren müssen, wobei wir immer mit einer Hinreise beginnen und ebenfalls mit einer Hinreise enden.
Vielleicht liegt schon längst wissenschaftliche Erkenntnis für dieses Rätsel vor, man muss wahrscheinlich nur den korrekten Namen dieses Rätsels (oder dieser Klasse von Rätseln, denen diese Rätsel zuzuordnen ist) wissen bzw. finden. Folgende Stichpunkte fallen mir leider nur ein: "Optimierung", "Planungsalgorithmus" oder eventuell der Begriff "diskrete Mathematik".
Falls du derzeit keine Zeit hast - kein Problem!! Wollte es nur mal abschicken, vielleicht interessierts ja.
Vielleicht kennst du ein (anderes) Forum, wo man die Frage stellen sollte?
Gruß
melmo
Hier kommt nufan Antwort:
Hallo melmo!
Wenn zwei Personen zusammen gehen, haben sie die Geschwindigkeit der langsameren Person, oder? Auf dem Rückweg hat dann der Taschenlampenträger einfach seine eigene Geschwindigkeit. Liege ich da richtig?
Falls ich bei meiner obigen Annahme richtig liege, würde ich sagen es spielt einfach immer die schnellste Person den Lampen-Träger. Da ja jede Person mindestens ein mal durch den Tunnel muss, ist ihre Geschwindigkeit auf dem Hinweg ohnehin nicht optimierbar. Das einzige was man hier optimieren kann ist der Rückweg, wo man natürlich die schnellste Person wählen sollte. Die restliche Reihenfolge ist egal, am Ergebnis ändert sich nix
Sehe ich auch so.
1+2 gehen durch den Tunnel (+2 Minuten, insgesamt 2 Minuten)
1 geht zurück (+1 Minute, insgesamt 3 Minuten)
1+4 gehen durch den Tunnel (+4 Minuten, insgesamt 7 Minuten)
1 geht zurück (+1 Minute, insgesamt 8 Minuten)
1+5 gehen durch den Tunnel (+5 Minuten, insgesamt 13 Minuten)
Also liegt man hier im Optimalfall bei 13 Minuten. Schneller gehts einfach nicht.
Formel:
t = Alle Zeiten zum Durchqueren des Tunnels
t' = Kürzeste Zeit zum Durchqueren des Tunnels
t \ t' = Alle Zeiten außer die kürzeste
n = Anzahl an Personen, n > 2
Gesamtsumme = (n-2) * t' + sum(t \ t')
n-2 hast du, weil beim ersten und letzten Durchgang jeweils nur in eine Richtung gegangen wird.
In deinem konkreten Beispiel:
t = {1, 2, 4, 5}
t' = 1
t \ t' = {2, 4, 5}
n = 4
Gesamtsumme = 2 * 1 + (2 + 4 + 5) = 13
Ich würde sagen man kann das relativ einfach über einen Gegenbeweis angeben. n-2 ist immer mindestens 1 (kann und wird im Normalfall aber auch größer sein). Eine Durchgangszeit im ersten Teil der Formel ((n-2) * t') hat also immer größeren Einfluss als im hinteren Teil (sum(t \ t')), da hier der Faktor konstant 1 ist und nie größer wird. Wäre t' nicht das Minimum, würde das den Gesamtwert vergrößern, da ein größerer Wert im vorderen Teil steht.
Das muss man jetzt halt noch schön formal anschreiben ^^
Wie oben bereits erklärt würde ich minus 2 sagen.
Eventuell habe ich ja das Problem falsch interpretiert - oder du siehst das ganze etwas komplizierter als es eigentlich ist ^^ Du kannst das ganze natürlich auch über kombinatorische Optimierung lösen, du wirst aber keine bessere Lösung finden.
Ich hoffe ich konnte dir ein wenig weiter helfen Falls es noch Fragen gibt möchte ich dich bitten hier im Forum zu posten, dann haben andere auch was davon
PS: Du hast deinen Usernamen nicht zufällig von einem iOS-Spiel, oder?
--------------------------------------------------------------------------------------------------------------
Hier nun meine Antwort an nufan:
Hallo nufan,
thanks!!!! meine ersten Gedanken dazu:
mhmmhmh, also der Ansatz mit der (n-2)*t'+sum(t\t') gefällt mir ein wenig. Ich verstehe, dass ein t im linken Summanden mehr wiegt als das selbe t im rechten Summanden. Dazu müsste man aber erst sauber belegen, dass ein solches t entweder im linken oder im rechten Summanden auftaucht. Dass hier entweder oder möglich ist scheint mir noch nicht erwiesen (man könnte ja auch auf die Idee kommen, jeden Rückweg mit einem anderen Passagier durchzuführen oder ähnliche Scherze....)
gerade hatte ich eine Konversation mit nufan, die ich hier weiterführen möchte.
Sie lautete:
auf der Suche nach Algorithmen und bekannten mathematischen Problemen bin ich auf dein Rucksackproblem-Artikel gestoßen.
Vielen Dank! Dafür wollte ich dir danken, denn er war sehr aufschlussreich.
Ich bin Student in Ingenieurwissenschaften und dies ist keine Formalwissenschaft wie Mathematik oder Informatik, weshalb ich in diesen Dingen weniger gut geschult bin.
Ich habe ein Problem und dachte, vielleicht hast du einen Ansatz oder kennst eine Klasse von Problemen, zu denen dieses zählt (denn ich denke nicht, dass es ein Problem der kombinatorischen Optimierung ist).
Nun zum Rätsel:
Vier Personen stehen auf der einen Seite eines Tunnels. Sie wollen zur anderen Seite. Durch den Tunnel können, weil er so eng ist, maximal 2 Personen gleichzeitig gehen. Die Personen sind unterschiedlich schnell. Der Tunnel ist dunkel und es muss bei jedem Weg durch den Tunnel eine Taschenlampe mitgeführt werden. Es gibt nur eine Taschenlampe.
Hier die Zahlen:
benötigte Zeit:
A: 1 min.
B: 2 min.
C: 4 min.
D: 5 min.
Das Problem: Die Taschenlampe hat exakt für 12 min. Batterieladung. Wer muss mit wem wie gehen, damit alle drüben ankommen?
----------------------------------------------------------------------------
Eins vorweg: ich glaube, dass dieses mit diesen Personen und dieser Taschenlampenbatterieladung keine Lösung hat.
Scheint so eine Art "Planungsalgorithmus" zu sein.
Es stellen sich aber dann sofort mehrere weitere (unter-) Fragen.
a)Nennen Sie für eine beliebige Zusammenstellung von Personen und ihren Geschwindigkeiten eine Formel für das zu erreichende Optimum
b)Nennen Sie einen Algorithmus (Laufstrategie), mit der dieses Optimum immer erreicht wird
c)Beweisen Sie beides, also dass die Formel stimmt, und dass der Algorithmus das Optimum liefert
Schnell wird klar, dass es wohl immer "Hinreisen" mit zwei Personen und "Rückreisen" mit einer Person geben muss, (die Taschenlampe muss immer zurückgebracht werden zur "Startseite" des Tunnels), alles andere wäre kontraproduktiv (etwa das nur ein einzelner eine Hinreise antritt oder etwa, dass irgendeine Rückreise aus zwei Personen bestehen würde). Auch schnell klar ist, dass also dann die Gesamtzahl der Hinreisen gleich der Anzahl der Reisenden minus eins sein muss (jede Hinreise und anschließende Rückreise transportiert effektiv eine Person ans Ziel, ausser der letzten Hinreise, auf die keine Rückreise mehr folgt, welche effektiv zwei Personen ans Ziel bringt). Die Anzahl der Rückreisen beträgt Anzahl der Hinreisen minus eins, da also ein Schema vorliegt, dass Hin- und Rückreisen immer abwechselnd passieren müssen, wobei wir immer mit einer Hinreise beginnen und ebenfalls mit einer Hinreise enden.
Vielleicht liegt schon längst wissenschaftliche Erkenntnis für dieses Rätsel vor, man muss wahrscheinlich nur den korrekten Namen dieses Rätsels (oder dieser Klasse von Rätseln, denen diese Rätsel zuzuordnen ist) wissen bzw. finden. Folgende Stichpunkte fallen mir leider nur ein: "Optimierung", "Planungsalgorithmus" oder eventuell der Begriff "diskrete Mathematik".
Falls du derzeit keine Zeit hast - kein Problem!! Wollte es nur mal abschicken, vielleicht interessierts ja.
Vielleicht kennst du ein (anderes) Forum, wo man die Frage stellen sollte?
Gruß
melmo
Hier kommt nufan Antwort:
Hallo melmo!
melmo hat geschrieben:Vier Personen stehen auf der einen Seite eines Tunnels. Sie wollen zur anderen Seite. Durch den Tunnel können, weil er so eng ist, maximal 2 Personen gleichzeitig gehen. Die Personen sind unterschiedlich schnell. Der Tunnel ist dunkel und es muss bei jedem Weg durch den Tunnel eine Taschenlampe mitgeführt werden. Es gibt nur eine Taschenlampe.
Wenn zwei Personen zusammen gehen, haben sie die Geschwindigkeit der langsameren Person, oder? Auf dem Rückweg hat dann der Taschenlampenträger einfach seine eigene Geschwindigkeit. Liege ich da richtig?
melmo hat geschrieben: Hier die Zahlen:
benötigte Zeit:
A: 1 min.
B: 2 min.
C: 4 min.
D: 5 min.
Das Problem: Die Taschenlampe hat exakt für 12 min. Batterieladung. Wer muss mit wem wie gehen, damit alle drüben ankommen?
Falls ich bei meiner obigen Annahme richtig liege, würde ich sagen es spielt einfach immer die schnellste Person den Lampen-Träger. Da ja jede Person mindestens ein mal durch den Tunnel muss, ist ihre Geschwindigkeit auf dem Hinweg ohnehin nicht optimierbar. Das einzige was man hier optimieren kann ist der Rückweg, wo man natürlich die schnellste Person wählen sollte. Die restliche Reihenfolge ist egal, am Ergebnis ändert sich nix
melmo hat geschrieben:Eins vorweg: ich glaube, dass dieses mit diesen Personen und dieser Taschenlampenbatterieladung keine Lösung hat.
Sehe ich auch so.
1+2 gehen durch den Tunnel (+2 Minuten, insgesamt 2 Minuten)
1 geht zurück (+1 Minute, insgesamt 3 Minuten)
1+4 gehen durch den Tunnel (+4 Minuten, insgesamt 7 Minuten)
1 geht zurück (+1 Minute, insgesamt 8 Minuten)
1+5 gehen durch den Tunnel (+5 Minuten, insgesamt 13 Minuten)
Also liegt man hier im Optimalfall bei 13 Minuten. Schneller gehts einfach nicht.
melmo hat geschrieben: a)Nennen Sie für eine beliebige Zusammenstellung von Personen und ihren Geschwindigkeiten eine Formel für das zu erreichende Optimum
Formel:
t = Alle Zeiten zum Durchqueren des Tunnels
t' = Kürzeste Zeit zum Durchqueren des Tunnels
t \ t' = Alle Zeiten außer die kürzeste
n = Anzahl an Personen, n > 2
Gesamtsumme = (n-2) * t' + sum(t \ t')
n-2 hast du, weil beim ersten und letzten Durchgang jeweils nur in eine Richtung gegangen wird.
In deinem konkreten Beispiel:
t = {1, 2, 4, 5}
t' = 1
t \ t' = {2, 4, 5}
n = 4
Gesamtsumme = 2 * 1 + (2 + 4 + 5) = 13
Siehe oben.melmo hat geschrieben:b)Nennen Sie einen Algorithmus (Laufstrategie), mit der dieses Optimum immer erreicht wird
melmo hat geschrieben: c)Beweisen Sie beides, also dass die Formel stimmt, und dass der Algorithmus das Optimum liefert
Ich würde sagen man kann das relativ einfach über einen Gegenbeweis angeben. n-2 ist immer mindestens 1 (kann und wird im Normalfall aber auch größer sein). Eine Durchgangszeit im ersten Teil der Formel ((n-2) * t') hat also immer größeren Einfluss als im hinteren Teil (sum(t \ t')), da hier der Faktor konstant 1 ist und nie größer wird. Wäre t' nicht das Minimum, würde das den Gesamtwert vergrößern, da ein größerer Wert im vorderen Teil steht.
Das muss man jetzt halt noch schön formal anschreiben ^^
melmo hat geschrieben:Die Anzahl der Rückreisen beträgt Anzahl der Hinreisen minus eins, da also ein Schema vorliegt, dass Hin- und Rückreisen immer abwechselnd passieren müssen, wobei wir immer mit einer Hinreise beginnen und ebenfalls mit einer Hinreise enden.
Wie oben bereits erklärt würde ich minus 2 sagen.
melmo hat geschrieben:Vielleicht liegt schon längst wissenschaftliche Erkenntnis für dieses Rätsel vor, man muss wahrscheinlich nur den korrekten Namen dieses Rätsels (oder dieser Klasse von Rätseln, denen diese Rätsel zuzuordnen ist) wissen bzw. finden.
Eventuell habe ich ja das Problem falsch interpretiert - oder du siehst das ganze etwas komplizierter als es eigentlich ist ^^ Du kannst das ganze natürlich auch über kombinatorische Optimierung lösen, du wirst aber keine bessere Lösung finden.
Ich hoffe ich konnte dir ein wenig weiter helfen Falls es noch Fragen gibt möchte ich dich bitten hier im Forum zu posten, dann haben andere auch was davon
PS: Du hast deinen Usernamen nicht zufällig von einem iOS-Spiel, oder?
--------------------------------------------------------------------------------------------------------------
Hier nun meine Antwort an nufan:
Hallo nufan,
thanks!!!! meine ersten Gedanken dazu:
mhmmhmh, also der Ansatz mit der (n-2)*t'+sum(t\t') gefällt mir ein wenig. Ich verstehe, dass ein t im linken Summanden mehr wiegt als das selbe t im rechten Summanden. Dazu müsste man aber erst sauber belegen, dass ein solches t entweder im linken oder im rechten Summanden auftaucht. Dass hier entweder oder möglich ist scheint mir noch nicht erwiesen (man könnte ja auch auf die Idee kommen, jeden Rückweg mit einem anderen Passagier durchzuführen oder ähnliche Scherze....)
Moment mal, dieser Satz scheint mir etwas zu unbrauchbar: Es gibt immer die folgende Idee: Läßt man 4+5 gemeinsam reisen, und dazu als letztes (keiner muss eine Rückreise antreten), scheint das doch sehr sparsam zu sein (Dies zu widerlegen gilt es vielleicht...)nufan hat geschrieben:Da ja jede Person mindestens ein mal durch den Tunnel muss, ist ihre Geschwindigkeit auf dem Hinweg ohnehin nicht optimierbar.
n-2 stimmt zwar, korrekter formulieren müsste man aber irgendwie, denn nicht beim ersten und letzten, sondern je nachdem wie man es sieht, entweder beim ersten oder beim letzten mal wird nur in eine Richtung gegangen.nufan hat geschrieben:n-2 hast du, weil beim ersten und letzten Durchgang jeweils nur in eine Richtung gegangen wird.