Problém s půjčováním lyží - Ski rental problem

Tento článek má několik problémů. Prosím pomozte zlepšit to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek může být pro většinu čtenářů příliš technická na to, aby tomu rozuměli. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Problém s půjčováním lyží“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, problém s půjčováním lyží je název pojmenovaný pro třídu problémů, ve kterých je na výběr mezi pokračováním v platbě opakujících se nákladů nebo platbou jednorázových nákladů, které eliminují nebo snižují opakující se náklady.

Problém

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Mnoho online problémy mít dílčí problém zvaný problém s nájmem / nákupem. Musíme se rozhodnout, zda zůstat v aktuálním stavu a zaplatit určitou částku nákladů za jednotku času, nebo přejít do jiného státu a zaplatit nějaké pevné velké náklady bez dalších plateb.^[1] Půjčovna lyží^[2][3] je jedním z příkladů, kdy pronájem / koupě představuje celý problém. Jeho základní verze je:

Osoba se chystá lyžovat neznámý počet dní. Pronájem lyží stojí 1 $ na den a nákup lyží stojí 10 $. Každý den se musí člověk rozhodnout, zda si bude i nadále půjčovat lyže na jeden den nebo si koupí pár lyží. Pokud daná osoba předem ví, kolik dní bude lyžovat, může se rozhodnout pro své minimální náklady. Pokud bude lyžovat déle než 10 dní, bude levnější koupit lyže, ale pokud bude lyžovat méně než 10 dní, bude levnější si půjčit. Co by měla, když předem neví, kolik dní se bude lyžovat?^{[Citace je zapotřebí ]}

Formálně lze problém nastavit následujícím způsobem. Existuje několik dní d (neznámé), že osoba bude lyžovat. Cílem je najít algoritmus, který minimalizuje poměr mezi tím, co člověk zaplatí pomocí algoritmu (který neví d) a co by daná osoba optimálně zaplatila, kdyby to věděla d dopředu. Problém je obecně analyzován v nejhorším případě, kdy je algoritmus pevný a poté se podíváme na výkonnost algoritmu v nejhorším případě přes všechny možné d. Zejména neexistují žádné předpoklady týkající se distribuce d (a je to snadno vidět, se znalostí distribuce d, upřednostňovala by se jiná analýza i jiná řešení).^{[Citace je zapotřebí ]}

Algoritmus zvratu

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Algoritmus rentability dává člověku pokyn, aby si pronajal na 9 dní a koupil si lyže 10. den ráno, pokud ještě lyžuje.^[4] Pokud musíte během prvních 9 dnů přestat lyžovat, stojí to stejně jako to, co byste zaplatili, kdyby jste věděli, kolik dní se lyžuje. Pokud člověk musí přestat lyžovat po 10. dni, jeho cena je 19 USD, což je o 90% více, než kolik by člověk zaplatil, kdyby věděl počet dní, kdy by mohl lyžovat předem. Toto je nejhorší případ pro algoritmus rentability.

Algoritmus zvratu je znám jako nejlepší deterministický algoritmus pro tento problém.

Rovnoměrné

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Osoba může hodit mincí. Pokud to přijde, koupí lyže osmý den; jinak si koupí lyže 10. den. Toto je příklad a randomizovaný algoritmus. Očekávané náklady jsou nejvýše o 80% vyšší, než kolik by daná osoba zaplatila, kdyby věděla, kolik dní bude lyžovat, bez ohledu na to, kolik dní lyžuje. Zejména pokud osoba lyžuje po dobu 10 dnů, její očekávaná cena je 1/2 [7 +10] + 1/2 [9 + 10] = 18 dolarů, pouze 80% přebytek místo 90%.

Randomizovaný algoritmus lze chápat jako složení různých algoritmů, z nichž každý se vyskytuje s danou pravděpodobností. Definujeme očekávaný konkurenční poměr na dané instanci i jako:

${displaystyle E_ {i} = součet _ {j} P (ALG_ {j}) cdot ALG_ {j} (i)}$, kde ${displaystyle ALG_ {j} (i)}$ je daný konkurenční poměr například i ${displaystyle ALG_ {j}}$.

V důsledku toho je konkurenční poměr randomizovaného algoritmu dán nejhorší hodnotou ${displaystyle E_ {i}}$ ve všech uvedených případech. V případě půjčení lyží na převrácení mincí si povšimněte, že randomizovaný algoritmus má 2 možné větve: Pokud se mince objeví na hlavě, nakupujeme 8. den, jinak nakupujeme 10. den. ${displaystyle ALG_ {heads}}$ a ${displaystyle ALG_ {ocasy}}$, resp. ${displaystyle E_ {i} = P (ALG_ {heads}) cdot ALG_ {heads} (i) + P (ALG_ {tails}) cdot ALG_ {tails} (i) = {frac {1} {2}} cdot 1 + {frac {1} {2}} cdot 1 = 1}$, pro ${displaystyle i <8}$. ${displaystyle E_ {8} = P (ALG_ {heads}) cdot ALG_ {heads} (8) + P (ALG_ {tails}) cdot ALG_ {tails} (8) = {frac {1} {2}} cdot { frac {17} {8}} + {frac {1} {2}} cdot 1 = 1,5625}$, ${displaystyle E_ {9} = P (ALG_ {heads}) cdot ALG_ {heads} (9) + P (ALG_ {tails}) cdot ALG_ {tails} (9) = {frac {1} {2}} cdot { frac {17} {9}} + {frac {1} {2}} cdot 1 = 1,444444}$, a ${displaystyle E_ {i} = P (ALG_ {heads}) cdot ALG_ {heads} (i) + P (ALG_ {tails}) cdot ALG_ {tails} (i) = {frac {1} {2}} cdot { frac {17} {10}} + {frac {1} {2}} cdot {frac {19} {10}} = 1,8}$, pro ${displaystyle igeq 10}$.

