Verhuur ski probleem

De skiverhuur probleem is de naam gegeven aan een klasse van problemen waarbij er een keuze tussen blijven een herhalend kosten te betalen of het betalen van een eenmalige kosten die voorkomt of verkleint de repeterende kosten.

Het probleem

Veel online problemen hebben een sub-probleem dat de huur / koop probleem. We moeten beslissen om te blijven in de huidige staat en betalen een bepaald bedrag van de kosten per tijdseenheid, of schakel over naar een andere staat en betaal sommige grote vaste kosten zonder verdere betaling. Skiverhuur is een klassiek speelgoed bijvoorbeeld, waar de huur / kopen is het hele probleem. De basisuitvoering is als volgt:

Je gaat skiën voor een onbekend aantal dagen. Veronderstellen dat het huren van ski's kost $ 1 per dag en het kopen van ski's kost $ 10. Elke dag moet je beslissen of het huren van ski's blijven voor een dag of koop een paar ski's. Als je van tevoren weet hoeveel dagen je gaat skiën, kunt u uw minimale kosten te beslissen. Bijvoorbeeld, als u skiën voor meer dan 10 dagen het goedkoper zal zijn om ski's te kopen, terwijl als je zal skiën voor minder dan 10 dagen zal het goedkoper te huren. De vraag is wat je moet doen als je niet van tevoren weet hoeveel dagen u skiën.

Formeel kan het probleem worden ingesteld als volgt. Er is een aantal dagen d dat u skiën. We zijn op zoek naar een algoritme dat de verhouding tussen wat u betalen via het algoritme en wat zou u optimaal betalen als je d wist op voorhand minimaliseert. Het probleem wordt in het algemeen geanalyseerd in het ergste geval, waarbij het algoritme is vastgesteld en bekijken we de worst-case prestaties van het algoritme alle mogelijke d. In het bijzonder worden geen veronderstellingen over de verdeling van d.

De break-even-algoritme

De break-even-algoritme instrueert u om te huren voor 9 dagen en koop ski's op de ochtend van dag 10 als je nog steeds om te skiën. Als u moet stoppen met skiën tijdens de eerste 9 dagen, het kost hetzelfde als wat je zou betalen als je het aantal dagen dat u zou gaan skiën had geweten. Als u moet stoppen met skiën na dag 10, uw kosten $ 19 die is 90% meer dan wat je zou betalen als je het aantal dagen dat u zou gaan skiën op voorhand had geweten. Dit is het slechtste geval voor het break-even-algoritme.

The break-even algoritme is bekend als de beste deterministisch algoritme om dit probleem.

Kun je beter dan break-even doen?

Ja. Zo kunt u een muntje flip. Als het aankomt op het hoofd, je ski's op dag 8 te kopen; anders, je ski's kopen op dag 10. Dit is een voorbeeld van een gerandomiseerde algoritme. Het is gemakkelijk om te zien dat de verwachte kosten ten hoogste 80% meer dan wat je zou betalen als je het aantal dagen dat je zou gaan skiën, ongeacht hoeveel dagen je ski had gekend. In het bijzonder, als je skiën voor 10 dagen, dan is uw verwachte kosten is 1/2 + 1/2 = 18 dollar, slechts 80% meer dan in plaats van 90%.

De beste gerandomiseerde algoritme tegen een tegenstander bewust is om een ​​dag te kiezen i willekeurig volgens de volgende verdeling p, huren voor i-1 dagen en kopen ski's op de ochtend van de dag dat ik als je nog steeds om te skiën. Karlin et al. eerst gepresenteerd dit algoritme met de distributie, waar het kopen van ski's kost $ b en het huren kost $ 1. De verwachte kosten is bij de meeste e / 1,58 keer wat je zou betalen als je het aantal dagen dat u zou gaan skiën had geweten. Geen gerandomiseerde algoritme beter kunnen doen.

Toepassingen

Snoopy caching: meerdere caches delen dezelfde geheugenruimte die is verdeeld in blokken. Wanneer een cache schrijft aan een blok, caches dat het blok delen besteden 1 bus cyclus bijgewerkt. Deze caches kunnen het blok ongeldig om de kosten van de bijwerking te voorkomen. Maar er is een boete van p bus cycli voor het ongeldig maken van een blok van een cache die kort daarna de toegang moet het. We kunnen de schrijfverzoek sequenties voor meerdere caches breken in verzoek sequenties voor twee caches. Een cache voert een reeks van schrijfbewerkingen op het blok. De andere cache moet beslissen of bijgewerkt door het betalen van 1 bus cyclus per verrichting of ongeldig het blok door het betalen p bus cycli voor toekomstige lezen verzoek van zichzelf. De twee cache, een blok snoopy caching probleem is gewoon de skiverhuur probleem.

TCP erkenning: Een stroom van pakketten aankomen op een bestemming en worden vereist door het TCP-protocol om erkend te worden bij aankomst. Wij kunnen een bevestigingspakket om gelijktijdig meerdere erkennen uitstekende pakketten, waardoor de overhead van de bevestigingen verminderen. Anderzijds, uitstellen bevestigingen te veel gas kunnen de TCP congestie controlemechanismen, en dus moeten we de latentie tussen packet aankomsttijd en het tijdstip waarop de bevestiging verzonden te veel verhogen toestaan. Karlin et al. beschreven in één parameter familie van inputs, genaamd basis inputs, en toonde aan dat wanneer beperkt tot deze basis inputs, het TCP bevestiging gedraagt ​​zich hetzelfde probleem als de ski probleem.

Totale doorlooptijd planning: Wij willen banen met vaste doorlooptijden op m identieke machines plannen. De doorlooptijd van baan j pj. Elke taak wordt bekend bij de planner op de release tijd rj. Het doel is aan de som van doorlooptijden over alle banen te minimaliseren. Een vereenvoudigde probleem is één machine met de volgende ingang: op tijd 0, een baan met verwerkingstijd 1 komt; k banen met verwerkingstijd 0 aankomt op een onbekende tijd. We moeten een starttijd voor de eerste baan te kiezen. Wachttijd loopt een kostprijs van 1 per tijdseenheid, maar het begin van de eerste baan voor de latere banen k kan een extra kost van k in het ergste geval oplopen. Deze vereenvoudigde probleem kan worden beschouwd als een continue versie van de ski probleem.

(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha