Ski-Rental-Problem - LinkFang.de





Ski-Rental-Problem


Dieser Artikel oder Abschnitt ist lückenhaft.

Beim Ski-Rental-Problem (Skiverleihproblem) geht es darum, zu einem passenden Zeitpunkt zu entscheiden, Skier einmalig zu kaufen oder für jeden Skilauf zu leihen, und zwar unter der Maßgabe, dass die Gesamtkosten minimal sind. Es entstand einst als pädagogisches Werkzeug für das Verständnis von Online-Algorithmen. Das Ski-Rental-Problem steht stellvertretend für eine Reihe von Problemen, in denen jeweils ein Konsument eine Sportart ausüben möchte (z. B. Radfahren, Surfen, Tennis), für die ein Sportgerät erforderlich ist (z. B. Fahrrad, Surfbrett, Tennisschläger), das wahlweise einmalig gekauft oder mehrfach ausgeliehen werden kann.

Problembeschreibung

Angenommen, eine Person, die keine Ski besitzt, möchte Ski fahren gehen. Die Person hat die Möglichkeit, zwischen dem einmaligen Kauf eines Paares Skier (Kaufpreis z. B. 200 Euro) und der Ausleihe eines Paares für jeden Skilauf (Leihpreis z. B. 20 Euro) zu wählen. Falls der Person die Anzahl der Skiläufe zu Beginn bekannt ist (z. B. 5 Läufe), fiele die Entscheidung im Falle des Beispiels auf die fünfmalige Leihe, da die Leihkosten in Höhe von 5 × 20 Euro = 100 Euro geringer wären als der Kaufpreis. Würde die Person hingegen 12 Tage Ski fahren wollen, wäre es für sie cleverer, sich gleich am ersten Tag das Paar Skier zu kaufen, da die Kaufkosten von 200 Euro kleiner sind als die Ausleihkosten für 12 Tage (12 × 20 Euro = 240 Euro).

Das Ziel hierbei ist es nun, eine Handlungsvorschrift (Algorithmus) zu finden, welcher die zusätzlichen Kosten, die durch Unwissenheit über die Anzahl der Skitage entstehen können, zu minimieren. Es ist leicht zu zeigen, dass wenn man am Morgen des 10. Tages das Paar Skier kauft, die zusätzlichen Kosten im schlimmsten Fall 90 % höher liegen, als wenn man wissen würde, wie lange man Ski fahren würde.

Literatur

  • Mark S. Manasse: Ski Rental Problem. In: Ming-Yang Kao (Hg.): Encyclopedia of Algorithms. Springer, Berlin/Heidelberg/New York 2008, ISBN 978-0-387-30162-4, Teil 18.
  • Anna R. Karlin: On the Performance of Competitive Algorithms in Practice. In: Amos Fiat, Gerhard J. Woeginger (Hg.): Online Algorithms. The State of the Art. Lecture Notes in Computer Science 1442, Springer, Berlin/Heidelberg/New York 2008, ISBN 3-540-64917-4, Kap. 16, S. 373 ff.

Kategorien: Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Ski-Rental-Problem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.