Proto je konkurenční poměr náhodného algoritmu převrácení mincí půjčovny lyží 1,8.

Nejlepší randomizovaný algoritmus proti zapomnětlivý protivník je vybrat si náhodně nějaký den podle následujícího rozdělení p, pronajmout si i-1 dny a koupit si lyže ráno, i když ještě jsou na lyžích. Karlin a kol.^[2] nejprve představil tento algoritmus s distribucí${displaystyle p_ {i} = left {{egin {array} {ll} ({frac {b-1} {b}}) ^ {bi} {frac {1} {b (1- (1- (1 / b)) ^ {b})}} & ileq b 0 & i> ohyb {pole}} vpravo.,}$kde nákup lyží stojí $${displaystyle b}$ a pronájem stojí $ 1. Jeho očekávaná cena je maximálně e / (e-1) ${displaystyle cca}$ 1,58násobek částky, kterou by člověk zaplatil, kdyby věděl, kolik dní by se lyžovalo. Žádný randomizovaný algoritmus nemůže být lepší.

Aplikace

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

• Snoopy ukládání do mezipaměti:^[2] několik mezipamětí sdílí stejný paměťový prostor, který je rozdělen na bloky. Když mezipaměť zapisuje do bloku, mezipaměti, které sdílejí blok, stráví aktualizací 1 cyklus sběrnice. Tyto mezipaměti mohou zneplatnit blok, aby se zabránilo nákladům na aktualizaci. Existuje ale pokuta p cyklů sběrnice za zneplatnění bloku z mezipaměti, která k němu krátce poté potřebuje přístup. Můžeme rozdělit sekvence požadavku na zápis pro několik mezipamětí na sekvence požadavků pro dvě mezipaměti. Jedna mezipaměť provádí sekvenci operací zápisu do bloku. Druhá mezipaměť se musí rozhodnout, zda se má aktualizovat zaplacením 1 sběrnicového cyklu za operaci, nebo zneplatnit blok zaplacením p sběrnicových cyklů pro budoucí žádost o čtení sama. Dva mezipaměti, jeden blok snoopy ukládání do mezipaměti problém je jen problém s půjčováním lyží.

• Potvrzení TCP:^[5] Proud paketů dorazí na místo určení a vyžaduje protokol TCP, aby byl potvrzen při příjezdu. Můžeme však použít jeden potvrzovací paket k současnému potvrzení několika nevyřízených paketů, čímž se sníží režie potvrzení. Na druhou stranu, přílišné zpoždění potvrzení může narušit mechanismy kontroly přetížení TCP, a proto bychom neměli dovolit, aby se latence mezi časem příjezdu paketu a časem, kdy je potvrzení odesláno, příliš zvýšila. Karlin a kol.^[6] popsal jednoparametrovou rodinu vstupů, která se nazývá základní vstupy, a ukázal, že když je omezen na tyto základní vstupy, problém s potvrzením TCP se chová stejně jako problém s půjčováním lyží.

• Celkové plánování času dokončení:^[1] Chceme naplánovat úlohy s pevnou dobou zpracování na m identických strojích. Doba zpracování úlohy j je str_j. Každá úloha se stane známou plánovači v době jejího vydání r_j. Cílem je minimalizovat součet časů dokončení u všech úloh. Zjednodušeným problémem je jeden jediný stroj s následujícím vstupem: v čase 0 přijde úloha s časem zpracování 1; k úlohy s dobou zpracování 0 dorazí v neznámém čase. Musíme si vybrat čas zahájení pro první práci. Čekání způsobí cenu 1 za časovou jednotku, ale zahájení první úlohy před pozdějšími k úlohami může v nejhorším případě způsobit další náklady k. Na tento zjednodušený problém lze pohlížet jako na průběžnou verzi problému s půjčováním lyží.

• Refaktoring versus práce se špatným designem: Při vývoji softwaru si inženýři musí vybrat mezi třením a rizikem chyb při práci s příliš složitým designem a snížením složitosti designu před provedením změny. Zvláštní náklady na každou změnu se starým designem jsou náklady na „pronájem“, náklady na refaktoring jsou náklady na „nákup“. „Kolikrát člověk pracuje se špatným designem, než jej vyčistí?“ je problém s půjčováním lyží.

Viz také

• Protivník (online algoritmus)
• Konkurenční analýza (online algoritmus)
• Online algoritmus
• Nejhorší důkaz

Reference